这个题非常巧妙啊~
#include <bits/stdc++.h>
#define M 170
#define N 50003
#define mod 10007
#define LL long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
inline int qpow(int x,int y)
{
int tmp=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) tmp=1ll*tmp*x%mod;
return tmp;
}
int n,edges,K;
int fac[N],inv[N],g[N][M],tmp[M],hd[N],to[N<<1],nex[N<<1],S[M][M],f[N][M];
inline void addedge(int u,int v) { nex[++edges]=hd[u],hd[u]=edges,to[edges]=v; }
void dfs1(int u,int ff)
{
f[u][0]=1;
for(int i=hd[u];i;i=nex[i])
{
int v=to[i]; if(v==ff) continue;
dfs1(v,u);
for(int j=0;j<=K;++j) f[u][j]=(f[u][j]+f[v][j])%mod;
for(int j=1;j<=K;++j) f[u][j]=(f[u][j]+f[v][j-1])%mod;
}
}
void dfs2(int u,int ff)
{
for(int j=0;j<=K;++j) g[u][j]=f[u][j];
if(ff)
{
for(int j=0;j<=K;++j) tmp[j]=g[ff][j];
for(int j=0;j<=K;++j) tmp[j]=(tmp[j]+mod-f[u][j])%mod;
for(int j=1;j<=K;++j) tmp[j]=(tmp[j]+mod-f[u][j-1])%mod;
for(int j=0;j<=K;++j) g[u][j]=(g[u][j]+tmp[j])%mod;
for(int j=1;j<=K;++j) g[u][j]=(g[u][j]+tmp[j-1])%mod;
}
for(int i=hd[u];i;i=nex[i]) if(to[i]!=ff) dfs2(to[i],u);
}
inline void Read()
{
int L,now,A,B,Q;
scanf("%d%d%d%d%d%d%d",&n,&K,&L,&now,&A,&B,&Q);
for(int i=1;i<n;i++)
{
now=(now*A+B)%Q;
int tmp=i<L?i:L;
int x=i-now%tmp,y=i+1;
addedge(x,y),addedge(y,x);
}
}
int main()
{
// setIO("input");
int i,j;
Read();
S[0][0]=fac[0]=1;
for(i=1;i<=K;++i) fac[i]=1ll*fac[i-1]*i%mod;
for(i=1;i<=K;++i) for(j=1;j<=i;++j) S[i][j]=(S[i-1][j-1]+1ll*j*S[i-1][j])%mod;
dfs1(1,0),dfs2(1,0);
for(i=1;i<=n;++i)
{
int ans=0;
for(j=0;j<=K;++j) ans=(ans+1ll*S[K][j]*fac[j]%mod*g[i][j]%mod)%mod;
printf("%d\n",ans);
}
return 0;
}BZOJ 2159: Crash 的文明世界 第二类斯特林数+树形dp
原文：https://www.cnblogs.com/guangheli/p/11895523.html