省选集训[?/6]：Math

Sets Scores

输入 \(n,m\)，输出长为 \(n\) 的集合序列 \(\mathcal S\) 代价总和 \(s\bmod 998244353\)，满足：

• \(\forall 1 \le i \le n,\mathcal S_i\subseteq [1,m]\cap \Z\)。
• \(\forall 1 \le i < n,|\mathcal S_{i+1}-\mathcal S_{i}|=1\)，其中 \(S-T=(S \cup T) \backslash (S \cap T)\)。
• \(\mathcal S\) 的代价定义为 \(\displaystyle\prod _{i=1}^{m}\sum _{j=1}^{n} [i \in \mathcal S_j]\)

首先考虑合法的集合序列长成什么样。容易发现，相邻集合恰好有一个元素包含在一个集合中而不在另一集合中。

对应地，就有一个长为 \(n-1\)，元素 \(\in [1,m]\) 的操作序列与之一一对应。（将 \(\mathcal S_1\) 特殊对待）。

然后观察得到初始存在 \(i\) 与初始不存在 \(i\) 的代价之和为 \(n \times \prod_{j\neq i} \dots\)，所以对于任意操作序列来说，取所有 \(\mathcal S_1\) 总的代价均为 \(n^m\)，所以答案为 \(n^mm^{n-1}\)。\(n,m\le2\cdot 10^5\) 是和一位。

Priority Queue 2

给一个多重集 \(A\)，\(K\) 次添加一个 \(1\sim m\) 的数并在添加后删除其中第 \(X\) 小的数，求所有添数方案的最后元素总和之和。

\(n, m, K\le 2000, 1 \le X \le n+1, 1\le A_i \le m\)。

单次的代价是：

\[\sum _{i} A_i=\sum_{j}\sum_{i}[A_{i}\ge j]=\sum_{j}c_j \]

\(c_j\) 的变化：

• 加入一个数 \(x\)，若 \(j \le x\) 则 \(c_j \gets c_j +1\)。
• 删掉第 \(x\) 小的数，若 \(n-x+1 < c_j\)，\(c_j \gets c_j -1\)。

枚举 \(j\)：

• 枚举 \(+1\) 的次数 \(i\)，方案数是 \(\dbinom{n}{i}(m-j+1)^{i}(j-1)^{n-i}\)。
• 考虑 \(-1\)：
  • 若 \(c_j\) 最初 \(\le n-x+1\)，则 \(c_j\) 不会 \(-1\) 直到 \(c_j =n-x+1\) 后，每一次 \(+1\) 都要 \(-1\)，保持不变。
  • 若 \(c_j\) 最初 \(>n-x+1\)，则 \(c_j\) 会不断 \(-1\) 直到 \(c_j=n-x+1\)，保持不变。

所以答案可以写出来：

\[\sum _{j=1}^{m} \sum _{i=0}^{K}\binom{K}{i}(m-j+1)^{i}(j-1)^{K-i}p(c_j,i)\\ p(c,i)=\begin{cases} \min(c+i,n-X+1) & c \le n-X+1\\ \max(c+i-K,n-X+1) & c > n-X+1 \end{cases} \]

补充：Stirling 数（第二类）

\(\begin{Bmatrix} n \\ m\end{Bmatrix}\) 表示将有 \(n\) 个元素的集合划分为 \(m\) 个非空集合的方案数。

通项公式

\[\begin{Bmatrix}n \\ m\end{Bmatrix} = \dfrac{1}{m!}\sum _{i=0}^{m} (-1)^i\binom{m}{i}(m-i)^n \]

通过容斥容易得到。

幂转化

1. 普通幂：

   \[n^m=\sum_{k=0}^n \begin{Bmatrix}m \\ k\end{Bmatrix}n^{\underline k}=\sum_{k=0}^n \begin{Bmatrix}m \\ k\end{Bmatrix}\binom{n}{k}k! \]

   观察组合意义：\(n\) 个盒子，\(m\) 个球，互不相同，要求装球，盒子可以为空；从 \(n\) 个盒子中选出 \(k\) 个装小球，把 \(n\) 个小球划分为 \(k\) 组，方案分别为 \(\dbinom{n}{k}\) 和 \(\begin{Bmatrix}m \\ k\end{Bmatrix}\)，最终还需要区分盒子，所以乘上 \(k!\)。

2. 上升下降幂。先不写了

Crash 的文明世界

给定一棵树，\(n,k\)，对每个 \(i\) 求：

\[S(i)=\sum_{j=1}^n \mathrm{dist}(i,j)^k \]

树的边权为 \(1\)。\(n \le 5\cdot 10^4, k \le 150\)

考虑普通幂转化，以下简记 \(\mathrm{dist}(i,j)=d(i,j)\)：

\[\begin{aligned} S(x)&=\sum_{y=1}^n d(x,y)^k\\ &=\sum _{y=1}^n \sum_{i=0}^{k}\begin{Bmatrix}k \\ i\end{Bmatrix}\binom{d(x,y)}{i}i!\\ &=\sum_{i=0}^k\begin{Bmatrix}k \\ i\end{Bmatrix}i!\sum_{y=1}^n\binom{d(x,y)}{i}\\ &:=\sum_{i=0}^k\begin{Bmatrix}k \\ i\end{Bmatrix}i!f_{x,i} \end{aligned} \]

后面那一坨相当于从路径上的每条边选或不选，恰好选出 \(i\) 个的方案数。

以 \(x\) 为根跑树形 DP，再进行换根即可。

\[f_{x,i}=\sum_{\mathrm{fa}_y=x}(f_{y,i}+f_{y,i-1}) \]

Vladislav and a Great Legend

给你一棵有 \(n\) 个节点的树 \(T\)，\(n\) 个节点编号为 \(1\) 到 \(n\)。

对于 \(T\) 中每个非空的顶点的集合 \(X\)，令 \(f(X)\) 为包含 \(X\) 中每个节点的最小连通子树的最小边数，即虚树的大小。

再给你一个整数 \(k\)。你需要计算对于每一个顶点的集合 \(X\)，\((f(X))^k\) 之和，即：

\[\sum_{X\subseteq\{1,2,\dots,n\},X\neq\varnothing}(f(X))^k \]

回顾上一题的做法：

\[\begin{aligned} \mathrm{ans}&=\sum_{X\subseteq[n],X\neq\varnothing}f^k(X)\\ &=\sum_{X\subseteq[n],X\neq \varnothing}\sum_{i=0}^{k}\begin{Bmatrix}k \\ i\end{Bmatrix}\binom{f(X)}{i}i!\\ &=\sum_{i=0}^{k} \begin{Bmatrix}k \\ i\end{Bmatrix}i!\sum_{X\subseteq[n],X\neq \varnothing}\binom{f(X)}{i} \end{aligned} \]

\(\dbinom{f(X)}{i}\) 意义为在 \(f(X)\) 条边中取 \(i\) 条的方案数，所以虚树中每增加一条边都要考虑一下。

令 \(f_{u,i}\) 表示 \(u\) 子树内，至少有 \(1\) 个节点被选中，且考虑继续向上连子树的虚树取边方案数。

合并：

\[f_{u,i} \gets f_{u,i}+\sum _{j+k=i} (f_{u,j}+[j=0])(f_{v,k}+f_{v,k-1}) \]

背包转移即可。这里涉及到 \(\mathcal O(nk^2)\) 转移优化为 \(\mathcal O(nk)\) 转移的技巧。只需要稍微卡一下上下界就好了。

统计答案：

\[g_i\gets g_{i}+\sum _{j+k=i} f_{u,j}(f_{v,k}+f_{v,k-1})\\ \mathrm{ans}=\sum _{i=0}^{k} \begin{Bmatrix}k \\ i\end{Bmatrix}i!g_i \]

Enjoy Coding time

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, r, l) for (int i = r; i >= l; --i)
#define int long long
#define eb emplace_back
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define FRE(p) freopen(#p".in", "r", stdin), freopen(#p".out", "w", stdout)
using namespace std;
const int N = 1e5+5, M = 205, mod = 1e9+7;
inline void cadd(int& x, int y) {
    x = (x+y)%mod;
}
int n, k;
vector<int> G[N];
int g[M], f[N][M], h[M], sz[N];
void dfs(int x, int fa) {
    sz[x] = 1, f[x][0] = 1;
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs(y, x);
        memcpy(h, f[x], sizeof(h));
        for (int i = min(k, sz[x]); ~i; --i)
            for (int j = min(k-i, sz[y]); ~j; --j) {
                cadd(f[x][i+j+1], (h[i]+(i==0))*f[y][j]);
                cadd(f[x][i+j], (h[i]+(i==0))*f[y][j]);
                cadd(g[i+j+1], h[i]*f[y][j]);
                cadd(g[i+j], h[i]*f[y][j]);
            }
        sz[x] += sz[y];
    }
}
int S[M][M];
signed main() {
    FASTIO;
#ifdef LOCAL
    FRE(test);
#endif
    cin >> n >> k;
    rep(i, 0, k) {
        S[i][0] = i==0;
        rep(j, 1, i) S[i][j] = (S[i-1][j]*j+S[i-1][j-1])%mod;
    }
    rep(i, 2, n) {
        int u, v;
        cin >> u >> v;
        G[u].eb(v), G[v].eb(u);
    }
    dfs(1, 0);
    int fac = 1, ans = 0;
    rep(i, 0, k) {
        cadd(ans,fac*S[k][i]%mod*g[i]);
        fac = fac*(i+1)%mod;
    }
    cout << ans << '\n';
    return 0;
}