解题：国家集训队 Crash 的文明世界

本文主要是介绍解题：国家集训队 Crash 的文明世界，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

这种套着高次幂的统计问题一般都要用到第二类斯特林数和自然数幂的关系：$a^k=\sum\limits_{i=0}^{k}S_k^iC_a^i*i!$

那么对于每个点$x$有：

$ans_x=\sum\limits_{i=0}^k S_{k}^i C_{\sum dis(x,j)}^i i!$

问题变成求$C_{\sum dis(x,j)}^i$，神仙告诉我们，这个东西要DP求

为什么要DP求？先往下看

那么就设$dp[i][k]$表示以i为根的子树里$C_{\sum dis(i,j)}^k$的值，$pd[i][k]$表示以$i$为根的子树外......的值

$dp$数组是符合我们常做的树形DP的思路的，先看这个

转移当然是从儿子合并啦：

$dp[i][k]=C_{\sum dis(i,j)}^k$

$=C_{\sum dis(son,j)+1}^k+[k==0]$

好，现在回答为什么要DP？因为根据组合数的性质$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$，这里可以直接转移

$=C_{\sum dis(son,j)}^k+C_{\sum dis(son,j)}^{k-1}+[k==0]$

$=dp[son][k]+dp[son][k-1]+[k==0]$

这样一来就可以从父亲往下转移求$pd$了，下面用$C'$表示从父亲转移过来时的组合数(区别于子树)

$dp[i][k]={C'}_{\sum dis(i,j)}^k$

$={C'}_{\sum dis(fth,j)+1}^k+C_{\sum dis(fth,j)+1}^k-C_{\sum dis(i,j)+1}^k$

爆拆一通得到：

$=pd[fth][k]+pd[fth][k-1]+dp[fth][k]+dp[fth][k-1]-dp[i][k]-2*dp[i][k-1]-dp[i][k-2]$

于是做完了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=50005,M=200,mod=10007;
 6 int n,k,t1,t2,cnt;
 7 int fac[N],inv[N],st2[M][M];
 8 int p[N],noww[2*N],goal[2*N];
 9 long long dp[N][M],pd[N][M];
10 void Add(long long &x,int y)
11 {
12     x+=y;
13     if(x>=mod) x-=mod;
14 }
15 int C(int n,int m)
16 {
17     return n<m?0:1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
18 }
19 int Qpow(int x,int k)
20 {
21     if(k==1) return x;
22     int tmp=Qpow(x,k/2);
23     return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;
24 }
25 void Link(int f,int t)
26 {
27     noww[++cnt]=p[f];
28     goal[cnt]=t,p[f]=cnt;
29     noww[++cnt]=p[t];
30     goal[cnt]=f,p[t]=cnt;
31 }
32 void Pre()
33 {
34     fac[0]=inv[0]=1,st2[0][0]=1;
35     for(int i=1;i<=k;i++)
36         for(int j=1;j<=k;j++)
37             st2[i][j]=(st2[i-1][j-1]+1ll*st2[i-1][j]*j%mod)%mod;
38     for(int i=1;i<=k;i++)
39         fac[i]=1ll*fac[i-1]*i%mod;
40     inv[k]=Qpow(fac[k],mod-2);
41     for(int i=k-1;i;i--)
42         inv[i]=1ll*inv[i+1]*(i+1)%mod;
43 }
44 void Gettre(int nde,int fth)
45 {
46     dp[nde][0]=1;
47     for(int i=p[nde],g;i;i=noww[i])
48         if(goal[i]!=fth)
49         {
50             Gettre(g=goal[i],nde);
51             Add(dp[nde][0],dp[g][0]);
52             for(int j=1;j<=k;j++)
53                 Add(dp[nde][j],(dp[g][j]+dp[g][j-1])%mod);
54         }
55 }
56 void Getanc(int nde,int fth)
57 {
58     if(nde!=1)
59     {
60         for(int i=0;i<=k;i++)
61         {
62             pd[nde][i]=pd[fth][i]+dp[fth][i]-dp[nde][i];
63             if(i>=1) pd[nde][i]+=pd[fth][i-1]+dp[fth][i-1]-2*dp[nde][i-1];
64             if(i>=2) pd[nde][i]-=dp[nde][i-2]; pd[nde][i]=(pd[nde][i]%mod+mod)%mod;
65         }
66     }
67     for(int i=p[nde];i;i=noww[i])
68         if(goal[i]!=fth) Getanc(goal[i],nde);
69 }
70 int main()
71 {
72     scanf("%d%d",&n,&k),Pre();
73     for(int i=1;i<n;i++)
74         scanf("%d%d",&t1,&t2),Link(t1,t2);
75     Gettre(1,0),Getanc(1,0);
76     for(int i=1;i<=n;i++)
77     {
78         long long ans=0;
79         for(int j=0;j<=k;j++)
80             Add(ans,1ll*st2[k][j]*fac[j]%mod*(dp[i][j]+pd[i][j])%mod);
81         printf("%lld\n",ans);
82     }
83     return 0;
84 }