题目
题目描述:
给定一个完全二分图,图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。
输入描述: 计算所有满足条件的染色的方案数,并对10^9+7取模。
(ps:本题数据量与实际比赛中数据量相比,少了一些)
二分图单边的顶点数目n(n ≤ 10^7)
输出描述:
输出一个整数,即所求的答案。
解析
其实,我以前也没写过二分图的题目,在邓老师的提示下我稍微理解了
这道题我没学过的知识点挺多的,所以我现学了这些知识点:二分图,乘法逆元,容斥。
除此之外这道题最重要的就是递推,递推可以减小时间复杂度到o(n)。
(ps:我们不将绿色算在颜色里面)
- 首先存储好二分图(详情看二分图专栏),因为二分图可以将结点分成两部分,所以我们用二维数组存储。
- 根据题目,我们现在可以知道,题目的意思就是在二维数组的同一行,同一列中不能同时出现红色和蓝色。
- 根据这个特点我们可以求出公式(原因下面补充)
- 但是如果为了缩短计算时间,所以我们要递推地求出F[i],可得(原因下面补充)。
- 最后按公式累加计算就行了。
染色结果公式:
- 只填一种颜色,当然就是单纯的排列组合就行了,先选i列放颜色,再排列:。
- 两种颜色的话则要用到容斥了。按照容斥的思想假如边数为i。可以得到为:
- 所以求和的答案就是上面那个了。
F递推结果公式:
我其实不太会,邓老师是这样讲的
- 从n-1到n的时候,格子增加了一行一列一共2n-1个,如果我们在这些格子里面只放一个棋子进去,就有2n-1个方案,加上一个都不放的1种,就是2n种。
- 但是这样的方法里面会有矛盾出现,即我当前放的这一个和它所在行(如果是放在最后一列的话)、所在列(放在最后一行)的棋子矛盾,方案数是。
- 还有放两个的情况:即在最后一行放一个,在最后一列也放一个,方案数为:。
- 所以两种的情况减一下就是。
- 求出得到。
二分图
首先呢,这个二分图是图类中的一个特殊模型。
我们可以假设集合可以分成不相交的两个子集(U,V),U只和V中的元素有关系,V也只和U中的元素有关系。(如下图)
而完全二分图就更为特殊,说明(U,V)中U中每一个元素都于V中每一个元素有对应关系。V也与U中每一个元素有对应关系。(如下图)
而二分图由于结构特殊,可以分成两部分,所以用二维数组表示。
比如我们可以将行认为是U中的元素,列认为是V中的元素。或者说是,用U中的元素构成行,V中的元素构成列。
依照此法可以表示二分图之间的线性关系。
乘法逆元
首先是基础概念:乘法逆元(其实也可以认为就是倒数):如果ax≡1 (mod p),且gcd(a,p)=1(a与p互质),则称a关于模p的乘法逆元为x。
(最简单的乘法逆元可以说是ax≡1,所以x=1/a,x就是a的倒数。上面类似。)
这里我们要引入一个定理:费马小定理。
(以下先确定一个条件:mod = p)
- 假如a是一个整数,p是一个质数,可以得到。
根据这个定理我们又可以得到,又因为乘法逆元的定理是。
所以我们就可以简单的得到。
本题应用:
在递推的基础上可以先把n的阶层的乘法逆元求出来,这样只需要用到快速幂就行了
容斥
这个我也不会,没看懂,orz
AC代码
#include <iostream> using namespace std; typedef long long ll; #define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); const int MOD = 1e9 + 7; const int MAX = 1e7 + 7; ll F[MAX], Factorial[MAX], Inverse[MAX];//F[i]为二分图单边数量为i的答案,Factorial为取模后的阶层,Inverse[i]为阶层为i对应的乘法逆元 void init(ll n);//初始化F,Factorial,Inverse(递推) ll A(ll n, ll m);//求排列数 ll C(ll n, ll m);//求组合数 ll qpow(ll n, ll m);//快速幂 int main() { js; init(1e7); ll n; cin >> n; ll ans = 0; for (ll i = 0; i <= n; i++) { ll k = i & 1 ? -1 : 1; ans += k * C(n, i) * A(n, i) % MOD * F[n - i] % MOD * F[n - i] % MOD; ans %= MOD; } cout << (ans + MOD) % MOD << endl; return 0; } void init(ll n) { Factorial[0] = 1; for (ll i = 1; i <= n; i++) Factorial[i] = Factorial[i - 1] * i % MOD; //递推求阶层 Inverse[n] = qpow(Factorial[n], MOD - 2); for (ll i = n - 1; i >= 0; i--) Inverse[i] = Inverse[i + 1] * (i + 1) % MOD; //递推求逆元 F[0] = 1; F[1] = 2; for (ll i = 2; i <= n; i++) { F[i] = (2 * i * F[i - 1] - (i - 1) % MOD * (i - 1) % MOD * F[i - 2]) % MOD; F[i] = (F[i] + MOD) % MOD; } //递推求F } ll A(ll n, ll m) { return Factorial[n] * Inverse[n - m] % MOD; } ll C(ll n, ll m) { return Factorial[n] * Inverse[m] % MOD * Inverse[n - m] % MOD; } ll qpow(ll n, ll m) { ll mul = 1; while (m) { if (m & 1) mul = mul * n % MOD; m >>= 1; n = n * n % MOD; } return mul; }