BZOJ2159 : Crash 的文明世界

$x^k=\sum_{i=1}^k Stirling2(k,i)\times i!\times C(x,i)$

设$f[i][j]=\sum_{k=1}^n C(dist(i,k),j)$。

则可以利用$C(i,j)=C(i-1,j-1)+C(i-1,j)$,通过树形DP求出$f$。

时间复杂度$O((n+k)k)$。

#include<cstdio>
const int N=50010,M=155,P=10007;
int n,k,i,j,x,y,S[M][M],fac[M],g[N],v[N<<1],nxt[N<<1],ed;
int d[N][M],u[N][M],size[N],ans,L,now,tmp,A,B,Q;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void up(int&x,int y){x=(x+y+P)%P;}
void caldown(int x,int y){
d[x][0]=1;
for(int i=g[x];i;i=nxt[i])if(v[i]!=y){
caldown(v[i],x);
up(d[x][0],d[v[i]][0]);
for(int j=1;j<=k;j++)up(d[x][j],d[v[i]][j-1]+d[v[i]][j]);
}
}
void calup(int x,int y){
if(y){
u[x][0]=n-d[x][0];
for(int j=1;j<=k;j++){
u[x][j]=(((u[y][j-1]+u[y][j]+d[y][j-1]+d[y][j]-2*d[x][j-1]-d[x][j])%P)+P)%P;
if(j>1)up(u[x][j],-d[x][j-2]);
}
}
for(int i=g[x];i;i=nxt[i])if(v[i]!=y)calup(v[i],x);
}
int main(){
scanf("%d%d%d%d%d%d%d",&n,&k,&L,&now,&A,&B,&Q);
for(S[0][0]=i=1;i<=k;i++)for(S[i][i]=j=1;j<i;j++)S[i][j]=(j*S[i-1][j]+S[i-1][j-1])%P;
for(fac[0]=i=1;i<=k;i++)fac[i]=fac[i-1]*i%P;
for(i=1;i<n;i++){
now=(now*A+B)%Q,tmp=i<L?i:L;
x=i-now%tmp,y=i+1;
add(x,y),add(y,x);
}
caldown(1,0),calup(1,0);
for(i=1;i<=n;i++){
for(ans=0,j=1;j<=k;j++)up(ans,1LL*S[k][j]*fac[j]*(u[i][j]+d[i][j])%P);
printf("%d\n",ans);
}
return 0;
}

  

上一篇:iOS面试的算法相关


下一篇:iOS masonry九宫格 单行 多行布局