题目

题目描述:
给定一个完全二分图,图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。
计算所有满足条件的染色的方案数,并对10^9+7取模。
(ps:本题数据量与实际比赛中数据量相比,少了一些)
输入描述:
二分图单边的顶点数目n(n ≤ 10^7) 
输出描述:
 输出一个整数,即所求的答案。


解析

其实,我以前也没写过二分图的题目,在邓老师的提示下我稍微理解了
这道题我没学过的知识点挺多的,所以我现学了这些知识点:二分图乘法逆元容斥
除此之外这道题最重要的就是递推,递推可以减小时间复杂度到o(n)。
(ps:我们不将绿色算在颜色里面)
  1. 首先存储好二分图(详情看二分图专栏),因为二分图可以将结点分成两部分,所以我们二维数组存储
  2. 根据题目,我们现在可以知道,题目的意思就是在二维数组的同一行,同一列中不能同时出现红色和蓝色。
  3. 根据这个特点我们可以求出公式(原因下面补充)
  4. 但是如果为了缩短计算时间,所以我们要递推地求出F[i],可得(原因下面补充)。
  5. 最后按公式累加计算就行了。
那么是怎么推出来的呢?
染色结果公式:
  1. 只填一种颜色,当然就是单纯的排列组合就行了,先选i列放颜色,再排列:
  2. 两种颜色的话则要用到容斥了。按照容斥的思想假如边数为i。可以得到为:
  3. 所以求和的答案就是上面那个了。
F递推结果公式:
我其实不太会,邓老师是这样讲的
  1. 从n-1到n的时候,格子增加了一行一列一共2n-1个,如果我们在这些格子里面只放一个棋子进去,就有2n-1个方案,加上一个都不放的1种,就是2n种。
  2. 但是这样的方法里面会有矛盾出现,即我当前放的这一个和它所在行(如果是放在最后一列的话)、所在列(放在最后一行)的棋子矛盾,方案数是
  3. 还有放两个的情况:即在最后一行放一个,在最后一列也放一个,方案数为:
  4. 所以两种的情况减一下就是
  5. 求出得到


二分图

首先呢,这个二分图是图类中的一个特殊模型。
我们可以假设集合可以分成不相交的两个子集(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;
}