bzoj
cogs

description

给你一棵树，要你对每个点\(u\)，求
\[s_u=\sum_{v=1}^n dis(u,v)^k\]
\(n\le30000,k<=150\)

sol

根据斯特林数反演
\[m^n=\sum_{i=0}^m S(n,i)\binom mi i!\]
所以要求的就是
\[s_u=\sum_{v=1}^n\sum_{i=0}^k S(k,i)\binom{dis(u,v)}{i}i!=\sum_{i=0}^k S(k,i)i!\sum_{v=1}^n\binom{dis(u,v)}{i}\]
所以只要求\(\sum_{v=1}^n\binom{dis(u,v)}{i}\)就行了。这个可以\(dp\)转移，方法和组合数递推是一样的，复杂度\(O(nk)\)。
因为对每个点都需要求，所以需要跑一遍换根\(dp\)。

code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int N = 50005;
const int K = 155;
const int mod = 10007;
int n,k,to[N<<1],nxt[N<<1],head[N],cnt,f[N][K],S[K][K],jc[K],ans[N];
void link(int u,int v){
    to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
    to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
}
void Input_a(){
    n=gi();k=gi();
    for (int i=1;i<n;++i) link(gi(),gi());
}
void Input_b(){
    n=gi();k=gi();int L=gi(),now=gi(),A=gi(),B=gi(),Q=gi(),tmp;
    for (int i=1;i<n;++i) now=(now*A+B)%Q,tmp=i<L?i:L,link(i-now%tmp,i+1);
}
inline void add(int &x,int y){(x+=y)%=mod;}
inline void mns(int &x,int y){(x+=mod-y)%=mod;}
void trans(int u,int v){
    add(f[u][0],f[v][0]);
    for (int i=1;i<=k;++i) add(f[u][i],(f[v][i]+f[v][i-1])%mod);
}
void retrans(int u,int v){
    mns(f[u][0],f[v][0]);
    for (int i=1;i<=k;++i) mns(f[u][i],(f[v][i]+f[v][i-1])%mod);
}
void dfs1(int u,int ff){
    f[u][0]=1;
    for (int e=head[u];e;e=nxt[e])
        if (to[e]!=ff) dfs1(to[e],u),trans(u,to[e]);
}
void dfs2(int u,int ff){
    for (int i=0;i<=k;++i) add(ans[u],1ll*f[u][i]*S[k][i]*jc[i]%mod);
    for (int e=head[u];e;e=nxt[e])
        if (to[e]!=ff){
            retrans(u,to[e]),trans(to[e],u);
            dfs2(to[e],u);
            retrans(to[e],u),trans(u,to[e]);
        }
}
int main(){
//  Input_a();
    Input_b();
    jc[0]=S[0][0]=1;
    for (int i=1;i<=k;++i) jc[i]=1ll*jc[i-1]*i%mod;
    for (int i=1;i<=k;++i)
        for (int j=1;j<=i;++j)
            S[i][j]=(S[i-1][j]*j+S[i-1][j-1])%mod;
    dfs1(1,0);dfs2(1,0);
    for (int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}

[BZOJ2159]Crash 的文明世界

原文：https://www.cnblogs.com/zhoushuyu/p/9484227.html