自动搬运

查看原文

来自洛谷，原作者为

	Pengzt 自己选择的路，跪着也要走完。

搬运于2025-08-24 22:40:12，当前版本为作者最后更新于2023-01-18 15:32:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8565

发现数列 $a$ 增长的特别快，项数最多时是 $a_1 = a_2 = 1, m = 2$，也就是斐波那契数列，这样也只需要不到 $100$ 项就可以超过 $10^{18}$。

发现值域上点的分布越来越稀疏且点极少，可以考虑搜索，函数 dfs(val, cur) 表示凑出 $x$ 还需要 $val$，现在在考虑 $cur$。

但光是搜索肯定不能过这道题，考虑优化。

先记忆化掉重复的操作，可以用一个 map 来存储，然后可以进行可行性剪枝，如果以后再怎么凑都不行，直接剪枝，可以用前缀和优化一下。

但是这样只有 30 分。

可以改变一下搜索的顺序，因为先考虑小元素的话，会有较多的无用的搜索，且小元素较灵活，更容易凑到 $x$，故可以从大到小的考虑。这样就可以过了。

注意：判断能否返回时是 mp[cur].conut(val)，而不是 mp[cur][val]，否则会超时。因为如果这样判断的话，会直接额外开一个节点，对每一层都是如此，但第一次搜索时会额外开 $2^{dep - 1}$ 个节点，会使后面的搜索查询越来越慢（尽管迟早也要开，等于这样使常数变大了不少）。

时空可过。

代码：

#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;
}