专栏文章

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

cchenzhiyv
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min4mo3h
此快照首次捕获于
2025/12/01 20:29
3 个月前
此快照最后确认于
2025/12/01 20:29
3 个月前
查看原文
20251118【NOIP】模拟 C. 修建道路
简化题意： 一棵树，任意加边，使新图恰有 kk 个边双。对合法方案计数。
关键观察：
  1. 将所有割边断开，会形成恰好 kk 个连通分量。
  2. 所有的割边都是原来的树边。
考虑结论 2 的证明：
  • 考虑新加入的边，一定不会有新割边产生，因为两个端点一定在原树上是连通的。
所以可以转化，新问题为：
一棵树，选 kk 个边作为割边，剩下的连通块加边使得连通块内不存在割边。对合法方案计数。
这个问题看起来还是很困难，因为我们无法对连通块内的合法方案数计数，所以考虑二项式反演。
二项式反演：
我有 nn 个限制，为 {a1,a2,a3,… }\{ a_1,a_2,a_3,\dots \}。
设 fkf_k 为恰好违反 kk 个限制的方案数，gkg_k 为至少违反 kk 个限制的方案数 。
有关系 gk=∑i=knfi∗(ik)g_k = \sum_{i=k}^{n} f_{i} * \binom{i}{k} ，即在 ii 中选 kk 个来满足。
回到原问题，我们使用二项式反演，将原问题转化为：
  • 一棵树，选 kk 个边作为割边，在剩下连通块里任意加边的方案数。
同时我们知道在一个大小为 sizsiz 的树内任意加边多的方案数是 2(siz2)−(siz−1)2^{\binom{siz}{2}-(siz-1)}，含义就是总的边数是 (siz2)\binom{siz}{2}，减去原来的树上的边，这些边任意。
所以如果我们知道了那些边被割掉，形成了一些大小为 siz1,siz2,siz3,…,sizksiz_1,siz_2,siz_3,\dots,siz_k 的连通块，答案就是 ∏2(sizi2)−(sizi−1)\prod 2^{\binom{siz_i}{2}-(siz_i-1)}
所以可以树形 dp。
设 dpu,i,jdp_{u,i,j} 表示现在在以 uu 为根的子树内，子树大小为 ii，钦定割掉 jj 条边的方案数。
转移，考虑将 uu 的儿子 vv 转移到自己，uu 子树内和 vv 子树内的状态都被确定了，所以只用考虑 uu 到 vv 这条边是否割：
dpv,i1,j1+dpu,i2,j2∗2(j22)−(j2−1)=dpu,i1,j1+j2+1dp_{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}
这是把当前这条边割去了，此时以 vv 为根的连通块的大小就确定了，所以就可以统计贡献。
dpv,i1,j1+dpu,i2,j2=dpu,i1+i2,j1+j2dp_{v,i_1,j_1}+dp_{u,i_2,j_2}=dp_{u,i_1+i_2,j_1+j_2}
此时是不割，继续向上递归。
这个复杂度是 O(n4)O(n^4) 的(vv子树大小固定，第二维不用枚举)，所以要优化。
考虑多项式，首先设 fu,i=∑j=0∞dpu,i,jxjf_{u,i} = \sum_{j=0}^{\infty} dp_{u,i,j} x_j ，转移改写形式为
fu,i1×fv,i2×x×2(i22)−(i2−1)=fu,i1f_{u,i_1} \times f_{v,i_2} \times x \times 2^{\binom{i_2}{2}-(i_2-1)} = f_{u,i_1} fu,i1×fv,i2=fu,i1+i2f_{u,i_1} \times f_{v,i_2} = f_{u,i_1+i_2}
但复杂度并没有变化，注意到这个复杂度瓶颈在于遍历数组中的每一个数。，所以使用另一个公式：拉格朗日插值
根据这个，我们知道了只用 n+1n+1 个点值就可以表示出来原来的 nn 次多项式，所以我们将每一次的 dp 变成点值，即一个 dpu,i,jdp_{u,i,j} ，这样一次转移只用，枚举前两维，所以是 O(n2)O(n^2) 的，做 nn 次是 O(n3)O(n^3) 的。
然后就是板子，使用 O(n3)O(n^3) 的高斯消元或 O(n2)O(n^2) 的拉插还原多项式，在套一个二项式反演的板子。
代码（赵队的）：
CPP
#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

*/

评论

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

正在加载评论...