bzoj 2159 Crash的文明世界

题目大意：

对每个点$x$ 求$\sum\limits_{i=1}^{n} {dis(i,j)}^k$

思路：

首先可以把式子展开得到$dis(i,j)^k=\sum\limits_{t=1}^k \binom{dis(i,j)}{t} S2(k,t)* t!$ ，$S2$为第二类斯特林数

因此对每个点 我们只需要求出$\sum\limits_{t=1}^k \sum\limits_{i=1}^n C_{dis(x,i)}^t $

而组合数有一个很好的性质$C(n,m)=C(n-1,m)+C(n-1,m-1)$

这样我们$dp$，$f(x,j)$表示子树内的$\sum C_{dis(x,v)}^j$按照组合数的性质很容易合并

然后我们再从上面继承其父亲子树外的点的与子树一样，考虑与它同级的其他点，用父亲的$f$减去之前用自己转移出的$fa$即可

即$g(x,i)+=f(fa,i)+f(fa,i-1)-f(x,i)-f(x,i-1)-f(x,i-1)-f(x,i-2)$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define ll long long
#define db double
#define inf 2139062143
#define MAXN 50100
#define MOD 10007
#define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
#define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
#define ren for(register int i=fst[x];i;i=nxt[i])
#define pb(i,x) vec[i].push_back(x)
#define pls(a,b) (a+b)%MOD
#define mns(a,b) ((a-(b))%MOD+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,L,las,A,B,Q,nxt[MAXN<<1],to[MAXN<<1],fst[MAXN],cnt;
int s[155][155],fac[155],f[MAXN][155],g[MAXN][155];
void add(int u,int v){nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
void dfs(int x,int pa)
{
    f[x][0]=1;ren if(to[i]^pa) {dfs(to[i],x);
        rep(j,0,m) f[x][j]=pls(f[x][j],f[to[i]][j]+(j?f[to[i]][j-1]:0));}
}
void Dfs(int x,int pa)
{
    g[x][0]=n-f[x][0];rep(i,1,m) g[x][i]=mns(g[pa][i]+g[pa][i-1]+f[pa][i]+f[pa][i-1],
        f[x][i]+f[x][i-1]*2+(i>1?f[x][i-2]:0));
    ren if(to[i]^pa) Dfs(to[i],x);
}
int main()
{
    n=read(),m=read(),L=read(),las=read(),A=read(),B=read(),Q=read();int a,b,x;
    rep(i,2,n) las=(las*A+B)%Q,a=i-1-las%min(i-1,L),b=i,add(a,b),add(b,a);
    s[1][1]=fac[1]=1;dfs(1,0);x=1;ren Dfs(to[i],x);int ans=0;
    rep(i,2,m) {rep(j,1,i) s[i][j]=pls(s[i-1][j-1],j*s[i-1][j]);fac[i]=mul(fac[i-1],i);}
    rep(i,1,n)
    {
        ans=0;rep(j,1,m) ans=pls(ans,mul(mul(fac[j],s[m][j]),f[i][j]+g[i][j]));
        printf("%d\n",ans);
    }
}