link：https://codeforces.com/problemset/problem/1967/C
题意：定义 \(f(a)=s\) 中的 \(f\) 表示把序列 \(a\) 映射为其树状数组的操作（\(s\) 就是对应的树状数组），并且操作是在取模下作的，已知 \(f^k (a)=b\)，已知序列 \(b\) 和自然数 \(k\)，求 \(a\).
\(1\leq n\leq 2\times 10^5,1\leq k\leq 10^9\).
\(f^k(a)=b\)，把 \(f\) 看成一个序列的映射，\(f\) 的逆运算 \(f^{-1}\)能够表示出来：
例如原本
\[\begin{aligned} s_1&=a_1\\ s_2&=a_1+a_2\\ s_3&=a_3\\ s_4&=a_1+a_2+a_3+a_4\\ s_5&=a_5\\ s_6&=a_5+a_6 \end{aligned}\]则逆运算相当于要求我们反过来用 \(s\) 求 \(a\)：
\[\begin{aligned} a_1&=s_1\\ a_2&=s_2-s_1\\ a_3&=s_3\\ a_4&=s_4-s_3-(s_2-s_1)-s_1=s_4-s_3-s_2\\ a_5&=s_5\\ a_6&=s_6-s_5 \end{aligned}\]根据我们平常写树状数组的习惯也可以看得出，一次逆运算就是反过来，把每个数 \(a_i\) 加到 \(s_i\)，同时把 \(-a_i\) 加到 \(s[i+lowbit(i)]\) 的位置。
所以可以把 \(f^{-1}\) 拆开看，\(a_i\) 加到 \(s_i\) 是单位映射\(I\)（把a序列原封不动地映射成a序列），后面的操作用一个符号 \(A\) 表示把\(a_i\) 加到 \(s[i+lowbit(i)]\) 上，整个\(f^{-1}=I-A\).
要求 $$a=f^{-k} b=(I-A)^k b=\Big[\sum_{i=0}^k \binom{k}{i}(-1)^i A^i \Big] (b)$$
其中 \(A\) 表示上述运算， \(A^i\) 表示运算复合 \(i\) 次，比如 \(A^2\) 作用在 \(b_i\) 上，就表示将其加到 \(s[i+lowbit(i)+lowbit(i+lowbit(i))]\) 上，也就是在Fenwick Tree上跳两步的事情。很明显跳lowbit的过程至多 \(O(\log n)\) 步就会停止，因此和式中的 \(i\) 只需要处理大约20项左右，总的时间复杂度就是 \(O(n\log n)\)的。
代码很简单：
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int MOD=998244353;
int ksm(int a,int b){
int ret=1;
for(;b;b>>=1,a=(ll)a*a%MOD)if(b&1)ret=(ll)ret*a%MOD;
return ret;
}
int n,k,b[N],ans[N];
int inv_fact[100];
int C(int n,int k){
if(k>n)return 0;
int ret=1;
for(int i=n;i>=n-k+1;i--)ret=(ll)ret*i%MOD;
return (ll)ret*inv_fact[k]%MOD;
}
int lowbit(int x){return x&-x;}
int main(){
fastio;
inv_fact[0]=1;
rep(i,1,50)inv_fact[i]=(ll)inv_fact[i-1]*ksm(i,MOD-2)%MOD;
int tc;cin>>tc;
while(tc--){
cin>>n>>k;
rep(i,1,n)ans[i]=0;
rep(i,1,n){
cin>>b[i];
for(int t=0,j=i;j<=n;j+=lowbit(j),t++){
if(t&1)ans[j]=(ans[j]+MOD-(ll)C(k,t)*b[i]%MOD)%MOD;
else ans[j]=(ans[j]+(ll)C(k,t)*b[i])%MOD;
}
}
rep(i,1,n)cout<<ans[i]<<' ';
cout<<endl;
}
return 0;
}