P8565 Sultan Rage 题解

Pengzt · 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;
}