ACM在线编程训练 nc13229 二分图染色

95 阅读 0 评论 63 点赞

我是靠谱客的博主现代身影，这篇文章主要介绍ACM在线编程训练 nc13229 二分图染色，现在分享给大家，希望可以做个参考。

题目：

题目描述：

给定一个完全二分图，图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色，并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。

计算所有满足条件的染色的方案数，并对10^9+7取模。

(ps：本题数据量与实际比赛中数据量相比，少了一些)

输入描述：

二分图单边的顶点数目n(n ≤ 10^7)

输出描述：

输出一个整数,即所求的答案。

解析：

乍看之下，题目比较简单。可以将顶点相连的所有边看成是一个n * n矩阵中的点，横轴纵轴分别代表二分图两侧的点。对于某一点而言，其横轴和纵轴如果不存在红色（蓝色）的点则此点可以取红色（蓝色）的点，则此点可取红色（蓝色），利用递归的方式可以求解此题。但是这样做时间复杂度高，无法AC。

必须考虑别的解决方法。我们从简化的问题开始求解：假设，我们现在只有红色或者只有蓝色（绿色对于染色不构成影响所以不特别考虑）,此时答案是多少呢？

只填红色或者蓝色，显然有 $f[n] =sum_{i=0}^{n}c(n, i)*a(n, i)$ 种方案。
红蓝都有，枚举红蓝重复的边数x，根据容斥的思想那么答案就是 $c_{n}^{x}a_{n}^{x}f[n-x]*f[n-x]$ ，最终求和得到答案等于 $sum_{i=0}^{n}(-1)^{i}*c_{n}^{i}a_{n}^{i}*f[n-i]*f[n-i]$
分析时间复杂度的时候发现预处理阶乘和逆元都可以通过 $o(n)$ 搞定，不过按照我们上面的组合数×全排列的
方法时间复杂度是 $o(n^{2})$ ，这可就不好办。使用一个神奇的网站OEIS，将f[n]打表找规律2,7,34,209,1546,13327,130922...一查，果然有递推关系 $f[x]=2*x*f[x-1]-(x-1)^2*f[x-2]$ 。

Code：

利用Python编码，AC 40，问题再慢慢找吧

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import math
def C(n,m):
return math.factorial(n)//(math.factorial(n-m)*math.factorial(m))
if __name__ == '__main__':
semi_node_num = int(input())
ans = 0
f = [1, 2]
mod = int(1e9 + 7)
for i in range(2, semi_node_num + 1):
tmp = (2 * i * f[i - 1] % mod - (i - 1) * (i - 1) % mod * f[i - 2] % mod + mod) % mod
f.append(int(tmp))
pass
for i in range(semi_node_num + 1):
opt = -1 if i & 1 else 1
res = int(C(semi_node_num, i) * C(semi_node_num, i) % mod
* math.factorial(i) % mod * f[semi_node_num - i] % mod * f[semi_node_num - i] % mod)
ans = (ans + opt * res % mod + mod) % mod
pass
print(int(ans))