「bzoj2159」Crash的文明世界 - 树形动规+自然数幂和/Stirling数 | Bill Yang's Blog

「bzoj2159」Crash的文明世界 - 树形动规+自然数幂和/Stirling数

题目大意

    Crash小朋友最近迷上了一款游戏——文明5(Civilization V)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。
    现在Crash已经拥有了一个$N$个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此Crash只修建了$N-1$条道路连接这些城市,不过可以保证任意两个城市都有路径相通。
    在游戏中,Crash需要选择一个城市作为他的国家的首都,选择首都需要考虑很多指标,有一个指标是这样的:

    其中$S(i)$表示第$i$个城市的指标值,$dist(i,j)$表示第$i$个城市到第$j$个城市需要经过的道路条数的最小值,$k$为一个常数且为正整数。
    因此Crash交给你一个简单的任务:给出城市之间的道路,对于每个城市,输出这个城市的指标值,由于指标值可能会很大,所以你只需要输出这个数$\bmod 10007$的值。


题目分析

一道结论题,如果不知道结论就只有写Fuck Fst Transform了。

其中${n \brace k}$表示第二类Stirling数,即将$n$个元素分为$k$个集合的方案数,$P_n^m$表示排列,从$n$个元素选出$m$个的方案数,即$n\cdot(n-1)\cdot(n-2)\cdots(n-m+1)$。

证明:
$x^k$表示给$k$个元素染色,每个元素有$x$种可染的不同颜色,合法的方案总数。
$P_x^i$表示在$x$种颜色中选出$i$种进行染色。
${k \brace i}$表示将相同颜色分到一个集合,$k$个元素的划分方案。
这样$P_x^i{k \brace i}$就表示给$k$个元素染色,共有$x$种可染的不同颜色,将其染成$i$种不同颜色的方案数。
显然,$P_x^i{k \brace i}$枚举一下$i$就和$x^k$等价了。
证毕。

因此,现在问题转化为了,求:

这样我们仍然不好做,因为排列没有明显的递推性质。
但排列可以转为组合数:

故问题转化为:

因为组合数有Pascal递推公式,因此我们设$Down[x,d]$表示$\sum_{j}\binom{dist(x,j)}{d}$,其中$j$是$x$的后代。
根据Pascal公式可以得到:

因此用一次从下至上的动规即可求出$Down$,再来一次从上往下的动规求出$Up$表示来自除子树外其他地方的$\sum_{j}\binom{dist(x,j)}d$。
注意$Up$要除开来自自己转移过的$Down$,那么$Up[i,k]+Down[i,k]$即可得到$\sum_jdist(i,j)^k$。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=50005,maxm=155,mod=10007;
int n,m,Down[maxn][maxm],Up[maxn][maxm],S[maxm][maxm],fac[maxm];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void TreeDp1(int Now,int fa) {
Down[Now][0]=1;
for(int Next:edges[Now]) {
if(Next==fa)continue;
TreeDp1(Next,Now);
Down[Now][0]+=Down[Next][0];
for(int k=1; k<=m; k++)Down[Now][k]=(Down[Now][k]+Down[Next][k]+Down[Next][k-1])%mod;
}
}
void TreeDp2(int Now,int fa) {
if(fa) {
Up[Now][0]=n-Down[Now][0];
for(int k=1; k<=m; k++) {
Up[Now][k]=(Up[Now][k]+Up[fa][k]+Up[fa][k-1]+Down[fa][k]+Down[fa][k-1]-Down[Now][k]-Down[Now][k-1]-Down[Now][k-1]-(k>1?Down[Now][k-2]:0))%mod;
Up[Now][k]=(Up[Now][k]+mod)%mod;
}
}
for(int Next:edges[Now]) {
if(Next==fa)continue;
TreeDp2(Next,Now);
}
}
int main() {
n=Get_Int();
m=Get_Int();
int L=Get_Int(),now=Get_Int(),A=Get_Int(),B=Get_Int(),Q=Get_Int();
for(int i=1; i<n; i++) {
now=(now*A+B)%Q;
int tmp=i<L?i:L;
AddEdge(i-now%tmp,i+1);
AddEdge(i+1,i-now%tmp);
}
S[0][0]=fac[0]=1;
for(int i=1; i<=m; i++) {
fac[i]=fac[i-1]*i%mod;
for(int j=1; j<=i; j++)S[i][j]=(S[i-1][j]*j%mod+S[i-1][j-1])%mod;
}
TreeDp1(1,0);
TreeDp2(1,0);
for(int i=1; i<=n; i++) {
int ans=0;
for(int k=1; k<=m; k++)ans=(ans+S[m][k]*fac[k]%mod*(Up[i][k]+Down[i][k])%mod)%mod;
printf("%d\n",ans);
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%