ARC 105 106

· · 个人记录

E

有一个无向图，1,n 初始不连通。

A 和 B 轮流往上面加边，不能加重边自环。如果一个人加边之后 1,n 连通，他就输了。

谁会赢？

n,m\le 10^5

考察游戏结束前一步，显然形成了两个完全图，一个包含 1，一个包含 n。

假设这两个图分别有 A,n-A 个点，则总步数为 \binom n2-A(n-A)-m。

如果 n 是奇数，则上面的式子奇偶性只与 n,m 有关，直接判断。

否则，设 1,n 初始连通块大小奇偶性分别为 x,y。

如果 x,y 奇偶性不同，则先手胜，否则，与 xy 的奇偶性有关。

证明：复读题解 https://www.cnblogs.com/whx666/p/13971386.html#arc105e---keep-graph-disconnected2020-10-18

F

有一张无向图。所有边都是白色。

你可以对其做以下操作：

  • 选择一个点，反转其邻边的颜色。

如果能把所有边都变黑，则这张图是好的。

求有几个边的子图是好的。

n\le 17

结论：好，当且仅当是二分图。

如果是二分图，当然好。

如果好，考虑操作过哪些点，可以发现操作过的点和没操作过的点内部没有边，所以是二分图。

于是就是二分子图计数。

根据 有标号二分图计数 的套路，考虑先计数染色方案数，然后集合幂级数 ln。

对于一个点的子集，其染色方案数就是分为两部分，其间随意连边的方案数。

染色方案数子集卷积，O(2^nn^2)（当然 3^n 就能过）。

E

有一些人来上班，第 i 个人在第 j 天上班当且仅当 j\bmod 2a_i\le a_i-1。

每天，如果有人上班，你可以给上班的某个人（至多一个人）发 1 元钱。

至少要几天，所有人才能都至少得到 K 元钱？

n\le 18;K,a_i\le 10^5

将问题写为人和天之间的匹配问题。

建图，设有 D 天，左部 nK 个点表示人，右部 D 个点表示天，如果某个人在某天来了，就在天和人的所有点之间连边，则就是要这个图有左部的完美匹配。

使用 Hall 定理，问题转化为：对于任意人的子集 S，其邻集大小大于等于 |S|K。

二分 D，则只需要求出邻集大小，即这些人至少有一个来工作的天数。如果能求出“恰好是子集 X 来工作的天数”，则子集和变换一下即可。

如果 D 很小，枚举每一天就能算出“恰好是子集 X 来工作的天数”。但是 D 的范围是什么？

事实上，D\le 2nK（因为每个人至少来了一半的天！），因此直接暴力的复杂度就是 O((nK+2^nn)\log (nK)) 的。

F

给定权值 a_1\sim a_n。

对于所有 n 个点的有标号树，设 i 的度数为 d_i，求 \prod \dfrac{a_i!}{(a_i-d_i)!} 的和对 998244353 取模。

n\le 10^5

非常套路。

考虑 prufer 序列，如果在 prufer 序列中出现 k 次，则度数就是 k+1。

枚举每个数的出现次数：

\sum_{a_1+\dots+a_n=n-2}\dfrac{(n-2)!}{\prod a_i!}\prod \binom{A_i}{a_i+1}(a_i+1)! =(n-2)!\sum_{a_1+\dots+a_n=n-2}\prod \binom{A_i}{a_i+1}(a_i+1)

设 F_n(x)=\sum_{i\ge 0}\binom{A_n}{i+1}(i+1)x^i，则答案就是 F_n(x) 的积的第 n-2 位。

注意到

F_n(x)=\sum_{i\ge 0}\dfrac{A_n!}{i!(A_n-i-1)!}x^i =A_n\sum_{i\ge 0}\dfrac{(A_n-1)!}{i!(A_n-i-1)!}x^i =A_n(1+x)^{A_n-1}

所以答案为

(n-2)![x^{n-2}]\prod F_i(x) =(n-2)!\prod A_i[x^{n-2}](1+x)^{\sum (A_i-1)}

容易直接计算。