【每日一题 4.9】二分图染色（弱化版）

传送门戳我

Solution：

将完全二分图匹配问题转化为n*n棋盘的涂色问题，初始颜色都为绿色，在棋盘上选一些格子替换成红色或者绿色，同时任意一行任意一列不能同时出现红色或者蓝色。
1、首先我们先考虑只涂一种颜色的情况。
假设当前染了k条边，因为棋盘的对称性，可以选择k行，这部分的方案数为 ;
对于k列就不是组合而是排列了，这部分方案数为 ;
所以，n个点的完全二分图只连k条红色/蓝色边的方案数为f[k]= * 。
2、红蓝颜色都涂时，枚举红蓝边重复的边数x，根据容斥的思想可得 * f[n-x] * f[n-x]。最终的答案就是ans= * f[n-x] * f[n-x]
注意到f[n]需要 (n)的复杂度去计算，明显是会TLE的，所以考虑是否可以从n-1递推得到n：
（1）因为多了一行一列共2n-1个格子，加上不涂色，多了2n种方案
（2）考虑重复部分，由于对称性，这里考虑行（考虑列也是一样的），若选择的格子在前n-1行，那么这一行可能存在同一个格子被选了，有n-1种可能，就相当于(n-1) * (n-1)棋盘中可能出现重复的格子的位置，去掉了这一行一列后(n-2) * (n-2)棋盘就没有重复的了，重复的方案数就是(n-1) * (n-1) * f[n-2]。

Code:

#include <bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e7 + 5;
int inv[N],f[N],pre[N];
ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)    ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}
void init(int n) {
    pre[0]=1;
    for(int i=1;i<=n;++i) pre[i]=1ll*pre[i-1]*i%mod;
    inv[n]=qpow(pre[n],mod-2);
    for(int i=n-1;i>=0;--i)  inv[i]=1ll*inv[i+1]*(i+1)%mod;
    f[0]=1; f[1]=2;
    for(int i=2;i<=n;++i) {
        f[i]=2ll*i*f[i-1]%mod-1ll*f[i-2]*(i-1)%mod*(i-1)%mod;
        if(f[i]<0)   f[i]+=mod;
    }
}
ll C(int n,int m) {
    return 1ll*pre[n]*inv[m]%mod*inv[n-m]%mod;
}
ll A(int n,int m) {
    return 1ll*pre[n]*inv[n-m]%mod;
}
int n;
ll ans,flag;
int main() {
    js;
    cin>>n;
    init(n);
    for(int i=0;i<=n;++i) {
        if(i&1) flag=-1;
        else flag=1;
        ans+=flag*C(n,i)*A(n,i)%mod*f[n-i]%mod*f[n-i]%mod;
        ans%=mod;
    }
    if(ans<0)    ans+=mod;
    cout<<ans<<endl;
}