2021 ICPC 沈阳 L.Perfect Matchings @ Wings            分类 ACM
发布于 星期五, 十一月 26 日, 2021 年
更新于 星期五, 十一月 26 日, 2021 年

题目

题意

从 $2n$ 个点的无向完全图中, 删除给定的 $2n - 1$ 条边, 且这些边是一棵树. 问剩下的图的完美匹配数是多少.

$1 \le n \le 2000$

题解

正难则反, 考虑求 “至少包含一条树边的完美匹配数”, 然后用完全图的完美匹配数相减.

无法直接数出 “至少包含一条树边的完美匹配数”, 所以这里考虑容斥. 如果能够求出包含树边 A 的完美匹配数, 包含树边 B 的完美匹配数, 包含树边 C 的完美匹配数… 包含树边 A 和 B 的完美匹配数, 包含树边 B 和 C 的完美匹配数, 包含树边 C 和 A 的完美匹配数… 包含树边 A, B, C 的完美匹配数… 这样就可以用容斥求出包含 A 或 B 或 C… 的完美匹配数, 即至少包含一条树边的完美匹配数了.

这样的话会有一个问题, 每条树边都得枚举, 复杂度会炸. 可以发现, 恰好包含一条树边, 无论是哪一条, 完美匹配数都是一样的. 进一步, 如果是恰好包含两条树边, 那么剩下来的点是可以随便连的, 而剩下来的点个数又是一样的, 所以, 无论选哪两条树边, 完美匹配数都是一样的. 那么我只要知道选择两条树边的方案有多少种, 然后乘以剩下来的点的匹配方案数, 就可以了. 推而广之, 现在的任务就是计算 “恰好选择k条树边的方案”.

这样问题就在树上了, 可以用树形背包解决这个问题.

设 $dp(u, i, 0/1)$ 表示以 $u$ 为根的子树中, 选择 $i$ 条边, 根是否在被选的某一条边上.

根据树形背包 $O(n^2)$ 的合并转移方式, 有方程:

$$tmp(i+j, 0) = tmp(i+j, 0) + dp(u, i, 0) \cdot (dp(v, j, 0) + dp(v, j, 1))$$

$dp(u, i, 0)$ 是当前已合并树的选择方案数, 根在当前以合并树中, 所以不能选上; $dp(v, j, 0/1)$ 是子树 $v$ 中选 $j$ 条边的选择方案数, $v$ 是否被选不影响, 因为不选 $(u, v)$ 这条边.

$$tmp(i+j, 1) = tmp(i+j, 1) + dp(u, i, 1) \cdot (dp(v, j, 0) + dp(v, j, 1))$$

上面这个方程是 $u$ 被已经合并的树中选了, 子树 $v$ 是否被选也不影响.

$$tmp(i+j+1, 1) = tmp(i+j+1, 1), dp(u, i, 0) \cdot dp(v, j, 0)$$

上面这个方程是选 $(u, v)$ 这条边, 所以结果会多出 $1$, 以及 $u$ 不能在已经合并的树中被选, $v$ 不能在子树中被选.

注意 $i(j)$ 枚举到 $\frac{sz}{2}$ 即可, 并且注意可以不选, 即需要枚举到 $0$.

接下来就是求 $2n$ 个点的完美匹配数了. 考虑递推. 设 $f(n)$ 为 $2n$ 个点的完美匹配数, 先把点标号, 拿出最大的那个来, 去和剩下的 $2n - 1$ 个点做一个匹配, 那么还剩下 $2n - 2 = 2(n-1)$ 个点, 这些点的完美匹配个数是 $f(n-1)$. 上面这个枚举方案正好把匹配方式枚举完, 没有遗漏也没有重复. 所以 $f(n) = (2n-1)f(n-1)$.

最后就可以求 “包含’所有k条树边的选择方案’的完美匹配数之和”(不知道怎么表达, 看之前的分析可能更好理解), 为 $(dp(rt, k, 0) + dp(rt, k, 1)) \cdot f(n-k)$. 当 $2 \mid k$ 时, 容斥系数为 $1$; 否则为 $-1$.

代码
int T, n, sz[MAXN<<1], dp[MAXN<<1][MAXN][2], f[MAXN], ans = 0, tmp[MAXN][2];
VI G[MAXN<<1];

void dfs(int u, int f) {
	sz[u] = 1;
	dp[u][0][0] = 1;
	for (int v : G[u]) if (v != f){
		dfs(v, u);
		for (int i = 0; i <= sz[u]/2 + sz[v]/2 + 1; i++)
			tmp[i][0] = tmp[i][1] = 0;
		for (int k = sz[u]/2; k >= 0; k--)
			for (int x = 0; x <= sz[v]/2; x++) {
				tmp[x+k][0] = pls(tmp[x+k][0], mult(dp[u][k][0], pls(dp[v][x][0], dp[v][x][1])));
				tmp[x+k][1] = pls(tmp[x+k][1], mult(dp[u][k][1], pls(dp[v][x][0], dp[v][x][1])));
				tmp[x+k+1][1] = pls(tmp[x+k+1][1], mult(dp[u][k][0], dp[v][x][0]));
			}
		sz[u] += sz[v];
		for (int i = 0; i <= sz[u]/2 + 1; i++)
			dp[u][i][0] = tmp[i][0], dp[u][i][1] = tmp[i][1];
	}
}

int main() {
	scanf("%d", &n);
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i < 2 * n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	dfs(1, 0);

	f[0] = 1;
	for (int i = 1; i <= n; i++)
		f[i] = mult(f[i-1], 2 * i - 1);
	for (int i = 0; i <= n; i++) {
		int k = i&1 ? -1 : 1;
		ans = pls(ans, mult(pls(dp[1][i][0], dp[1][i][1]), k * f[n-i]));
	}
	printf("%d\n", ans);
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星
  21. [2021 ICPC 沈阳 105名 真银尾]
  22. [2021 CCPC 哈尔滨 银牌]
  23. [2021 ICPC 南京 铜牌]

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch