[国家集训队2011]Crash的文明世界 …

题目:

Crash小朋友最近迷上了一款游戏——文明5(CivilizationV)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。

现在Crash已经拥有了一个N个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此Crash只修建了N-1条道路连接这些城市,不过可以保证任意两个城市都有路径相通。

在游戏中,Crash需要选择一个城市作为他的国家的首都,选择首都需要考虑很多指标,有一个指标是这样的:



其中S(i)表示第i个城市的指标值,dist(i,j)表示第i个城市到第j个城市需要经过的道路条数的最小值,k为一个常数且为正整数。

因此Crash交给你一个简单的任务:给出城市之间的道路,对于每个城市,输出这个城市的指标值,由于指标值可能会很大,所以你只需要输出这个数mod10007的值。


分析:
出题人的解法是树分治,不过在网上能找到一篇神奇的题解:

这篇题解是基于第二类斯特林(Stirling)数的。我们先来看一下这个“第二类斯特林数”到底是什么东西。

Wiki的定义:“第二类斯特林数是n个元素的集定义k个等价类的方案数”。
什么意思呢?它是这样的一个函数S(n,k),代表将n个人分成k组(组之间不可区分)的方案数。也可以理解为,将n个不同的小球放入k个相同的盒子,要求所有盒子非空的方案数。

斯特林数有一个递推公式:S(n,k)=S(n-1,k-1)+k*S(n-1,k)。边界条件S(n,1)=S(n,n)=1.
边界条件很好理解:n个小球放进一个盒子只有一种方案,放进n个相同盒子(每个盒子非空)也只有一种方案,即每个球一个盒子。
那递推关系怎么理解呢?n个小球放入k个相同盒子,每个盒子非空,那么有两种可能:
①第n个小球单独占一个盒子,此时其余n-1个小球占k-1个盒子,方案数是S(n-1,k-1)
②第n个小球放进前面个某个盒子,那么其余n-1个小球必然占k个盒子,第n个球可以放进k个盒子中的任意一个,方案数是k*S(n-1,k)。

并且,斯特林数还有一个很好的性质:

其中的含义是n选m的排列数(即n(n-1)…(n-m+1))。
顺便插一句:排列数还有一种高端洋气的写法:

(那篇题解中就是这么写的,但他打不出来角标,就写成下划线了……)


那么,为什么它是对的?从组合数的意义考虑。
x^n的意义是:n个不同的小球放进x个不同的盒子,允许有空盒的方案数。(每个球都有x种放法)
我们关注等式右边的某一项:S(n,i)*P(x,i)。S(n,i)代表把n个不同小球放进i个相同的盒子,P(x,i)的意义则是:从1~x中有序地取出i个数,来给这i个盒子标号的方案数。
换句话说,S(n,i)*P(x,i)就是:n个不同小球放进x个不同的盒子,其中i个盒子非空的方案数。
自然,对i从1到n求和后就是x^n了。

斯特林数在这道题中有什么用呢?一个自然的想法是:对节点i,记录f[i][j]=∑P(dist(x,i),j),x=1..n。但这个方程难以递推。假设我们知道了g[i][j]=∑P(dist(x,i),j),x是i的后代,那么对于某节点v和其父亲u,有dist(x,u)=dist(x,v)+1,其中x是v的后代。但P(dist(x,u),j)难以快速和P(dist(x,v), j)即P(dist(x,u)-1 , j)建立关系。
但是!排列无法迅速建立关系,组合却可以!我们有公式C(n,m)=C(n-1,m-1)+C(n-1,m)。

我们考虑把排列改成组合。设down[i][j]=∑C(dist(x,i),j),x是i的后代。在用u的某儿子v去更新u时,我们只需要让down[v]“走一步”(即在杨辉三角中向下移动一行),就能把v后代到v的结果变成u后代到u的结果。
在一遍DP出down后,再设f[i][j]=∑C(dist(x,i),j),x=1..n。它比down[i][j]多包含了i“上方”的那些节点。当我们用u去更新u的儿子v时,先让down[u]走一步,然后再减去down[v]走两步的结果,再加上down[v],就得到了f[v]。

代码:

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注