1967C - 树状数组

---

一、题意与图理解

题目定义：

• 对数组 $a$，$s = f(a)$ 是其 Fenwick Tree 表示，其中$$s_u = \sum_{v \in \text{subtree}(u)} a_v \mod 998244353 $$即每个节点 $u$ 存储其对应区间内 $a$ 的和。
• $f^k(a)$ 表示对 $a$ 连续执行 $k$ 次 $f$ 操作。
• 已知 $b = f^k(a)$，求原数组 $a$。

结合图：每个 $a_i$ 只出现在它所有祖先节点的子树中，因此 $a_i$ 会被加到所有这些祖先节点上。

---

二、标程核心数学结论

1. 关键系数公式

设：

• $u$ 为任意节点，$v$ 是 $u$ 的祖先节点；
• $\Delta d = dep(u) - dep(v)$ 为 $u$ 到 $v$ 的深度差。

经过 $k$ 次 $f$ 操作后，$a_u$ 在 $b_v$ 中的系数为：

$$\boldsymbol{\binom{\Delta d + k - 1}{\Delta d}}$$

直观理解

每次 $f$ 操作，一个节点的值会“向上传播”到所有祖先节点。这等价于： 从 $u$ 到 $v$ 需要向上走 $\Delta d$ 步，经过 $k$ 次操作，总共相当于把 $k$ 个“增量”分配到这 $\Delta d$ 步上，其方案数就是组合数 $\binom{\Delta d + k - 1}{\Delta d}$。

---

三、标程给出的算法思路

1. 基础性质：叶子节点直接相等

对于 Fenwick Tree 的叶子节点（即编号为奇数的节点），其在树中没有子节点（除自身外），因此：

$$b_u = a_u$$

所以，所有叶子节点的 $a$ 值可以直接由 $b$ 得到。

2. 按节点顺序递推修正

标程核心做法：

1. 按节点编号从小到大遍历（即从下往上）；
2. 对于当前节点 $u$，此时它的所有子节点（编号更小）的 $a$ 值都已经求出；
3. 对于 $u$ 的所有祖先节点 $v$，用已知的 $a_u$ 去修正 $b_v$：$$b_v \leftarrow b_v - a_u \times \binom{\Delta d + k - 1}{\Delta d} \pmod{998244353} $$
4. 处理完所有子节点后，当前节点 $u$ 的 $b_u$ 就等于 $a_u$，直接赋值。

3. 时间复杂度

Fenwick Tree 的高度为 $O(\log n)$，每个节点最多有 $O(\log n)$ 个祖先，因此总复杂度为：

$$O(n \log n)$$

完全满足题目 $n \le 2 \times 10^5$ 的限制。

---

四、关键预处理：组合数计算

我们需要计算 $\binom{\Delta d + k - 1}{\Delta d} \mod 998244353$。 设 $d = \Delta d$，则：

$$\binom{d + k - 1}{d} = \frac{(k)(k+1)\cdots(k+d-1)}{d!} \mod 998244353 $$

由于 $d$ 的最大值为树高 $O(\log n) \le 20$，我们可以对每个节点 $u$ 预先计算它到所有祖先的 $d$，并在 $O(\log n)$ 时间内算出对应的组合数。

---

五、C++ 标程级实现代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MOD = 998244353;
const int MAXN = 2e5 + 5;
const int LOG = 20; // log2(2e5) ≈ 18

ll inv_fact[LOG];

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void precompute() {
    inv_fact[0] = 1;
    for (int i = 1; i < LOG; i++)
        inv_fact[i] = qpow(i, MOD - 2);
}

ll comb(ll k, int d) {
    if (d == 0) return 1;
    ll res = 1;
    for (int i = 0; i < d; i++)
        res = res * ((k + i) % MOD) % MOD;
    for (int i = 1; i <= d; i++)
        res = res * inv_fact[i] % MOD;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute();
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        ll k;
        cin >> n >> k;
        vector<ll> b(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> b[i];
        
        vector<ll> a(n + 1);
        for (int u = 1; u <= n; u++) {
            // 计算u到其所有祖先的组合数，并修正b
            int cur = u;
            int d = 0;
            while (cur <= n) {
                ll c = comb(k, d);
                if (cur != u) {
                    b[cur] = (b[cur] - a[u] * c % MOD + MOD) % MOD;
                }
                cur += cur & -cur;
                d++;
            }
            a[u] = b[u];
        }
        
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << "\n";
    }
    return 0;
}

---

六、正确性保证

• 按从小到大顺序处理，保证处理节点 $u$ 时，其所有子节点的 $a$ 值都已求出；
• 用组合数修正所有祖先节点后，b[u] 就不再包含任何子节点的贡献，直接等于 a[u]；
• 时间复杂度 $O(n \log n)$，可以通过所有测试点。

---