题解 P5641 【【CSGRound2】开拓者的卓识】
tzc_wk
·
·
题解
我的博客园
一道挺有意思的题，并且竟然自己搞出来了！
首先要清楚 sum_{k,l,r} 的含义是什么。
$sum_{2,l,r}$ 根据 $sum_{k,l,r}$ 的公式，可以看作是选择一个区间 $[l_1,r_1]\subseteq [l,r]$，再将 $a_{l_1}$ 到 $a_{r_1}$ 的和累加入答案中。
$sum_{3,l,r}$ 是选择一个区间 $[l_1,r_1]\subseteq[l,r]$，再对 $[l_1,r_1]$ 求一遍 $sum_{2,l_1,r_1}$，也就是再选择一个区间 $[l_2,r_2]\in [l_1,r_1]$ 将 $a_{l_2}$ 到 $a_{r_2}$ 的和加入答案中。
…………
$sum_{k,l,r}$ 就是选择 $k-1$ 个区间 $[l_{k-1},r_{k-1}]\subseteq [l_{k-2},r_{k-2}]\subseteq\dots\subseteq[l_1,r_1]\subseteq [l,r]$，并将 $[l_k,r_k]$ 的和加入答案中。
考虑转换贡献体，枚举 $a_i$ 会对 $sum_{k,1,r}$ 产生多大的贡献，也就是有多少组区间 $[l_i,r_i]$ 满足 $i\in[l_{k-1},r_{k-1}]\subseteq [l_{k-2},r_{k-2}]\subseteq\dots\subseteq[l_1,r_1]\subseteq [1,r]$，由于是相邻区间之间是包含关系，故 $i\geq l_{k-1}\geq l_{k-2}\geq\dots\geq l_1\geq 1$，记 $d_k=i-l_{k-1},d_{k-1}=l_{k-1}-l_{k-2},\dots,d_2=l_2-l_1,d_1=l_1-1$，那么有 $d_1+d_2+d_3+\dots+d_k=i-1$，其中 $d_i\geq 0$，采用隔板法可求得所有 $(l_1,l_2,\dots,l_{k-1})$ 的个数为 $\dbinom{i+k-2}{k-1}$。同理可得所有 $(r_1,r_2,\dots,r_{k-1})$ 的个数为 $\dbinom{r-i+k-1}{k-1}$。
故 $a_i$ 对 $r$ 产生的贡献为 $a_i\times \dbinom{i+k-2}{k-1}\times \dbinom{r-i+k-1}{k-1}$。记 $A_i=a_i\times \dbinom{i+k-2}{k-1},B_i=\dbinom{i+k-2}{k-1}$，求一遍 $A$ 与 $B$ 的卷积 $C$，那么 $C_{r+1}=sum_{k,1,r}$。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
x=0;char c=getchar();T neg=1;
while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=neg;
}
const int pr=3;
const int MOD=998244353;
const int MAXN=1e5;
const int MAXP=1<<18;
int n,k,x[MAXN+5],t[MAXN+5];
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;return ret;}
int a[MAXP+5],b[MAXP+5],c[MAXP+5],LEN=1,LOG=0,inv[MAXP+5],rev[MAXP+5],prs[MAXP+5][2],ipr;
void NTT(int *a,int len,int type){
int lg=log2(len);
for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
for(int i=0;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int i=2;i<=len;i<<=1){
int W=prs[i][type<0];
for(int j=0;j<len;j+=i){
int w=1;
for(int k=0;k<(i>>1);k++,w=1ll*w*W%MOD){
int X=a[j+k],Y=1ll*a[(i>>1)+j+k]*w%MOD;
a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;
}
}
}
if(type==-1) for(int i=0;i<len;i++) a[i]=1ll*a[i]*inv[len]%MOD;
}
int main(){
scanf("%d%d",&n,&k);ipr=qpow(pr,MOD-2);
for(int i=1;i<=n;i++) scanf("%d",&x[i]);ll mul=1;
for(int i=1;i<=n;i++) t[i]=mul,mul=1ll*mul*qpow(i,MOD-2)%MOD,mul=1ll*mul*(i+k-1)%MOD;
for(int i=1;i<=n;i++) a[i]=1ll*t[i]*x[i]%MOD,b[i]=t[i];
while(LEN<=n+n) LEN<<=1,LOG++;
for(int i=1;i<=LEN;i<<=1){
inv[i]=qpow(i,MOD-2);
prs[i][0]=qpow(pr,(MOD-1)/i);
prs[i][1]=qpow(ipr,(MOD-1)/i);
} NTT(a,LEN,1);NTT(b,LEN,1);
for(int i=0;i<LEN;i++) c[i]=1ll*a[i]*b[i]%MOD;
NTT(c,LEN,-1);for(int i=1;i<=n;i++) printf("%d ",c[i+1]);
return 0;
}
```