二分图染色

邓老师题解写的十分的好.
首先把完全二分图转化成一个二维的棋盘,因为完全二分图的连边可以把左边看成横坐标和右边看成纵坐标.如此题目就变成了,棋盘中同一横纵坐标不能存在相同颜色,且绿色根本不影响结果,我们不妨假设棋盘原本都是绿色,然后涂上红蓝两色...orz
我们不妨设f[n]是一种颜色满足要求的所有涂法.然后这个可以递推.邓老师讲了.那么我们直接上方程:

f[n]=f[n-1]*2*n-(n-1)*(n-1)*f[n-2];

然后根据容斥原理.邓老师也讲了.

是从i是从0到n.
然后ac代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e7+5;
ll f[N],ivf[N],n;//阶层及其逆元.
ll dp[N];//一种颜色填的方案数啦
ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void init()
{
    dp[0]=1;
    dp[1]=2;
    for(ll i=2;i<=n;i++)
    {
        dp[i]=(dp[i-1]*2ll*i%mod-(i-1)*(i-1)%mod*dp[i-2]%mod+mod)%mod;
    }
}

int main()
{
    scanf("%lld",&n);
    f[0]=1;
    for(int i=1;i<=N-5;i++) f[i]=f[i-1]*i%mod;
    ivf[N-5]=qp(f[N-5],mod-2);//倒数嘛.
    for(int i=N-6;i>=0;i--)
    {
        ivf[i]=ivf[i+1]*(i+1)%mod;
    }
    init();
    ll ans=0;
    ll x;
    //cout<<ivf[0]<<' '<<ivf[1]<<' '<<ivf[2]<<endl;
    for(int i=0;i<=n;i++)
    {
        if(i&1) x=-1;
        else    x=1;
        ans=(ans+x*f[n]*ivf[n-i]%mod*dp[n-i]%mod*dp[n-i]%mod*f[n]%mod*ivf[n-i]%mod*ivf[i]%mod+mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}