【向盟约宣誓】(数学)

Description

求边数为奇数的边和边数为偶数的边的图的分数之差。

一个图的分数定义如下:

同一个联通块内的点颜色相同,$k$染色的方案数即为分数。

$n\leq k\leq 10^7$,$T\leq 10^5$

题目解析

好神啊!!! ——SunIsMe

首先我们将其转换为数学表达:

定义$T(e)$为满足$e$两端点颜色相等的方案

则有$Ans = \sum\limits_{S\subset E}(-1)^{|S|+1}\bigcap\limits_{e\in S}T(e)$

我们发现这其实是一个容斥的式子,最后的集合是满足任一$e$的方案的集合。

那么就相当于染色后使得至少两点颜色相同。

就有$Ans=k^n-A_k^n$

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注