[ARC232E] Doubling

Genius_Star · 2026-10-20 09:05:32 · 题解

或许更好的阅读体验。

区区题，这题 *3600？？？

思路：

考虑每个位置操作的次数 a_i，因为跟操作顺序无关，我们总可以从前往后操作，这里令原来的 x_i 为 A_i，操作后的是 A'_i = A_i - a_i + 2a_{i - 1}，因为 A'_i \ge 0，所以 a_i \le A_i + 2a_{i - 1}。

对于所有满足这个条件的 a 对应的序列显然互不相同（容易反证法证明），于是只需要数满足 a_1 \le A_1, a_i \le A_i + 2_{a - 1} 的序列 a 数量即可；然后答案要对于每个 k 算出 \sum a_i = k 的方案。

有一个显然的 dp，考虑 dp_{i, j, k} 表示前 i 个数选的 \sum a = j 然后 a_i = k 的方案数，转移是 容易的，可以刷表转移 i + 1，即枚举 a_{i + 1} \in [0, A_{i + 1} + 2k]，直接做是 O(nk^3) 的，完全无法通过。

看起来状态数就不太好优化，考虑生成函数，你发现一维生成函数也是不太好转移的，刚好 dp 后面有两维，于是设：

初始 F_1(x, y) = \sum_{i \le A_1} x^i y^i；刷表可以得到：

这个递推式子一点也不漂亮，想了挺久感觉不太能求封闭形式；然后你可以注意到一个关键性质，这个递推式中第一项始终是 x 即算 F_i(x, \cdot)，然后再考虑一下最终答案是什么，求 \sum a = m 的方案数是 [x^m]F_n(x, 1)，于是只需要算 F_n(x, 1)。

使用上面的递推式子：

然后你还要算 F_{n - 1}(x, x^2)，相当于要多算 F_{n - 2}(x, x^6)，推广开来，对于每个 (i, k) 你需要算 F_i(x, x^{2^k - 2})，显然 k 是 n 级别的；然后考虑除法怎么做，你需要乘上一个 \frac{1}{1 - x^p} 这个形式，可以看作乘以 (1 + x^p + x^{2p} + \cdots)，于是可以看作一个 p 前缀和的形式，即 s_i \gets s_i + s_{i - p}，可以 O(k) 算。

于是你要进行 n^2 次多项式的加减操作，时间复杂度是 O(n^2k) 的，可以轻松通过；精细实现可以做到 O(n \min(n, \log k) k)，不过没有必要。

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 21, M = 2.5e5 + 10, mod = 998244353;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
inline void getadd(int &x, int y){
    x = (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline int add(int x, int y){
    return (x + y >= mod) ? (x + y - mod) : (x + y); 
}
inline void getdec(int &x, int y){
    x = (x < y) ? (x - y + mod) : (x - y);
}
inline int dec(int x, int y){
    return (x < y) ? (x - y + mod) : (x - y);
}
int n, K;
int poww[N], A[N];
class poly{
public:
    int a[M];
    inline int& operator[](int i){
        return a[i];
    }
    inline void getp(int p){
        for(int i = p; i <= K; ++i)
          getadd(a[i], a[i - p]);
    }
}F[N][N];
int main(){
    n = read(), K = read();
    for(int i = 0; i < n; ++i){
        A[i] = read();
        poww[i] = 1 << i;
        // cout << i << ' ' << poww[i] << '\n';
    }
    poww[n] = 1 << n;
    for(int i = 0; i < n; ++i){
        int p = poww[i + 1] - 2;
        for(int j = 0; j <= A[0]; ++j){
            int x = j * (p + 1);
            if(x > K)
              break;
            F[0][i][x] = 1;
            // cout << i << ' ' << x << '\n';
        }
    }
    for(int i = 1; i < n; ++i){
        for(int k = 0; k < n - i; ++k){
            int p = poww[k + 1] - 2;
            ll x = 1ll * (p + 1) * (A[i] + 1);
            for(int j = 0; j <= K; ++j){
                F[i][k][j] = F[i - 1][0][j];
                if(j >= x)
                  getdec(F[i][k][j], F[i - 1][k + 1][j - x]);
            }
            F[i][k].getp(p + 1);
        }
    }
    for(int i = 1; i <= K; ++i){
        write(F[n - 1][0][i]);
        putchar(' ');
    }
    return 0;
}