【容斥原理】Arrange the Numbers LightOJ – 1095

Consider this sequence {1, 2, 3 ... N}, as an initial sequence of first N natural numbers. You can rearrange this sequence in many ways. There will be a total of N! arrangements. You have to calculate the number of arrangement of first N natural numbers, where in first M positions; exactly K numbers are in their initial position.

For Example, N = 5, M = 3, K = 2

You should count this arrangement {1, 4, 3, 2, 5}, here in first 3 positions 1 is in 1st position and 3 in 3rd position. So exactly 2 of its first 3 are in there initial position.

But you should not count {1, 2, 3, 4, 5}.

Input
Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case contains three integers N (1 ≤ N ≤ 1000), M (M ≤ N), K (0 < K ≤ M).

Output
For each case, print the case number and the total number of possible arrangements modulo 1000000007.

Sample Input
2

5 3 2

10 6 3

Sample Output
Case 1: 12

Case 2: 64320

$ans = C\binom{k}{m} * ∑ (C\binom{i}{n-k} * A\binom{n-k-i}{n-k-i} * (-1)^i ) \mod mod$

• 由于容斥原理求的是$\mid \cup A_i \mid$ 而这题求的是$\mid \cap A_i \mid$ 所以需要变化一下。
• 某班54人，共三项活动，参加一项的分别有25，22，34人，参加两项的12，18，14人，求三项都参加的人数。可以猜到这题最后用54减去容斥结果。
• 推广而来就是由全集减去容斥结果。
• 具体证明：容斥原理

• 由于c++里面%的结果的符号取决于被mod的数，所以会有负数结果。例如：
• ${(4-2)\mod 3=4\ mod 3-2\mod 3=(1-2)\mod 3=-1\mod 3=-1}$
• 所以当结果小于0的时候要加上mod的数字。
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
ll po[1010]={0};
ll se[1010][1010];
ll mo=1000000007;
ll t,n,m,k;
ll c(ll mm,ll nn)
{
//if(nn==0) return 1;
//return po[mm]/(po[nn]*po[mm-nn])%mo;
return se[mm][nn];
}
int main()
{
po[0]=1;
for(int i=1;i<=1000;i++)
{
po[i]=po[i-1]*i%mo;
se[i][0]=1;
}
se[0][0]=1;
for(int i=1;i<=1000;i++)
for(int j=1;j<=i+1;j++)
se[i][j]=(se[i-1][j-1]+se[i-1][j])%mo;
scanf("%lld",&t);
for(ll i=1;i<=t;i++)
{
ll ans=0,res=0;
scanf("%lld%lld%lld",&n,&m,&k);
for(ll j=0;j<=m-k;j++)
{
ll temp=c(m-k,j)*po[n-k-j];
if(~j&1) res+=temp;
else res-=temp;
//if(res<0) res+=mo;
res=res%mo;
if(res<0) res+=mo;
}
ans=res*c(m,k)%mo;
printf("Case %lld: %lld\n",i,ans);
}

}