文章目錄
- 題目
- 思路
- 代碼
題目
思路
首先，我還是不會容斥，然後這道題爆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;
}