以为是个什么 DS 题，原来还有这种操作？（似乎确实可以 DS 做）
以下 \(\mathrm{subtree}(p)\) 表示以 \(p\) 为根的子树中所有结点的集合，\(\mathrm{son}(p)\) 表示 \(p\) 的所有儿子的集合，\(\mathrm{fa}(p)\) 表示 \(p\) 的父亲。
根据第二类斯特林数的某些性质，有 \[ n^k = \sum\limits_{i=0}^k i! {k \brace i} \binom ni \]
故 \[ S(i) = \sum\limits_{e=0}^k e! {k \brace e} \sum\limits_{j=1}^n \binom{\mathrm{dist}(i,j)}e \]
主要问题在于如何算 \(\sum\limits_{j=1}^n \binom{\mathrm{dist}(i,j)}e\)。
考虑设 \[
\begin{aligned}
f_{u,e} &= \sum\limits_{v \in \mathrm{subtree}(u)} \binom{\mathrm{dist}(u,v)}e \\
g_{u,e} &= \sum\limits_{v \not \in \mathrm{subtree}(u)} \binom{\mathrm{dist}(u,v)}e
\end{aligned}
\]
看起来 \(f\) 更好做： \[ \begin{aligned} f_{u,e} &= \binom0e + \sum\limits_{v \in \mathrm{son}(u)} \sum\limits_{w \in \mathrm{subtree}(v)} \binom{\mathrm{dist}(v,w)+1}e \\ &= [e=0] + \sum\limits_{v \in \mathrm{son}(u)} \sum\limits_{w \in \mathrm{subtree}(v)} \left[\binom{\mathrm{dist}(v,w)}e + \binom{\mathrm{dist}(v,w)}{e-1}\right] \\ &= [e=0] + \sum\limits_{v \in \mathrm{son}(u)} (f_{v,e} + f_{v,e-1}) \end{aligned} \]
于是是 \(g\)： \[ \begin{aligned} g_{u,e} &= \sum\limits_{v \not \in \mathrm{subtree}(\mathrm{fa}(u))} \binom{\mathrm{dist}(\mathrm{fa}(u),v)+1}e + \sum\limits_{v \in \mathrm{subtree}(\mathrm{fa}(u))} \binom{\mathrm{dist}(\mathrm{fa}(u),v)+1}e - \sum\limits_{v \in \mathrm{subtree}(u)} \binom{\mathrm{dist}(u,v)+2}e \\ &= (g_{\mathrm{fa}(u),e} + g_{\mathrm{fa}(u),e-1}) + (f_{\mathrm{fa}(u),e} + f_{\mathrm{fa}(u),e-1}) - (f_{u,e} + 2f_{u,e-1} + f_{u,e-2}) \end{aligned} \]
然后就做完了鸭。
代码： 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
using namespace std;
const int N = 5e4;
const int K = 150;
const int mod = 10007;
int n,k;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5];
int S[K + 5][K + 5],fac[K + 5];
int f[N + 5][K + 5],g[N + 5][K + 5],ans;
void dfs1(int p)
{
f[p][0] = 1;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = p,dfs1(to[i]),f[p][0] = (f[p][0] + f[to[i]][0]) % mod;
for(register int j = 1;j <= K;++j)
f[p][j] = (f[p][j] + f[to[i]][j] + f[to[i]][j - 1]) % mod;
}
}
void dfs2(int p)
{
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
g[to[i]][0] = (g[p][0] + f[p][0] - f[to[i]][0] + mod) % mod;
g[to[i]][1] = (g[p][1] + g[p][0] + f[p][1] + f[p][0] - f[to[i]][1] - 2 * f[to[i]][0] + mod * 3) % mod;
for(register int j = 2;j <= K;++j)
g[to[i]][j] = (g[p][j] + g[p][j - 1] + f[p][j] + f[p][j - 1] - f[to[i]][j] - 2 * f[to[i]][j - 1] - f[to[i]][j - 2] + mod * 4) % mod;
dfs2(to[i]);
}
}
int main()
{
int L,now,A,B,Q,tmp,u,v;
scanf("%d%d%d",&n,&k,&L),fac[0] = S[0][0] = 1;
scanf("%d%d%d%d",&now,&A,&B,&Q);
for(register int i = 1;i <= k;++i)
fac[i] = fac[i - 1] * i % mod;
for(register int i = 1;i <= k;++i)
for(register int j = 1;j <= k;++j)
S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % mod;
for(register int i = 1;i < n;++i)
{
now = (now * A + B) % Q;
tmp = (i < L) ? i : L;
u = i - now % tmp,v = i + 1;
add(u,v),add(v,u);
}
dfs1(1),dfs2(1);
for(register int i = 1;i <= n;++i)
{
ans = 0;
for(register int j = 0;j <= k;++j)
ans = (ans + fac[j] * S[k][j] % mod * (f[i][j] + g[i][j]) % mod) % mod;
printf("%d\n",ans);
}
}