题解：CF1967C Fenwick Tree

· · 题解

我们充分发扬人类智慧

题意

我们定义操作为：

a_i = (\sum _ {j = \operatorname{lowbit}(i)}^i a_j) \bmod 998244353

给出 k 此操作后的结果 b_i，求原先数组 a_i \bmod 998244353 的结果。

更改关系

由于 k 非常大，且部分下标下的数不变，如 a_1,a_3，考虑先推更改关系，再用于推原数组。
我们列举一下影响关系，易于知道这些关系简化成祖先到子孙的关系可以得到一棵树状数组。

贡献

对于祖先关系的两点，我们发现同层的两个点对共同祖先的更改可以按同类处理，我们可以考虑操作时 a_1 对 a_2,a_4 的影响：

  1. 操作一次，a_2 共加上一次 a_1，a_4 加上一次 a_1。
  2. 操作两次，a_2 共加上 2 次 a_1，a_4 加上 3 次 a_1。
  3. 操作三次，a_2 共加上 3 次 a_1，a_4 加上 6 次 a_1。

由此我们猜测当 j 节点为比 i 节点高 t 层的祖先，操作 k 次后，b_j 共加过 \frac{(k + t - 1)!}{t! \cdot (k - 1)!} 次 a_i。

接下来证明：

  1. 当 t = 1 时，b_j 加了 k = \frac{(k +1 - 1)!}{1! \cdot (k - 1)!} 次 a_i，符合条件；
  2. 若 t = r 时成立，当 t = r + 1 时，加上的倍数为：
\sum _{o = 1}^ {k} \frac{(o + r - 1)!}{r! \cdot (o - 1)!}

因为

\frac{(o + r - 1)!}{r! \cdot (o - 1)!} = \frac{1}{r + 1}\cdot (\frac{(o + r)!}{r! \cdot (o - 1)!} - \frac{(o + r - 1)!}{r! \cdot (o - 2)!})

故

\begin{aligned} \sum _{o = 1}^ {k} \frac{(o + r - 1)!}{r! \cdot (o - 1)!} &= \frac{1}{r + 1}\cdot (\frac{(k + r)!}{r! \cdot (k - 1)!} - 0)\\ &= \frac{(k + (r + 1) - 1) !}{(r + 1) ! \cdot (k - 1) !} \\ &= \frac{(k + t - 1)!}{t! \cdot (k - 1)!} \end{aligned}

证毕。

3. 反推

我们易得可以从前往后遍历，遍历到 i 时，我们减去 a_i 因操作对相应的 b_j 的贡献，就会得到答案。

通过类似树状数组的修改方法，可以得到一个 \operatorname{O}(n\log n) 的方法。

4. 上代码

#include<cstdio>
using namespace std;
int n,m,k,b[200009],dt[29],inv[29];
const int mod = 998244353;
int main(){
    scanf("%d",&m);
    while(m--){
        scanf("%d %d",&n,&k);
        dt[0] = 1;
        for(int i = 1; i <= 20; i ++){
            inv[i] = (i == 1) ? 1 : 1ll * (mod - mod / i) * inv[mod % i] % mod;
            dt[i] = 1ll * dt[i - 1] * (k + i - 1) % mod;
            dt[i] = 1ll * dt[i] * inv[i] % mod;
        }
        for(int i = 1; i <= n; i ++){
            scanf("%d",&b[i]);
        }
        for(int i = 1; i <= n; i ++){
            int o = i;
            for(int j = 1; o + (o & (-o)) <= n; j ++){
                o += o & (-o);
                b[o] = (b[o] - 1ll * b[i] * dt[j] % mod + mod) % mod;
                //printf("%d %d %d\n",i,o,b[o]);
            }
        }
        for(int i = 1; i <= n; i ++){
            printf("%d ",b[i]);
        }
        puts("");
        //return 0;
    }
    return 0;
}