思维+容斥计数。
首先的转化比较妙，二分图转化为 \(n\times n\) 的网格图染色。
与网络流的转化方向相反，值得注意。
然后发现两种颜色（红、蓝）如果独立染色，同一个格子可能会重复染色。
考虑容斥，式子很好列，直接容斥即可。
\[ans=\sum\limits_{i=0}^n (-1)^n \times \binom{n}{i}^2\times i!\times g_{n-i}^2\\ g_n=\sum\limits_{i=0}^n \binom{n}{i}^2 \times i! \]发现 \(g\) 不是很好求，只能考虑组合意义递推。
\[g_n=2n\times g_{n-1}-(n-1)^2\times g_{n-2} \]前一项是考虑第 \(n\) 行和第 \(n\) 列选一个或不选的方案数。
后一项是减去算重的第 \(n\) 行和第 \(n\) 列各选一个的方案数。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e7+10,mod=1e9+7;
int n,g[N],fac[N],ifac[N];
ll qpow(ll x,ll y=mod-2){
ll ans=1;
for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
return ans;
}
void init(){
for(int i=fac[0]=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=qpow(fac[n]);
for(int i=n;i>=1;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
}
int C(int n,int m){
if(0>m||m>n)return 0;
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n,init();
g[0]=1,g[1]=2;
for(int i=2;i<=n;i++){
g[i]=(2ll*i*g[i-1]+(mod-i+1ll)*(i-1)%mod*g[i-2])%mod;
}
int ans=0;
for(int i=0;i<=n;i++){
int val=i&1?mod-1:1;
ans=(ans+1ll*val*fac[i]%mod*C(n,i)%mod*C(n,i)%mod*g[n-i]%mod*g[n-i])%mod;
}
cout<<ans;
return 0;
}