bzoj 2159: Crash 的文明世界

又来做了一次。。
之前写得实在是太差了，这次写好点吧。。
这里介绍用斯特林数展开的方法
如果不会的可以先看看这里
我们知道$x^n={\sum }_{k=0}^{n}S(n,k)?k!?C(x,k)$
因此，如果想知道答案，其实就是要知道对于每一个$k$，$C(x,k)$的和
然后，你会发现，这题边权是1，这个很关键
我们知道组合数的性质$C_n^m=C_{n?1}^m+C_{n?1}^{m?1}$
因此，不难想到怎么求1的答案
我们对于每一个节点DP一个值$f[son][k]$，表示他子树里面所有点到他的$C(x,k)$的答案
那么不难得到$f[fa][k]=f[son][k]+f[son[k?1]$
就这么DP上去就可以得到1的答案了
然后再顺着DP下来，用父亲更新儿子的答案
也就是，先把儿子对父亲的贡献去掉，就相当于父亲的信息是儿子的子树了，用同样的方法转移即可

实现也很简单，时间复杂度$O(nk)$

因为没有看题。。特殊的读入不知道WA了很多发。。
CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int MOD=10007;
const int N=50005;
const int K=155;
struct qq
{
    int x,y,last;
}e[N*2];int num,last[N];
int n,k;
void init (int x,int y)	{
    num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;}
int S[N][K];
int f[N][K];//子树里面的答案
int JC[K];
void dfs (int x,int fa)
{
    f[x][0]=1;for (int u=last[x];u!=-1;u=e[u].last){
    int y=e[u].y;if (y==fa) continue;dfs(y,x);f[x][0]=(f[x][0]+f[y][0])%MOD;for (int i=1;i<=k;i++)	f[x][i]=(f[x][i]+f[y][i]+f[y][i-1])%MOD;}
}
int calc (int x)
{
    int lalal=0;for (int u=1;u<=k;u++)	lalal=(lalal+S[k][u]*JC[u]%MOD*f[x][u]%MOD)%MOD;return (lalal+MOD)%MOD;
}
int d[K];
void dfs1 (int x,int fa)
{
    for (int u=last[x];u!=-1;u=e[u].last){
    int y=e[u].y;if (y==fa) continue;d[0]=(f[x][0]-f[y][0])%MOD;for (int i=1;i<=k;i++) d[i]=(f[x][i]-f[y][i]-f[y][i-1])%MOD;f[y][0]=(f[y][0]+d[0])%MOD;for (int i=1;i<=k;i++)	f[y][i]=(f[y][i]+d[i]+d[i-1])%MOD;dfs1(y,x);}
}
int main()
{
    num=0;memset(last,-1,sizeof(last));int tL, tNOW, tA, tB, tC;scanf("%d%d",&n,&k);scanf("%d%d%d%d%d",&tL,&tNOW,&tA,&tB,&tC);for (int u=1;u<n;u++){
    int x,y;//scanf("%d%d",&x,&y);tNOW=(tNOW*tA+tB)%tC;x=u-tNOW%(u<tL?u:tL),y=u+1;init(x,y);init(y,x);}S[0][0]=1;for (int u=1;u<=k;u++)for (int i=1;i<=u;i++)S[u][i]=(S[u-1][i-1]+S[u-1][i]*i%MOD)%MOD;JC[0]=1;for (int u=1;u<=k;u++) JC[u]=JC[u-1]*u%MOD;dfs(1,0);dfs1(1,0);for (int u=1;u<=n;u++) printf("%d\n",calc(u));return 0;
}