NC13229 二分图染色(弱化版) （组合数学+容斥）

题意

给一个 $2n$ 个点的完全二分图（即有 $n^2$ 条边），每条边可以染红色，蓝色，绿色。一个点不能连出超过一条红色边，也不能连出超过一条蓝色边。问将这些边染色的方案数有多少种，答案对 $1e9+7$ 取模。( $n\leq 1e7$ )

分析

给这题跪了！我还是太菜了。
完全二分图可以转化为一个 $n*n$ 的矩阵，第 $i$ 行第 $j$ 列的点 $(i,j)$ 表示左边第 $i$ 个点和右边第 $j$ 个点。如果我们把染绿色看成不染色，这样子，问题可以转化为： $n*n$ 的矩阵，每个点可以染红色或蓝色，每一行每一列最多有一个红色，每一行每一列最多有一个蓝色。求涂色方案数。
同时有两种颜色很烦，要是能只考虑一种颜色就好了！我们不妨看看两种颜色的方案能不能由一种颜色的推过来。
设 $f_n$ 表示只有红色的方案数， $F_n$ 表示有红有蓝的方案数。
那么 $F_n=f_{n}^2$ 吗？
并不是，因为这样子一个点可能既涂了红色又涂了蓝色，我们要把它减掉。于是这就涉及容斥原理了。
我们设 $g_i$ 表示至少有特定的 $i$ 个点既涂了红色又涂了蓝色的方案数。
那么我们把这 $i$ 行 $i$ 列抽出来，剩下 $n-i$ 行和 $n-i$ 列可以随便涂，于是 $g_i=f_{n-i}^2$
这 $i$ 行 $i$ 列的选法有 $C_{n}^{i}A_n^{i}$ 种，于是我们得到容斥式： $F_n=\sum\limits_{i=0}^{n}(-1)^iC_{n}^{i}A_n^{i}f_{n-i}^2$ 。
这告诉了我们，只要得到一种颜色的涂法，就可以得到两种颜色的涂法！！！
于是我们接下来来看只有红色涂法的方案数 $f_n$ 怎么求。
有一个容易想的求法，就是选 $i$ 个点来涂色，即： $f_n=\sum\limits_{i=0}^{n}C_n^{i}A_n^{i}$
不过这样做必然 $gg$ ，因为复杂度是 $O(n^2)$ 的。
让我们看看多出来的这一行一列来涂色，总共有 $2n-1$ 个点。
这里盗一下邓老师的图！！！！
考虑只涂一个，即在最后一行或最后一列涂：
图片说明
不考虑重复的话（就是随便放），有 $2n-1$ 种涂法，再加上不涂，有 $2n$ 种涂法，总共是 $2*n*F_{n-1}$ 。
但是我们每涂一个，意味着那一行或那一列都不能再涂了，于是那一行有 $n-1$ 种重复方案（选一列来和重复），那么总共重复了 $(n-1)F_{n-1}$ 次，由于可以选 $n-1$ 行，所以有 $(n-1)^2F_{n-2}$ 次。每一列也可以进行同样的操作，于是涂一个的方案： $2(n-1)^2F_{n-2}$
考虑涂两个，即最后一行和最后一列都涂：
图片说明
那我们只用抽出那一行一列即可。方案数为 $(n-1)^2F_{n-2}$
于是我们把这些加起来，可以得到递推式： $F_n=2nF_{n-1}-(n-1)^2F_{n-2}$

总体评价

好难啊啊啊啊！！不过感谢邓老师让我学会这题！！

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 10000005
using namespace __gnu_pbds;
const int mod = 1e9 + 7;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int f[N], fac[N], inv[N], ans;
int C(int n, int m){
    return z * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int A(int n, int m){
    return z * fac[n] * inv[n - m] % mod;
}
int main(){
    int i, j, n, m;
    n = read();
    for(fac[0] = i = 1; i <= n; i++) fac[i] = z * fac[i - 1] * i % mod;
    inv[n] = ksm(fac[n], mod - 2, mod);
    for(i = n - 1; i >= 0; i--) inv[i] = z * inv[i + 1] * (i + 1) % mod;
    f[0] = 1, f[1] = 2;
    for(i = 2; i <= n; i++) f[i] = (z * 2 * i * f[i - 1] % mod - z * (i - 1) * (i - 1) % mod * f[i - 2] % mod) % mod;
    for(i = 0; i <= n; i++){
        if(i % 2) ans = (ans - z * C(n, i) * A(n, i) % mod * f[n - i] % mod * f[n - i] % mod) % mod;
        else ans = (ans + z * C(n, i) * A(n, i) % mod * f[n - i] % mod * f[n - i] % mod) % mod;
    }
    ans = (ans + mod) % mod;
    printf("%d", ans);
    return 0;
}