题解：P13234 [GCJ 2015 Finals] Campinatorics
Eddie08012025
·
·
题解
简要分析
枚举 3 的个数，若个数为 k。
选出这 k 个 3 的方案数即为选出 k 行 k 列再乘以在这 k 行 k 列中选出 k 个位置的方案数，为：
\binom{n}{k}^2 k!
剩下 n-k 行 n-k 列，先安排 n-k 个 2，方案数 (n-k)!。
最后考虑 1，如果填 2 可以看作一个序列 a_1,a_2,\dots a_{n-k} 表示每一行的 2 放在哪一列，就可以看作错排问题，要求 1 的位置和 2 的位置不重合。
那么总方案数就是：
\sum_{k=x}^{n}\binom{n}{k}^2 k!(n-k)!d(n-k)
其中错排的递推方程式是 $d(x)=(x-1)(d(x-1)+d(x-2))$，其中 $d(0)=1,d(1)=0$。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int t,n,x,jie[1000005],inv[1000005],d[1000005];
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1)ans=1ll*ans*x%mod;
y>>=1;
x=1ll*x*x%mod;
}
return ans;
}
long long C(int x,int y){
if(y>x)return 0;
if(y==0||y==x)return 1;
return 1ll*jie[x]*inv[x-y]%mod*inv[y]%mod;
}
int solve(int x){
if(x==0)return 1;
if(x==1)return 0;
long long ans=jie[x];
for(int i=1;i<=x;i++){
ans+=1ll*C(x,i)*jie[x-i]%mod*(i&1?-1:1)+mod;
ans%=mod;
}
// cout<<x<<" "<<ans<<'\n';
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
jie[0]=1;
d[0]=1,d[1]=0;
for(int i=1;i<=1e6;i++){
jie[i]=1ll*jie[i-1]*i%mod;
inv[i]=qpow(jie[i],mod-2);
if(i>=2)d[i]=(1ll*(i-1)*(d[i-1]+d[i-2]))%mod;
}
for(int _=1;_<=t;_++){
cin>>n>>x;
int ans=0;
for(int i=x;i<=n;i++){
ans+=1ll*C(n,i)*C(n,i)%mod*jie[i]%mod*jie[n-i]%mod*d[n-i]%mod;
ans%=mod;
}
printf("Case #%d: %d\n",_,ans);
}
return 0;
}
```