【每日一题】二分图染色(弱化版)

1. 首先存储好二分图（详情看二分图专栏），因为二分图可以将结点分成两部分，所以我们用二维数组存储。
2. 根据题目，我们现在可以知道，题目的意思就是在二维数组的同一行，同一列中不能同时出现红色和蓝色。
3. 根据这个特点我们可以求出公式（原因下面补充）
4. 但是如果为了缩短计算时间，所以我们要递推地求出F[i]，可得（原因下面补充）。
5. 最后按公式累加计算就行了。

1. 只填一种颜色，当然就是单纯的排列组合就行了，先选i列放颜色，再排列：。
2. 两种颜色的话则要用到容斥了。按照容斥的思想假如边数为i。可以得到为：
3. 所以求和的答案就是上面那个了。

1. 从n-1到n的时候，格子增加了一行一列一共2n-1个，如果我们在这些格子里面只放一个棋子进去，就有2n-1个方案，加上一个都不放的1种，就是2n种。
2. 但是这样的方法里面会有矛盾出现，即我当前放的这一个和它所在行（如果是放在最后一列的话）、所在列（放在最后一行）的棋子矛盾，方案数是。
3. 还有放两个的情况：即在最后一行放一个，在最后一列也放一个,方案数为：。
   
4. 所以两种的情况减一下就是。
5. 求出得到。

• 假如a是一个整数，p是一个质数，可以得到。

根据这个定理我们又可以得到，又因为乘法逆元的定理是。

#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;
}