题意:
给定一棵 \(n\) 个点的树和一个常数 \(k\) , 对于每个 \(i\) , 求
- \[\displaystyle S(i) = \sum _{j=1} ^ {n} \mathrm{dist}(i, j)^k\]
- \(n 50000, k 150\)
题解 :
先划划那个 \(S(i)\) 的式子
我们需要知道一个化 \(x^n(n \ge 0)\) 的东西 qwq
\[\displaystyle x^n=\sum_{k=0}^{n}\begin{Bmatrix} n \\ k \end{Bmatrix} x^{\underline k}=\sum _{k=0}^{n}(-1)^k \begin{Bmatrix} n \\ k \end{Bmatrix} {\overline x}\]
这个式子十分的有用, 可以转化很多幂指数的东西为斯特林数
\[\displaystyle S(i)=\sum _{j=1}^{n}\sum_{l=0}^{k}\begin{Bmatrix} k \\ l \end{Bmatrix} \mathrm{dist}(i,j)^{\underline l}\]
然后换个位置
\[\displaystyle S(i)=\sum_{l=0}^{k}\begin{Bmatrix} k \\ l \end{Bmatrix}\sum _{j=1}^{n} \mathrm{dist}(i,j)^{\underline l}\]
然后用一下组合数的一个定义式子:
- \[\displaystyle \binom n k = \frac{n!}{(n-k)!k!}=\frac{n^{\underline k}}{k!}\]
- \[\therefore \displaystyle n^{\underline k}=\binom n k k!\]
这也可以导出下降幂了
\[\displaystyle S(i)=\sum_{l=0}^{k}\begin{Bmatrix} k \\ l \end{Bmatrix} l!\sum _{j=1}^{n} \binom {\mathrm{dist}(i,j)} l\]
前面那一部分显然是稳定不变的, 我们就可以去维护第二部分啦
令 \[\displaystyle dp[i][l]=\sum _{j=1}^{n} \binom {\mathrm{dist}(i,j)} l\]
由于是组合数我们就可以直接套用它的一个递推式来转移了 (因为转移的时候, 所有 \(\mathrm{dist}(i,j)\) 同增减 \(1\) )
\[\displaystyle \binom n k = \binom {n-1} {k} + \binom {n-1} {k-1}\]
同样的, 就有 \(dp[i][l]=dp[j][l]+dp[j][l-1]\) 此处 \(j\) 是 \(i\) 的一个儿子 (这个递推式用来转移真的是巧妙啊 qwq)
然后我们要算两个 \(dp\) 值, 一个 \(f_{i,l}\) 统计子树的, 一个 \(g_{i,l}\) 统计子树外的
统计子树外的时候, 要先算父亲那过来的贡献, 然后再算兄弟的贡献
算兄弟的贡献可以用父亲贡献减掉自己的贡献 (见代码中分步写的 \(g_{i,j}\) 的转移) 而且要先转移, 再遍历
所以最后 \(O(nk)\) 个状态, \(O(1)\) 的转移, 总复杂度就是 \(\Theta(nk)\) .
那个解压输入直接拷贝了 Hany01 大佬的 qwq 不会写
代码:
- /**************************************************************
- Problem: 2159
- User: zjp_shadow
- Language: C++
- Result: Accepted
- Time:4156 ms
- Memory:67680 kb
- ****************************************************************/
- #include <bits/stdc++.h>
- #define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
- #define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i>= i##end; --i)
- #define Set(a, v) memset(a, v, sizeof(a))
- using namespace std;
- inline bool chkmin(int &a, int b) {return b <a ? a = b, 1 : 0;}
- inline bool chkmax(int &a, int b) {return b> a ? a = b, 1 : 0;}
- inline int read() {
- int x = 0, fh = 1; char ch = getchar();
- for (; !isdigit(ch); ch = getchar()) if (ch == -) fh = -1;
- for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
- return x * fh;
- }
- void File() {
- #ifdef zjp_shadow
- freopen ("2159.in", "r", stdin);
- freopen ("2159.out", "w", stdout);
- #endif
- }
- const int Mod = 10007, N = 50010;
- vector<int> G[N];
- int n, k, S[160][160];
- int fac[160];
- void Init(int maxn) {
- S[0][0] = 1; For (i, 1, maxn) { S[i][1] = 1; For (j, 1, i) S[i][j] = (j * S[i - 1][j] % Mod + S[i - 1][j - 1]) % Mod; }
- fac[0] = fac[1] = 1; For (i, 2, maxn) fac[i] = fac[i - 1] * i % Mod;
- }
- int f[N][160], sz[N];
- void Dfs1(int u, int fa) {
- f[u][0] = 1; sz[u] = 1;
- For (i, 0, G[u].size() - 1) {
- int v = G[u][i]; if (v == fa) continue ;
- Dfs1(v, u); sz[u] += sz[v];
- (f[u][0] += f[v][0]) %= Mod;
- For (j, 1, k) (f[u][j] += f[v][j] + f[v][j - 1]) %= Mod;
- }
- }
- int g[N][160];
- void Dfs2(int u, int fa) {
- g[u][0] = (n - sz[u]) % Mod;
- if (fa) {
- For (i, 1, k) {
- g[u][i] = g[fa][i] + g[fa][i - 1];
- g[u][i] += f[fa][i] - (f[u][i] + f[u][i - 1]);
- g[u][i] += f[fa][i - 1] - (f[u][i - 1] + (i> 1 ? f[u][i - 2] : 0));
- g[u][i] = (g[u][i] % Mod + Mod) % Mod;
- }
- }
- For (i, 0, G[u].size() - 1) { int v = G[u][i]; if (v == fa) continue ; Dfs2(v, u); }
- }
- int ans[N];
- inline void Input_Umcompress()
- {
- register int l, now, a, b, q, tmp, u, v;
- n = read(), k = read(), l = read(), now = read(), a = read(), b = read(), q = read();
- For(i, 1, n - 1)
- now = (now * a + b) % q, tmp = i < l ? i : l,
- u = i - now % tmp, v = i + 1, G[u].push_back(v), G[v].push_back(u);
- }
- int main () {
- File(); Init(150);
- Input_Umcompress();
- /*n = read(); k = read();
- For (i, 1, n - 1) {
- int u = read(), v = read();
- G[u].push_back(v);
- G[v].push_back(u);
- }*/
- Dfs1(1, 0); Dfs2(1, 0);
- For (i, 1, n) {
- For (l, 0, k)
- (ans[i] += S[k][l] * fac[l] % Mod * (f[i][l] + g[i][l]) % Mod) %= Mod;
- printf ("%d\n", ans[i]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2537624.html