P7 UVA11481 Arrange the Numbers

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