题解：P12495 [集训队互测 2024] 链覆盖

· · 题解

考虑 原问题 怎么做：实际上是一个贪心，每次贪心选择最优的叶子节点，正确性可以使用 Exchange Argument 证明。上述贪心可以看作先对 T 进行长链剖分，然后选择前 k 长链，它们的长度和就是 ans(T,k)。

长剖视角看起来更为容易来刻画这个问题。不妨就从长剖视角入手。

回想长剖，长剖的过程需要维护一个 d_u 表示子树内最深的叶子节点到达 u 的距离，即 \max_{x 是 u 的后代} dis(u,x)。每次转移时会选择一个 d_v 最大的儿子，使得 d_u=d_v+1，然后 v 在剖出来的链上的父亲就是 u 了。这些都是众所周知的。

考虑这个过程有什么用，我们设 d_u=i 的有 s_i 个，那么一种 s=\{s_1,s_2,\cdots,s_n\} 是合法的（存在一种树 T（n 个点，1 为根）使得它剖分后的 d 对应的 s 是这个），当且仅当：

最后一条则是因为对于每个 d_{u}\neq 1，都需要找到至少一个对应的 v 满足 d_v=d_u-1 当它的儿子。如果存在 s_i<s_{i+1}，那么 d_{u}=i 的就不够分配给 d_u=i+1 的了。

上面三条的必要性是显然的，充分性可以考虑使用构造证明。我们将 d_u=up 的点作为根，然后后面依次将 d_u=i 的点接在 d_u=i+1 上，只需要满足 d_u\neq 1 的点都有一个 d_v=d_u-1 的儿子就好了，因为 s 不增，所以这是容易的。

我们发现 s 的刻画过程似乎很适合我们 dp。这是因为我们的答案虽然是 d 的前 k 大之和，但也可以被刻画为 \sum_i \min(s_i,k)，因为一个 d_u=i 必然会使得 s[1\sim i] 都至少加一，总之这个就是很对，不好用语言表达，可以感受一下。所以说我们 dp 出来的 s 可以算出答案。

考虑从 s_n 到 s_1 通过 dp 逐一确认。设 f_{i,j,k} 表示当前计入了 s_i\sim s_n 的方案，且 s_i=j，\sum_{x=i}^n s_x=k。dp 转移则需要枚举 s_{i-1}=l，那么我们的转移系数则需要一个 \binom{n-k}{l} 的组合数，乘上一个将 l 个 d_u=i-1 的点连向 d_u=i 的父亲的方案数。

我们先考虑怎么求这个系数，设 coef_{a,b,c} 表示 s_{i-1}=a,s_i=b,\sum_{x=i\textcolor{red}{+1}}^n s_x=c，对所有 d=i-1 的点确认父亲的方案数。

确认父亲有几种选择，要么是选择一个 d=i 的父亲，要么选择一个 d>i 的父亲。但是要求每个 d=i 的父亲都有至少一个儿子。经典的容斥，设有 t 个 d=i 的父亲没有儿子：

coef_{a,b,c}=\sum_{t=0}^b (-1)^t(b+c-t)^a\binom{b}{t}

三个东西都是可以分开递推求的，那么我们猜测合在一起也可以递推求：

\begin{aligned} coef_{a,b,c}&=\sum_{t=0}^b (-1)^t(b+c-t)^a\binom{b-1}{t}+\sum_{t=0}^b (-1)^t(b+c-t)^a\binom{b-1}{t-1}\\ &=\sum_{t=0}^{b-1} (-1)^t((b-1)+(c+1)-t)^a\binom{b-1}{t}+\sum_{t=1}^b (-1)^t((b-1)+c-(t-1))^a\binom{b-1}{t-1}\\ &=\sum_{t=0}^{b-1} (-1)^t((b-1)+(c+1)-t)^a\binom{b-1}{t}-\sum_{t=0}^{b-1} (-1)^t((b-1)+c-t)^a\binom{b-1}{t}\\ &=coef_{a,b-1,c+1}-coef_{a,b-1,c} \end{aligned}

那么我们可以在 O(n^3) 内求出 coef，已经足够快了。求出 coef 后，就可以跑上述 dp 了。上述 dp 需要枚举一个 i，范围是 O(n)；枚举一个 j，是 O(\frac{n}{i})；还有一个 k，也是 O(n)；最后还有 l，这个是 O(\frac{n}{i})。

复杂度是 O(\sum_{i}n(\frac{n}{i})^2)=O(n^3)。

但是用上述 dp 算答案似乎有一点困难，这是因为 s_i 要和 k 取 \min，取最小值并不好刻画。但是注意到 s 是不增的，那么我们必然存在一个分界点 p 使得 s_p\le k,s_{p-1}>k。再枚举 \sum s[p\sim n]=j，那么答案就是 j+(p-1)k。

但是这样的话我们需要再倒着做一遍 dp 求出前缀的情况。设 g_{i,j,k} 表示当前计入了 s_1\sim s_{i-1} 的方案，且 s_i=j，\sum_{x=i}^n s_x=k。转移是类似的，写代码时乱写一下就会了。

最后枚举分界点 p，将前后缀的答案相乘就可以算出答案和方案数了。然后注意这样算不了 s_1\le k 的情况，但是没有关系，一种简单的处理方法是发现这种情况下答案必然等于 n，也就是只会对方案数的最后一列产生影响。用 n^{n-2} 减去前面的结果赋值给最后一列即可。当然其他麻烦一点的解决方案也是存在的。

然后此时就可以做了，因为最后枚举分界点 p 还需要枚举 s_{i},s_{i-1},\sum s[i\sim n] 与 k，朴素实现是 O(n^4) 的，但是枚举 k 可以改为打 tag，总之很容易对着代码优化到 O(n^3)。

下面代码是 O(n^4) 的，注释部分是 O(n^3) 的：

// https://www.luogu.com.cn/article/eadbop1r
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 310;
int P;
inline int add(int x, int y) { if (x + y >= P) return x + y - P; return x + y; }
inline int sub(int x, int y) { if (x - y < 0) return x - y + P; return x - y; }
inline int mul(int x, int y) { return 1LL * x * y % P; }
inline void Add(int& x, int y) { x = add(x, y); }
inline void Sub(int& x, int y) { x = sub(x, y); }
inline void Mul(int& x, int y) { x = mul(x, y); }
inline int qpow(int x, int y = P - 2) {
    int z = 1;
    while (y) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}
int n;
int C[N][N];
// coef[a][b][c] 表示有 a 个 d[u] = i（s[i]=a）, b 个 d[u] = i + 1, c 个 d[u] > i + 1
int coef[N][N][N];
// f 从大到小 dp,s[i] = j, sum s[i,n] = k,s[i,n]的权值和
int f[N][N][N];
// g 从小到大 dp,s[i] = j, sum s[i,n] = k,s[1,i)的权值和
int g[N][N][N];

int tag[N][N][N];
int ans[N][N];
int main() {
    freopen("counting.in", "r", stdin);
    freopen("counting.out", "w", stdout);
    cin >> n >> P;
    if (n == 1) {
        cout << "1" << "\n";
        return 0;
    }
    C[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
        }
    }
    for (int a = 0; a <= n; a++) {
        for (int c = 0; c <= n; c++) {
            coef[a][0][c] = qpow(c, a);
        }
        for (int b = 1; b <= a; b++) {
            for (int c = 0; c <= n; c++) {
                coef[a][b][c] = sub(coef[a][b - 1][c + 1], coef[a][b - 1][c]);
            }
        }
    }
    for (int i = n; i >= 1; i--) {
        // 处理 i=up，作为根的那个
        Add(f[i][1][1], 1);
        int n1 = n / (i + 1), n2 = n / i;
        for (int j = 0; j <= n1; j++) {
            for (int k = j; k <= n; k++) if (f[i + 1][j][k]) {
                // 枚举 s[i] 是什么
                for (int l = j; l <= n2 && l + k <= n; l++) {
                    Add(f[i][l][l + k], mul(f[i + 1][j][k], mul(coef[l][j][k - j], C[n - k][l])));
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        Add(g[1][i][n], 1);
    }
    for (int i = 2; i <= n; i++) {
        int n1 = n / (i - 1), n2 = n / i;
        for (int j = 0; j <= n1; j++) {
            for (int k = j; k <= n; k++) if (g[i - 1][j][k]) {
                // 枚举 s[i] 是什么
                for (int l = 0; l <= n2 && l <= j && l <= k - j; l++) {
                    Add(g[i][l][k - j], mul(g[i - 1][j][k], mul(coef[j][l][k - j - l], C[n - (k - j)][j])));
                }
            }
        }
    }
    // 枚举 s[i] <= k, s[i - 1] > k
    for (int i = 2; i <= n; i++) {
        // s[i] = a, s[i - 1] = b
        int n1 = n / i, n2 = n / (i - 1);
        for (int a = 1; a <= n1; a++) {
            for (int b = a + 1; b <= n2; b++) {
                // s[i, n] = j
                for (int j = a; j + b <= n; j++) {
                    int val = mul(mul(f[i][a][j], g[i - 1][b][j + b]), mul(coef[b][a][j - a], C[n - j][b]));
                    /*
                    // 对 ans[k][(i - 1) * k + j] 产生贡献
                    Add(tag[a][i - 1][j], val);
                    Sub(tag[b][i - 1][j], val);
                    */
                    // k in [a, b - 1]
                    for (int k = a; k < b; k++) if ((i - 1) * k + j <= n) {
                        Add(ans[k][(i - 1) * k + j], val);
                    }
                }
            }
        }
    }
    /*for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                Add(tag[i + 1][j][k], tag[i][j][k]);
                if (j * i + k <= n) Add(ans[i][j * i + k], tag[i][j][k]);
            }
        }
    }*/
    // 处理答案最后一列，用 n^{n-2} 减去
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j < n; j++) Add(sum, ans[i][j]);
        ans[i][n] = sub(qpow(n, n - 2), sum);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
}