题解：P13234 [GCJ 2015 Finals] Campinatorics
lzqy_
·
·
题解
小清新数数题，像是二维错排。
考虑只有 $1,2$ 怎么做，设答案为 $f_n$。
一个平凡的想法是从 $f_{n-1}$ 转移而来。我们钦定第 $n$ 行的第 $n$ 个数为 $1$，然后枚举第 $n$ 行 $2$ 的位置 $i$，然后将原本第 $i$ 列的 $2$ 放置到第 $n$ 列，这样我们就实现了一个 $f_{n-1}\rightarrow f_n$ 的映射，即
$$f_n=n\times (n-1)\times f_{n-1}$$
乘的 $n$ 是把钦定的最后一行放回到任意一行中。
然而这样存在漏数的情况。类比错拍的递推，上式默认了去掉特定的一行一列（第 $n$ 列有 $1$ 的行，该行有 $2$ 的列）后的矩阵依然合法，而则不总是存在。
考虑计算不存在的情况。容易发现，不存在当且仅当该特定的行列处于一个合法的 $2\times 2$ 矩阵中（这也和错排类似），这一部分的贡献是 $n\times (n-1)^2\times f_{n-2}$。
最后再处理 $3$ 的影响即可。
时间复杂度 $O(Tn)$。
```cpp
#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N=1000000;
const int maxn=1000010;
const int mod=1e9+7;
il int read(){
int x=0;
char c=getchar();
for(;!(c>='0'&&c<='9');c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+c-'0';
return x;
}
il int fpow(int n,int m,int x=1){
for(;m;m>>=1,n=1ll*n*n%mod)
if(m&1) x=1ll*x*n%mod;
return x;
}
int fac[maxn],ifac[maxn];
int f[maxn],T,n,X,ans;
int C(int i){return (1ll*i*(i-1)/2)%mod;}
int main(){
fac[0]=ifac[0]=1;
for(int i=1;i<=N;i++)
fac[i]=1ll*fac[i-1]*i%mod;
ifac[N]=fpow(fac[N],mod-2);
for(int i=N-1;i;i--)
ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
f[0]=1,f[1]=0,f[2]=2;
for(int i=3;i<=N;i++){
f[i]=1ll*f[i-1]*(i-1)%mod*i%mod;
f[i]=(f[i]+1ll*f[i-2]*i%mod*(i-1)%mod*(i-1))%mod;
}
// for(int i=1;i<=10;i++)
// printf("%d ",f[i]);
// printf("\n");
T=read();
for(int Case=1;Case<=T;Case++){
n=read(),X=read(),ans=0;
for(int i=1,tot=1;i<=n;i++){
tot=1ll*tot*(n-i+1)%mod*(n-i+1)%mod;
if(i>=X) ans=(ans+1ll*tot*f[n-i]%mod*ifac[i])%mod;
}
if(!X) ans=(ans+f[n])%mod;
printf("Case #%d: %d\n",Case,ans);
}
return 0;
}
```