【BZOJ2159】Crash的文明世界 【斯特林數】【樹形dp】

題目傳送門

題意：求對于每個i的 ∑nj=1dis(i,j)k ∑ j = 1 n d i s ( i , j ) k 。

這裡有一個公式： xk=∑xi=1S(k,i)Aix x k = ∑ i = 1 x S ( k , i ) A x i 。S是第二類斯特林數，A是排列數。

其實這個式子的組合意義就是把 k k 個球放進xx個盒子的方案數。右邊的意思是枚舉有哪些盒子要放球，選球的方案數乘上選盒子的方案數。

這個是不好統計的，我們把它變一下： xk=∑xi=1S(k,i)i!Cix x k = ∑ i = 1 x S ( k , i ) i ! C x i 。

于是我們令 f[i][j]=∑nk=1C(dis(i,k),j) f [ i ] [ j ] = ∑ k = 1 n C ( d i s ( i , k ) , j ) ，通過兩次樹形dp求出f數組，最後再統計一下即可。具體方法詳見代碼。

常數極大的代碼

#include<cstdio>
typedef int ll;
const int N=,M=;
const ll mod=;
int n,k,u,v,cnt,head[N],to[N*],nxt[N*];
ll ans,f[N][M][],jc[M],s[M][M];
void adde(int u,int v){
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void dfs1(int pre,int u){
    f[u][][]=;
    int v;
    for(int i=head[u];i;i=nxt[i]){
        v=to[i];
        if(v!=pre){
            dfs1(u,v);
            f[u][][]=(f[u][][]+f[v][][])%mod;
            for(int j=;j<=k;j++){
                f[u][j][]=(f[u][j][]+f[v][j-][]+f[v][j][])%mod;
            }
        }
    }
}
void dfs2(int pre,int u){
    if(pre){
        f[u][][]=(n-f[u][][]+mod)%mod;
        for(int i=;i<=k;i++){
            f[u][i][]=(f[u][i][]+f[pre][i][]+f[pre][i-][]+f[pre][i-][]+f[pre][i][])%mod;
            f[u][i][]=((f[u][i][]-f[u][i][]-*f[u][i-][])%mod+mod)%mod;
            if(i>){
                f[u][i][]=(f[u][i][]-f[u][i-][]+mod)%mod;
            }
        }
    }
    int v;
    for(int i=head[u];i;i=nxt[i]){
        v=to[i];
        if(v!=pre){
            dfs2(u,v);
        }
    }
}
int main(){
    int L,now,A,B,Q,tmp;
    scanf("%d%d%d",&n,&k,&L); 
    scanf("%d%d%d%d",&now,&A,&B,&Q); 
    for (int i=;i<n;i++){ 
        now=(now*A+B)%Q;
        tmp=(i<L)?i:L;
        u=i-now%tmp;
        v=i+;
        adde(u,v);
        adde(v,u);
    }
/*  scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        adde(u,v);
        adde(v,u);
    }*/
    dfs1(,);
    dfs2(,);
    jc[]=s[][]=;
    for(int i=;i<=k;i++){
        jc[i]=i*jc[i-]%mod;
        for(int j=;j<=k;j++){
            s[i][j]=(s[i-][j-]+j*s[i-][j])%mod;
        }
    }
    for(int i=;i<=n;i++){
        ans=;
        for(int j=;j<=k;j++){
            ans=(ans+L*s[k][j]*jc[j]%mod*(f[i][j][]+f[i][j][])%mod)%mod;
        }
        printf("%d\n",ans);
    }
    return ;
}