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

题目：

题目描述：

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

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

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

输入描述：

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

输出描述：

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

解析：

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

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

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

Code：

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

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))

最后

以上就是现代身影为你收集整理的ACM在线编程训练 nc13229 二分图染色的全部内容，希望文章能够帮你解决ACM在线编程训练 nc13229 二分图染色所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。