UVA11481 Arrange the Numbers
组合数问题。
做法貌似很多，显然在前 \(m\) 个数中选 \(k\) 个，即 \(C(m,k)\)，然后后面有 \(m-k\) 个数需要保证不放在自己的位置上，所以后面整体是一个禁位问题，貌似可以用棋盘多项式去推禁位公式，但是暂时不会。不过还有另外一种思路，就是对于后面的 \(n-m\) 个 “自由数”，可以考虑枚举有多少数放在原位，这样显然可以包含所有情况，那么对于剩下的就是经典的错排问题了。复杂度为 \(O(n^2+Tn)\)，OK。
关于错排递推公式 \(D(n)=(n-1)*[D(n-1)+D(n-2)]\) 的证明：考虑第 \(n\) 个数可以放在 \(1 \sim n-1\) 这些位置上，比如放在第 \(i\) 位，那么对于 \(i\) ，如果把它放在 \(n\) 这个位置上，那么就变成了 \(D(n-2)\) 这个位置；如果把它放在其它位置上，发现实际上其本质就变成了 \(D(n-1)\) 这个问题。
当然错排公式也可以由容斥定理推出 \(D(n)=n!\sum^n_{i=0} \frac{1}{i!}*(-1)^i\) 。
const int N=1005,mod=1e9+7;
ll fac[N],d[N],c[N][N];
signed main(){
IOS
fac[0]=1;
for(int i=1;i<=1000;++i) fac[i]=fac[i-1]*i%mod;
c[0][0]=1;
for(int i=1;i<=1000;++i){
c[i][0]=1;
for(int j=1;j<=i;++j)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}//combinatorial number
d[0]=1,d[1]=0;
for(int i=2;i<=1000;++i)
d[i]=(d[i-1]+d[i-2])%mod*(i-1)%mod;
int T;
cin>>T; int n,m,k;
for(int kase=1;kase<=T;++kase){
cin>>n>>m>>k; ll ans=0;
for(int i=0;i<=n-m;++i) ans=(ans+d[m-k+i]*c[n-m][i]%mod)%mod;
cout<<"Case "<<kase<<": "<<ans*c[m][k]%mod<<'\n';
}
return 0;
}
· EOF