专栏文章

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

ZZnPdCo
P12495题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2gwha
此快照首次捕获于
2025/12/01 19:29
3 个月前
此快照最后确认于
2025/12/01 19:29
3 个月前
查看原文
考虑 原问题 怎么做：实际上是一个贪心，每次贪心选择最优的叶子节点，正确性可以使用 Exchange Argument 证明。上述贪心可以看作先对 TT 进行长链剖分，然后选择前 kk 长链，它们的长度和就是 ans(T,k)ans(T,k)。
长剖视角看起来更为容易来刻画这个问题。不妨就从长剖视角入手。
回想长剖，长剖的过程需要维护一个 dud_u 表示子树内最深的叶子节点到达 uu 的距离，即 max⁡x是u的后代dis(u,x)\max_{x 是 u 的后代} dis(u,x)。每次转移时会选择一个 dvd_v 最大的儿子，使得 du=dv+1d_u=d_v+1，然后 vv 在剖出来的链上的父亲就是 uu 了。这些都是众所周知的。
考虑这个过程有什么用，我们设 du=id_u=i 的有 sis_i 个，那么一种 s={s1,s2,⋯ ,sn}s=\{s_1,s_2,\cdots,s_n\} 是合法的（存在一种树 TT（nn 个点，11 为根）使得它剖分后的 dd 对应的 ss 是这个），当且仅当：
  • ∑s=n,si≥0\sum s=n,s_i\ge 0；
  • 最大的 upup 使得 sup>0s_{up}>0 的数满足 sup=1s_{up}=1；
  • ss 不增，即 si≥si+1s_i\ge s_{i+1}。
最后一条则是因为对于每个 du≠1d_{u}\neq 1，都需要找到至少一个对应的 vv 满足 dv=du−1d_v=d_u-1 当它的儿子。如果存在 si<si+1s_i<s_{i+1}，那么 du=id_{u}=i 的就不够分配给 du=i+1d_u=i+1 的了。
上面三条的必要性是显然的，充分性可以考虑使用构造证明。我们将 du=upd_u=up 的点作为根，然后后面依次将 du=id_u=i 的点接在 du=i+1d_u=i+1 上，只需要满足 du≠1d_u\neq 1 的点都有一个 dv=du−1d_v=d_u-1 的儿子就好了，因为 ss 不增，所以这是容易的。
我们发现 ss 的刻画过程似乎很适合我们 dp。这是因为我们的答案虽然是 dd 的前 kk 大之和，但也可以被刻画为 ∑imin⁡(si,k)\sum_i \min(s_i,k)，因为一个 du=id_u=i 必然会使得 s[1∼i]s[1\sim i] 都至少加一，总之这个就是很对，不好用语言表达，可以感受一下。所以说我们 dp 出来的 ss 可以算出答案。
考虑从 sns_n 到 s1s_1 通过 dp 逐一确认。设 fi,j,kf_{i,j,k} 表示当前计入了 si∼sns_i\sim s_n 的方案，且 si=js_i=j，∑x=insx=k\sum_{x=i}^n s_x=k。dp 转移则需要枚举 si−1=ls_{i-1}=l，那么我们的转移系数则需要一个 (n−kl)\binom{n-k}{l} 的组合数，乘上一个将 ll 个 du=i−1d_u=i-1 的点连向 du=id_u=i 的父亲的方案数。
我们先考虑怎么求这个系数，设 coefa,b,ccoef_{a,b,c} 表示 si−1=a,si=b,∑x=i+1nsx=cs_{i-1}=a,s_i=b,\sum_{x=i\textcolor{red}{+1}}^n s_x=c，对所有 d=i−1d=i-1 的点确认父亲的方案数。
确认父亲有几种选择，要么是选择一个 d=id=i 的父亲，要么选择一个 d>id>i 的父亲。但是要求每个 d=id=i 的父亲都有至少一个儿子。经典的容斥，设有 tt 个 d=id=i 的父亲没有儿子：
coefa,b,c=∑t=0b(−1)t(b+c−t)a(bt)coef_{a,b,c}=\sum_{t=0}^b (-1)^t(b+c-t)^a\binom{b}{t}
三个东西都是可以分开递推求的，那么我们猜测合在一起也可以递推求：
coefa,b,c=∑t=0b(−1)t(b+c−t)a(b−1t)+∑t=0b(−1)t(b+c−t)a(b−1t−1)=∑t=0b−1(−1)t((b−1)+(c+1)−t)a(b−1t)+∑t=1b(−1)t((b−1)+c−(t−1))a(b−1t−1)=∑t=0b−1(−1)t((b−1)+(c+1)−t)a(b−1t)−∑t=0b−1(−1)t((b−1)+c−t)a(b−1t)=coefa,b−1,c+1−coefa,b−1,c\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(n3)O(n^3) 内求出 coefcoef，已经足够快了。求出 coefcoef 后，就可以跑上述 dp 了。上述 dp 需要枚举一个 ii，范围是 O(n)O(n)；枚举一个 jj，是 O(ni)O(\frac{n}{i})；还有一个 kk，也是 O(n)O(n)；最后还有 ll，这个是 O(ni)O(\frac{n}{i})。
复杂度是 O(∑in(ni)2)=O(n3)O(\sum_{i}n(\frac{n}{i})^2)=O(n^3)。
但是用上述 dp 算答案似乎有一点困难，这是因为 sis_i 要和 kk 取 min⁡\min，取最小值并不好刻画。但是注意到 ss 是不增的，那么我们必然存在一个分界点 pp 使得 sp≤k,sp−1>ks_p\le k,s_{p-1}>k。再枚举 ∑s[p∼n]=j\sum s[p\sim n]=j，那么答案就是 j+(p−1)kj+(p-1)k。
但是这样的话我们需要再倒着做一遍 dp 求出前缀的情况。设 gi,j,kg_{i,j,k} 表示当前计入了 s1∼si−1s_1\sim s_{i-1} 的方案，且 si=js_i=j，∑x=insx=k\sum_{x=i}^n s_x=k。转移是类似的，写代码时乱写一下就会了。
最后枚举分界点 pp，将前后缀的答案相乘就可以算出答案和方案数了。然后注意这样算不了 s1≤ks_1\le k 的情况，但是没有关系，一种简单的处理方法是发现这种情况下答案必然等于 nn，也就是只会对方案数的最后一列产生影响。用 nn−2n^{n-2} 减去前面的结果赋值给最后一列即可。当然其他麻烦一点的解决方案也是存在的。
然后此时就可以做了，因为最后枚举分界点 pp 还需要枚举 si,si−1,∑s[i∼n]s_{i},s_{i-1},\sum s[i\sim n] 与 kk，朴素实现是 O(n4)O(n^4) 的，但是枚举 kk 可以改为打 tag，总之很容易对着代码优化到 O(n3)O(n^3)。
下面代码是 O(n4)O(n^4) 的，注释部分是 O(n3)O(n^3) 的：
CPP
// 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";
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...