题目

题目描述：
给定一个完全二分图，图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色，并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。
计算所有满足条件的染色的方案数，并对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;
}