CF1967C Fenwick Tree 题解

· · 题解

题意：定义 f(a) 表示将 a 序列变为其所对应的树状数组。已知 f^k(a)=b，给定长度为 n 的序列 b，求 a 序列。

很神奇的一道组合题。

首先我们考虑树状数组的结构。会发现 a_i 最终一定只会对 a_i 以及 a_i 的祖先节点产生贡献。那么假设有两点 u,v，且 u 在 v 的上面 d 层，考虑 v 对 u 会贡献多少次。其实这等价于从 v 开始走 k 步（每一步可以选择不动）走到 u 的路径总数，因为每走一步都相当于是做了一次 f 操作。而求这种路径数可以直接用插板法解决，答案为 C_{d+k-1}^{k-1}。

于是我们知道了每一个点对其祖先的贡献。又因为我们已知最终的 b 序列，所以我们可以枚举每一个点以及它的所有祖先，将它祖先的值减去它对祖先的贡献即可。这样最终得到的就是原序列 a 了。注意枚举点一定要从叶子往上枚举，因为需要保证当前点的儿子对它的贡献已经被减掉了，这样它对它祖先的贡献才是正确的。

因为每个点在树状数组上的祖先最多有 \log(n) 个，所以总时间复杂度 O(n \log n)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
const int mod = 998244353; 
int T,n,a[MAXN],inv[MAXN],k;    
inline int Lowbit(int x) {return (x & -x);}
signed main() {
    inv[0] = inv[1] = 1;
    for(int i = 2;i < MAXN;i++)
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    for(cin >> T;T;T--,puts("")) {
        cin >> n >> k;
        for(int i = 1;i <= n;i++) cin >> a[i];
        for(int v = 1;v <= n;v++) {
            int C = 1;
            for(int d = 1,u = v + Lowbit(v);u <= n;u += Lowbit(u),d++) {
                C = C * ((d + k - 1) * inv[d] % mod) % mod;
                a[u] = (a[u] - C * a[v] % mod + mod) % mod;
            }
        }
        for(int i = 1;i <= n;i++) cout << a[i] << " ";
    } return 0;
}