题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2159
使用公式：( n^{k} = sumlimits_{i=0}^{k} S(k,i) * i! * C_{n}^{i} )
所以维护 ( f[x][i] = sumlimits_{uin subtree[x],d=dist(x,u)} C_{d}^{i} )
然后利用 ( C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1} )，可以树形DP过程中维护(原来想着可以线段树维护矩阵来着，呵呵)。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int const xn=50005,xm=155,mod=10007; int n,m,hd[xn],ct,to[xn<<1],nxt[xn<<1],f[xn][xm],g[xm],t[xn][xm]; int ans[xn],s[xm][xm],jc[xm]; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return f?ret:-ret; } void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;} int upt(int x){while(x>=mod)x-=mod; while(x<0)x+=mod; return x;} void dfs(int x,int fa) { f[x][0]=1; for(int i=hd[x],u;i;i=nxt[i]) { if((u=to[i])==fa)continue; dfs(u,x); f[x][0]=upt(f[x][0]+f[u][0]); for(int k=1;k<=m;k++)f[x][k]=upt(f[x][k]+f[u][k]+f[u][k-1]); } } void dfsx(int x,int fa) { if(!fa)memcpy(t[x],f[x],sizeof f[x]); else { t[x][0]=upt(f[x][0]+g[0]); for(int k=1;k<=m;k++)t[x][k]=upt(f[x][k]+g[k]+g[k-1]);//sum of C(d,k) } for(int i=0;i<=m;i++) ans[x]=(ans[x]+(ll)s[m][i]*jc[i]%mod*t[x][i])%mod; for(int i=hd[x],u;i;i=nxt[i]) { if((u=to[i])==fa)continue; g[0]=upt(t[x][0]-f[u][0]); for(int k=1;k<=m;k++)g[k]=upt(t[x][k]-(f[u][k]+f[u][k-1])); dfsx(u,x); } } void init() { jc[0]=1; for(int i=1;i<=m;i++)jc[i]=(ll)jc[i-1]*i%mod; s[0][0]=1; for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) s[i][j]=upt(s[i-1][j-1]+j*s[i-1][j]); } int main() { n=rd(); m=rd(); int L=rd(); int now=rd(),A=rd(),B=rd(),Q=rd(); 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; add(x,y); add(y,x); } init(); dfs(1,0); dfsx(1,0); for(int i=1;i<=n;i++)printf("%d ",ans[i]); return 0; }
update(2018.12.16)
http://acm.hdu.edu.cn/showproblem.php?pid=4625
几乎是一模一样的题；
只是在子函数里传个数组，会莫名不对...还是开成全局的了...
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int const xn=5e4+5,xm=505,mod=10007; int n,k,hd[xn],ct,to[xn<<1],nxt[xn<<1],f[xn][xm],g[xm]; int jc[xm],s[xm][xm],ans[xn]; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return f?ret:-ret; } int upt(int x){while(x>=mod)x-=mod; while(x<0)x+=mod; return x;} void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;} void init() { int mx=500; jc[0]=1; for(int i=1;i<=mx;i++)jc[i]=(ll)jc[i-1]*i%mod; s[0][0]=1; for(int i=1;i<=mx;i++) for(int j=1;j<=i;j++) s[i][j]=(s[i-1][j-1]+(ll)s[i-1][j]*j)%mod; } void dfs(int x,int fa) { f[x][0]=1;// for(int i=hd[x],u;i;i=nxt[i]) { if((u=to[i])==fa)continue; dfs(u,x); for(int j=0;j<=k;j++)f[x][j]=upt(f[x][j]+f[u][j]+(j?f[u][j-1]:0)); } } /* void dfsx(int x,int fa,int *t) { if(fa)for(int i=k;i>=0;i--)t[i]=upt(t[i]+(i?t[i-1]:0)); for(int j=0;j<=k;j++) ans[x]=(ans[x]+(ll)s[k][j]*jc[j]%mod*(f[x][j]+t[j]))%mod; for(int i=hd[x],u;i;i=nxt[i]) { if((u=to[i])==fa)continue; for(int j=0;j<=k;j++)g[j]=upt(t[j]+f[x][j]-f[u][j]-(j?f[u][j-1]:0)); dfsx(u,x,g); } } */ int t[xn][xm]; void dfsx(int x,int fa) { if(!fa)memcpy(t[x],f[x],sizeof f[x]); else for(int j=0;j<=k;j++)t[x][j]=upt(f[x][j]+g[j]+(k?g[j-1]:0)); ans[x]=0; for(int i=0;i<=k;i++) ans[x]=(ans[x]+(ll)s[k][i]*jc[i]%mod*t[x][i])%mod; for(int i=hd[x],u;i;i=nxt[i]) { if((u=to[i])==fa)continue; for(int j=0;j<=k;j++)g[j]=upt(t[x][j]-(f[u][j]+(j?f[u][j-1]:0))); dfsx(u,x); } } int main() { int T=rd(); init(); while(T--) { ct=0; memset(hd,0,sizeof hd); memset(f,0,sizeof f); memset(g,0,sizeof g); n=rd(); k=rd(); for(int i=1,x,y;i<n;i++)x=rd(),y=rd(),add(x,y),add(y,x); dfs(1,0); dfsx(1,0); for(int i=1;i<=n;i++)printf("%d ",ans[i]); } return 0; }