[BZOJ2159]Crash 的文明世界-Stirling数-动态规划

比眉伴天荒 2021-11-09 11:42 260阅读 0赞

**Crash 的文明世界**

**Description**

**Crash 小朋友最近迷上了一款游戏——文明5(Civilization V)。在这个游戏中，玩家可以建立和发展自己的国家，通过外交和别的国家交流，或是通过战争征服别的国家。现在Crash 已经拥有了一个N 个城市的国家，这些城市之间通过道路相连。由于建设道路是有花费的，因此Crash 只修建了N-1 条道路连接这些城市，不过可以保证任意两个城市都有路径相通。在游戏中，Crash 需要选择一个城市作为他的国家的首都，选择首都需要考虑很多指标，有一个指标是这样的：**   
  
**其中S(i)表示第i 个城市的指标值，dist(i, j)表示第i 个城市到第j 个城市需要经过的道路条数的最小值，k 为一个常数且为正整数。因此Crash 交给你一个简单的任务：给出城市之间的道路，对于每个城市，输出这个城市的指标值，由于指标值可能会很大，所以你只需要输出这个数mod 10007 的值。**

**Input**

**输入的第一行包括两个正整数N 和k。下面有N-1 行，每行两个正整数u、v (1 ≤ u, v ≤ N)，表示第u 个城市和第v 个城市之间有道路相连。这些道路保证能符合题目的要求。**

**Output**

**输出共N 行，每行一个正整数，第i 行的正整数表示第i 个城市的指标值 mod 10007 的值。**

**Sample Input**

**5 2**   
**1 2**   
**1 3**   
**2 4**   
**2 5**

**Sample Output**

**10**   
**7**   
**23**   
**18**   
**18**

**HINT**

**20%的数据满足N ≤ 5000、k ≤ 30。**   
**50%的数据满足N ≤ 50000、k ≤ 30。**   
**100%的数据满足N ≤ 50000、k ≤ 150。**

**【特别注意】由于数据大小限制为5MB，我只好对测试时的输入文件进行压缩处理。下面的函数可以将压缩的输入文件转化为原始输入文件。（函数从infile 中读入压缩的输入文件，将解压缩后的输入文件输出到outfile 中）**

--------------------

**将题目中的式子用第二类斯特林数以下降幂的形式展开**

**会出现sigma（ C(dis(u,i), j )的形式**

**然后就是可以通过树形dp来统计这个东西，这里用到的组合数的递推式子**

**这个题目很巧妙，边权可以看成1，所以可以从相邻的点转移过来。**

**进行dp求sigma的时候，要进经两次，一次子树的和子树外的**

**统计子树外的时候注意减去多的贡献**

--------------------

1 #include<bits/stdc++.h> 2 using namespace std; 3 4 inline int read() 5 { 6 int x=0;char ch=getchar(); 7 while(ch<'0' || '9'<ch)ch=getchar(); 8 while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar(); 9 return x; 10 } 11 12 const int N=50009; 13 const int K=159; 14 const int md=10007; 15 16 int n,k; 17 int to[N<<1],nxt[N<<1],beg[N],tot; 18 int fa[N],siz[N],f[N][K],g[N][K]; 19 int s[K][K],fac[K]; 20 21 inline void adde(int u,int v) 22 { 23 to[++tot]=v; 24 nxt[tot]=beg[u]; 25 beg[u]=tot; 26 } 27 28 inline void add(int &a,int b) 29 { 30 if(b>=md)b-=md;a+=b;if(a>=md)a-=md; 31 } 32 33 inline void init() 34 { 35 s[0][0]=fac[0]=1; 36 for(int i=1;i<K;i++) 37 { 38 fac[i]=(long long)fac[i-1]*i%md; 39 s[i][0]=0;s[i][i]=1; 40 for(int j=1;j<i;j++) 41 s[i][j]=(j*s[i-1][j]%md+s[i-1][j-1])%md; 42 } 43 } 44 45 inline void normal() 46 { 47 n=read();k=read(); 48 for(int i=1,u,v;i<n;i++) 49 { 50 u=read();v=read(); 51 adde(u,v);adde(v,u); 52 } 53 } 54 55 inline void dfs(int u) 56 { 57 f[u][0]=1; 58 for(int i=beg[u];i;i=nxt[i]) 59 if(to[i]!=fa[u]) 60 { 61 fa[to[i]]=u; 62 dfs(to[i]); 63 for(int j=1;j<=k;j++) 64 add(f[u][j],f[to[i]][j-1]+f[to[i]][j]); 65 add(f[u][0],f[to[i]][0]); 66 } 67 } 68 69 inline void dfs2(int u) 70 { 71 g[u][0]=n-f[u][0]; 72 for(int i=beg[u],v;i;i=nxt[i]) 73 if((v=to[i])!=fa[u]) 74 { 75 for(int j=1;j<=k;j++) 76 { 77 add(g[v][j],((g[u][j-1]+g[u][j]+f[u][j]+f[u][j-1]-f[v][j]-f[v][j-1]*2)%md+md)%md); 78 if(j>=2)add(g[v][j],-f[v][j-2]+md); 79 } 80 dfs2(to[i]); 81 } 82 } 83 84 int main() 85 { 86 init(); 87 decompressed(); 88 dfs(1); 89 dfs2(1); 90 91 for(int i=1;i<=n;i++) 92 { 93 int ans=0; 94 for(int j=1;j<=k;j++) 95 add(ans,(long long)(g[i][j]+f[i][j])%md*fac[j]%md*s[k][j]%md); 96 printf("%d\n",ans); 97 } 98 99 return 0;

转载于:https://www.cnblogs.com/zhangbuang/p/10996634.html