二分图染色[容斥]

题目

思路

首先，我还是不会容斥，然后这道题爆0了
思路：可以看成可以转化为棋盘染色问题
相当于每一行/每一列同一种颜色只能放一个，并且格子颜色不能重复
然后考虑只有一种颜色的答案
显然为：
f n = ∑ i = 0 n ( n i ) 2 i ! f_n=\sum_{i=0}^n \binom{n}{i}^2i! fn​=i=0∑n​(in​)2i!
然后由于有两个颜色会算重，重复的时候就是重点，那么此时可以看作一种混合色
然后就可以容斥了：
总的方案数相当于：随便放-钦定重复一个+钦定重复两个-…
也就是：
∑ i = 0 n ( − 1 ) i ( n i ) 2 i ! f n − i 2 \sum_{i=0}^n (-1)^i\binom{n}{i}^2i!f^2_{n-i} i=0∑n​(−1)i(in​)2i!fn−i2​
前面是放混合色，后面是两个颜色随便放
这样是 O ( n 2 ) O(n^2) O(n2) 的复杂度
考虑递推 f f f
递推式为：
f n = 2 n f n − 1 − ( n − 1 ) 2 f n − 2 f_n=2nf_{n-1}-(n-1)^2f_{n-2} fn​=2nfn−1​−(n−1)2fn−2​
首先显然只能多放一个，那么就有 2 n − 1 2n-1 2n−1 个位置+不放有 2 n 2n 2n 种方法，又因为会算重，如图：

放右中时候下中在 f n − 1 f_{n-1} fn−1​ 中贡献，反过来同理有两倍贡献
然后枚举算重的是哪两个减去一倍贡献即可

代码

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<cctype>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read(){
	bool f=0;int x=0;char c=getchar();
	while(!isdigit(c)) f=(c=='-'),c=getchar();
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return !f?x:-x;
}
void print(int x){
	if(x<10){
		if(x<0) putchar('-'),x=-x;
		else{
			putchar('0'+x);
			return ;
		}
	}
	print(x/10);
	putchar('0'+x%10);
	return ;
}
#define fi first
#define se second
#define mp make_pair
const int MAXN=10000000;
const int INF=0x3f3f3f3f;
const int Mod=(int)(1e9+7);
int Sub(int x,int y){x-=y;return x<0?x+Mod:x;}
int Mul(LL x,int y){x*=y;return x>=Mod?x%Mod:x;}
int Add(int x,int y){x+=y;return x>=Mod?x-Mod:x;}
int Pow(int x,int y){
	int ret=1; 
	while(y){
		if(y&1) ret=Mul(ret,x);
		x=Mul(x,x),y>>=1;
	}
	return ret;
}
int f[MAXN+5],fac[MAXN+5],inv[MAXN+5];
int C(int n,int m){return Mul(fac[n],Mul(inv[m],inv[n-m]));}
int main(){
	//freopen("rgbgraph.in","r",stdin);
	//freopen("rgbgraph.out","w",stdout);
	fac[0]=1;
	for(int i=1;i<=MAXN;i++)
		fac[i]=Mul(fac[i-1],i);
	inv[MAXN]=Pow(fac[MAXN],Mod-2);
	for(int i=MAXN-1;i>=0;i--)
		inv[i]=Mul(inv[i+1],i+1);
	f[0]=1,f[1]=2;
	for(int i=2;i<=MAXN;i++){
		f[i]=Sub(Mul(Add(i,i),f[i-1]),Mul(Mul(i-1,i-1),f[i-2]));
	}
	int n=read(),ans=0;
	for(int i=0;i<=n;i++){
		int c=C(n,i);
		if(i&1) ans=Sub(ans,Mul(Mul(c,c),Mul(fac[i],Mul(f[n-i],f[n-i]))));
		else ans=Add(ans,Mul(Mul(c,c),Mul(fac[i],Mul(f[n-i],f[n-i]))));
	}
	printf("%d\n",ans);
	return 0;
}