bzoj2159:Crash 的文明世界(树形DP+斯特林数)

题解

  套路题,GDOI2018就出了一道题面类似做法类似的…第一次做记录一下
  很多kk次方的题都是要用斯特林数拆成组合数来做的。
  斯二林有以下性质:

nk=i=1k{ki}×i!×(ni)n^k=\sum_{i=1}^k \begin{Bmatrix} k\\ i \end{Bmatrix}\times i!\times \binom{n}{i}

  证明不再赘述。
  用此性质可以将一个点ii的指标可以化为下式:

j=1ndisti,jm=k=1m{mk}×k!j=1n(disti,jk)\sum_{j=1}^n dist_{i, j}^m=\sum_{k=1}^m \begin{Bmatrix} m\\ k \end{Bmatrix}\times k!\sum_{j=1}^n\binom{dist_{i,j}}{k}

  等式右边第二个求和可以用树形DP求得。
  令fi,jf_{i,j}ii子树内的点的贡献,则有:

fi,j=fson,j+fson,j1f_{i,j}=f_{son,j}+f_{son, j-1}

  令gi,jg_{i,j}ii子树外的点的贡献,则有:

gi,j=gfa,j+gfa,j1gi,j=gi,j+(ffa,jfi,jfi,j1)gi,j=gi,j+(ffa,j1fi,j1fi,j2)\begin{gathered} g_{i,j}=g_{fa,j}+g_{fa,j-1}\\ g_{i,j}=g_{i,j}+(f_{fa,j}-f_{i,j}-f_{i,j-1})\\ g_{i,j}=g_{i,j}+(f_{fa,j-1}-f_{i,j-1}-f_{i,j-2}) \end{gathered}

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define ll long long
#define MOD(x) ((x)>=mod?(x)-mod:(x))
using namespace std;
const int maxn=50010, maxk=160, mod=10007;
struct edge{int too, pre;}e[maxn<<1];
int n, m, L, now, A, B, Q, tot, x, y;
int last[maxn], f[maxn][maxk], g[maxn][maxk], s[maxn][maxk], fac[maxn];

inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline void add(int x, int y){e[++tot]=(edge){y, last[x]}; last[x]=tot;}

void dfs1(int x, int fa)
{
	f[x][0]=1;
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa) 
	{
		dfs1(too, x); f[x][0]+=f[too][0]; f[x][0]=MOD(f[x][0]);
		for(int j=1;j<=m;j++)
		f[x][j]+=MOD(f[too][j]+f[too][j-1]), f[x][j]=MOD(f[x][j]);
	}
}

void dfs2(int x, int fa)
{
	g[x][0]=n-f[x][0]; g[x][0]%=mod; g[x][0]=MOD(g[x][0]+mod);
	if(fa) 
	for(int j=1;j<=m;j++)
	{
		g[x][j]+=MOD(g[fa][j]+g[fa][j-1]); g[x][j]=MOD(g[x][j]);
		g[x][j]+=MOD(f[fa][j]+f[fa][j-1]); g[x][j]=MOD(g[x][j]);
		g[x][j]-=MOD(f[x][j]+MOD(f[x][j-1]<<1)); g[x][j]=MOD(g[x][j]+mod);
		if(j>1) g[x][j]-=f[x][j-2], g[x][j]=MOD(g[x][j]+mod);
	}
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa) dfs2(too, x);
}

int main()
{
	scanf("%d%d%d%d%d%d%d", &n, &m, &L, &now, &A, &B, &Q);
    for (int i=1;i<n;i++)
	{
        now=(now*A+B)%Q;
        int tmp=i<L?i:L;
        x=i-now%tmp; y=i+1;
        add(x, y); add(y, x);
    }
	s[0][0]=fac[0]=1;
	for(int i=1;i<=m;i++)
	{
		fac[i]=1ll*fac[i-1]*i%mod;
		for(int j=1;j<=i;j++) s[i][j]=(1ll*s[i-1][j]*j+s[i-1][j-1])%mod;
	}
	dfs1(1, 0); dfs2(1, 0);
	for(int i=1;i<=n;i++)
	{
		int ans=0;
		for(int j=1;j<=m;j++) 
		ans=(ans+1ll*s[m][j]*fac[j]%mod*MOD(f[i][j]+g[i][j]))%mod;
		printf("%d\n", ans);
	}
}