LightOJ 1095 Arrange the Numbers（容斥原理）

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1095

题意：给出数字n,m,K(0<K<=m<=n)。在n个数字(1到n)的所有全排列中(有n!个)，有多少个满足前m个数字恰有K个数字是不变的？

思路：首先应该在前m个中选出K个作为不变的，有C(m,K)种，接着，前m个中剩下的m-K个必须都不能自己放自己。后面还有n-m位，设p=m-K,q=n-m，则(p+q)!，即将剩余所有位全排列，这样肯定有前m位中剩下的m-K位放自己，所以要减去这些，根据容斥原理答案为C(m,K)*∑C(p,i)*(p+q-i)!*((-1)^i)(1<=i<=p)。

 

View Code #include <iostream>#include <cstdio>#include <cstring>#define int64 long longusing namespace std;const int64 MOD=1000000007;int C,num=0;int n,m,K;int64 b[1005],a[1005];int64 exGcd(int64 a,int64 b,int64 &x,int64 &y){int64 r,t;if(b==0){x=1;y=0;return a;}r=exGcd(b,a%b,x,y);t=x;x=y;y=t-a/b*y;return r;}void init(){int64 i,x,y;for(i=1;i<=1000;i++){exGcd(i,MOD,x,y);a[i]=x;a[i]=(a[i]%MOD+MOD)%MOD;}b[0]=1;b[1]=1;for(i=2;i<=1000;i++) b[i]=b[i-1]*i%MOD;}int64 ok(int n,int m){int64 ans=1;int i;for(i=n;i>=n-m+1;i--) ans=ans*i%MOD;for(i=1;i<=m;i++) ans=ans*a[i]%MOD;return ans;}int64 cal(){int64 ans=ok(m,K),temp;int i,t=-1,p=m-K,q=n-m;temp=b[p+q];for(i=1;i<=p;i++){temp+=t*b[p+q-i]%MOD*ok(p,i)%MOD;temp%=MOD;t*=-1;}if(temp<0) temp+=MOD;return ans*temp%MOD;}int main(){init();for(scanf("%d",&C);C--;){scanf("%d%d%d",&n,&m,&K);printf("Case %d: %lld\n",++num,cal());}return 0;}