P8565 Sultan Rage

题目描述

有一个数列 {an}\{a_n\}{an​} 满足对 $n>m$ 均有 $a_n=\sum _{j=1}^m{a}_{n-j}$，并且 $a_1,a_2,\cdots ,a_m$ 是输入中给出的正整数。

$q$ 次询问，每一次给出一个正整数 $x$，问有多少个不可重正整数集 $S$ 满足 $\sum _{s\in S}{a}_s=x$。答案对质数 $998244353$ 取模。

本题有多组数据。

输入格式

本题有多组数据。

第一行一个整数 $T$ 表示数据组数。对于每一组数据：

第一行两个整数 $m,q$。

第二行 $m$ 个整数 $a_1,a_2,\cdots ,a_m$。

第三行 $q$ 个整数，每一个整数代表一次询问。

输出格式

对于每组询问输出一行表示答案。

输入输出样例 #1

输入 #1

2
2 5
1 1
3 5 7 9 11
3 5
1 2 5
4 7 10 18 22

输出 #1

3
3
3
5
5
0
1
1
1
1

说明/提示

对于所有数据，$T=5$，$2\le m\le 100$，$1\le q,a_i\le 100$，$1\le x\le 10^{18}$。
$$\begin{array}{cccccc}\text{测试点编号}& \mathbf{m}\le & \mathbf{q}\le & {\mathbf{a}}_{\mathbf{i}}\le & \mathbf{x}\le & \text{特殊性质}\\ \text{1}\sim 2& 8& 8& 8& 100& \\ 3\sim 5& 15& & 15& 10^3& \\ \text{6}& & & & 1& \\ 7\sim 11& & 1& & & \text{A}\\ 12\sim 16& 2& & & & \\ 17\sim 20& & & & & \end{array}$$

$\text{A}$：$m=10$，且 $x$ 在所有可能的 $x$ 中随机生成。

C++实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
ll read() {
	ll ret = 0, sgn = 0;
	char ch = getchar();
	while (!isdigit(ch)) sgn |= ch == '-', ch = getchar();
	while (isdigit(ch)) ret = ret * 10 + ch - '0', ch = getchar();
	return sgn ? -ret : ret;
}
const int N = 180, mod = 998244353;
const ll INF = 1e18;
int n, q;
ll a[N], sum[N];
map<ll, int> mp[N];

int dfs(ll x, int cur) {
	if (x < 0 || x > sum[cur]) return 0;
	if (!cur) return (x == 0);
	if (mp[cur].count(x)) return mp[cur][x];
	return mp[cur][x] = (dfs(x - a[cur], cur - 1) + dfs(x, cur - 1)) % mod;
}

int main() {
	int T = read();
	while (T--) {
		n = read(), q = read();
		for (int i = 1; i <= n; i++) a[i] = read();
		int m = n;
		while (a[m] <= INF) {
			a[++m] = 0;
			for (int i = 1; i <= n; i++) a[m] += a[m - i];
		}
		n = m - 1;
		for (int i = 1; i <= n; i++) {
			sum[i] = sum[i - 1] + a[i];
			mp[i].clear();
		}
		while (q--) {
			ll x = read();
			printf("%d\n", dfs(x, n));
		}
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容