20251118【NOIP】模拟 C. 修建道路

· · 个人记录

20251118【NOIP】模拟 C. 修建道路

简化题意： 一棵树，任意加边，使新图恰有 k 个边双。对合法方案计数。

关键观察：

  1. 将所有割边断开，会形成恰好 k 个连通分量。
  2. 所有的割边都是原来的树边。

考虑结论 2 的证明：

所以可以转化，新问题为：

一棵树，选 k 个边作为割边，剩下的连通块加边使得连通块内不存在割边。对合法方案计数。

这个问题看起来还是很困难，因为我们无法对连通块内的合法方案数计数，所以考虑二项式反演。

二项式反演：

我有 n 个限制，为 \{ a_1,a_2,a_3,\dots \} 。

设 f_k 为恰好违反 k 个限制的方案数，g_k 为至少违反 k 个限制的方案数 。

有关系 g_k = \sum_{i=k}^{n} f_{i} * \binom{i}{k} ，即在 i 中选 k 个来满足。

回到原问题，我们使用二项式反演，将原问题转化为：

同时我们知道在一个大小为 siz 的树内任意加边多的方案数是 2^{\binom{siz}{2}-(siz-1)} ，含义就是总的边数是 \binom{siz}{2}，减去原来的树上的边，这些边任意。

所以如果我们知道了那些边被割掉，形成了一些大小为 siz_1,siz_2,siz_3,\dots,siz_k 的连通块，答案就是 \prod 2^{\binom{siz_i}{2}-(siz_i-1)}

所以可以树形 dp。

设 dp_{u,i,j} 表示现在在以 u 为根的子树内，子树大小为 i，钦定割掉 j 条边的方案数。

转移，考虑将 u 的儿子 v 转移到自己，u 子树内和 v 子树内的状态都被确定了，所以只用考虑 u 到 v 这条边是否割：

dp_{v,i_1,j_1}+dp_{u,i_2,j_2}* 2^{\binom{j_2}{2}-(j_2-1)}=dp_{u,i_1,j_1+j_2+1}

这是把当前这条边割去了，此时以 v 为根的连通块的大小就确定了，所以就可以统计贡献。

dp_{v,i_1,j_1}+dp_{u,i_2,j_2}=dp_{u,i_1+i_2,j_1+j_2}

此时是不割，继续向上递归。

这个复杂度是 O(n^4) 的(v子树大小固定，第二维不用枚举)，所以要优化。

考虑多项式，首先设 f_{u,i} = \sum_{j=0}^{\infty} dp_{u,i,j} x_j ，转移改写形式为

f_{u,i_1} \times f_{v,i_2} \times x \times 2^{\binom{i_2}{2}-(i_2-1)} = f_{u,i_1} f_{u,i_1} \times f_{v,i_2} = f_{u,i_1+i_2}

但复杂度并没有变化，注意到这个复杂度瓶颈在于遍历数组中的每一个数。，所以使用另一个公式：拉格朗日插值

根据这个，我们知道了只用 n+1 个点值就可以表示出来原来的 n 次多项式，所以我们将每一次的 dp 变成点值，即一个 dp_{u,i,j} ，这样一次转移只用，枚举前两维，所以是 O(n^2) 的，做 n 次是 O(n^3) 的。

然后就是板子，使用 O(n^3) 的高斯消元或 O(n^2) 的拉插还原多项式，在套一个二项式反演的板子。

代码（赵队的）：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int get() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int N = 705, P = 1e9 + 7, sgn[] = { 1ll, P - 1 };
int n, fac[N], inv[N], ans[N];
struct Edge { int v, nxt; } edge[N << 1];
int head[N], tot;
int f[N][N], sze[N], a[N][N], g[N], tmp[N], x, C[N][N];

int qpow(int x, int y) {
    int res = 1;
    while(y) res = res * ((y & 1)? x : 1) % P, x = x * x % P, y >>= 1;
    return res;
}

void add(int u, int v) { edge[++tot] = (Edge){ v, head[u] }, head[u] = tot; }
void inc(int &x, int y) { x = (x + y) % P; }
void dec(int &x, int y) { x = ((x - y) % P + P) % P; }
int S(int n) { return qpow(2, n * (n - 1) / 2 - (n - 1)); }

void init(int n) {
    fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % P;
    inv[n] = qpow(fac[n], P - 2);
    for(int i = n; i >= 1; i--) inv[i - 1] = inv[i] * i % P;
    for(int i = 1; i <= n; i++) g[i] = S(i);
    for(int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
    }
}

void dfs(int u, int lst) {
    f[u][1] = 1, sze[u] = 1;
    for(int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].v;
        if(v == lst) continue;
        dfs(v, u);
        for(int a = 1; a <= sze[u]; a++)
            for(int b = 1; b <= sze[v]; b++) {
                // 不连接
                inc(tmp[a], f[u][a] * f[v][b] % P * g[b] % P * x);
                // 连接
                inc(tmp[a + b], f[u][a] * f[v][b]); 
            }
        for(int i = 1; i <= sze[u] + sze[v]; i++) f[u][i] = tmp[i], tmp[i] = 0;
        sze[u] += sze[v]; 
    }
}

void Gauss_Jordan(int n) {
    for(int i = 1; i <= n; i++) {
        int mp = i;
        for(int j = i + 1; j <= n; j++) if(a[j][i] > a[mp][i]) mp = j;
        for(int j = 1; j <= n + 1; j++) swap(a[i][j], a[mp][j]);
        int t = qpow(a[i][i], P - 2);
        for(int j = 1; j <= n + 1; j++) a[i][j] = a[i][j] * t % P;
        for(int j = 1; j <= n; j++) {
            if(j == i || !a[j][i]) continue;
            int t = a[j][i];
            for(int k = 1; k <= n + 1; k++) dec(a[j][k], a[i][k] * t);
        } 
    }
}

main() {
    n = get();
    for(int i = 1, u, v; i < n; i++) 
        u = get(), v = get(), add(u, v), add(v, u);
    init(n);
    for(int i = 1; i <= n + 1; i++) {
        memset(f, 0, sizeof(f)), x = i;
        dfs(1, 0);
        for(int j = 1; j <= n; j++) inc(a[i][n + 2], f[1][j] * g[j] % P * x);
        for(int j = 1; j <= n + 1; j++) a[i][j] = qpow(x, j - 1);
    }
    Gauss_Jordan(n + 1);
    for(int i = 1; i <= n; i++) ans[i] = a[i + 1][n + 2];
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++) inc(ans[i], sgn[(j - i) & 1] * ans[j] % P * C[j - 1][i - 1]);
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
    return 0;
}

/*
3
1 2
1 3

*/