文章目录
- 题目
- 思路
- 代码
题目
思路
首先，我还是不会容斥，然后这道题爆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;
}