题目大意
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;
}
|
