给出n,m,k,求1~n中前m个正好有k个在原来位置的种数(i在第i个位置)
做法:容斥,先选出k个放到原来位置,然后剩下m-k个不能放到原来位置的,用0个放到原来位置的,有C(m-k,0)*(n-k)!种 - 1个放原来位置的,有C(m-k,1)*(n-k-1)!种+...-...
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int N=1e3+10; 5 const int INF=0x3f3f3f3f; 6 const int mod=1e9+7; 7 int cas=1,T; 8 int n,m,k,c[N][N]; 9 LL fac[N]; 10 void init() 11 { 12 memset(c,0,sizeof(c)); 13 c[0][0]=fac[0]=1; 14 for(int i=1;i<N;i++) 15 { 16 fac[i]=fac[i-1]*i%mod; 17 c[i][0]=1; 18 for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; 19 } 20 //for(int i=0;i<100;i++) 21 //{ 22 //for(int j=0;j<=i;j++) printf("%d ",c[i][j]); 23 //printf(" "); 24 //} 25 } 26 int main() 27 { 28 //freopen("1.in","w",stdout); 29 //freopen("1.in","r",stdin); 30 //freopen("1.out","w",stdout); 31 init(); 32 scanf("%d",&T); 33 while(T--) 34 { 35 scanf("%d%d%d",&n,&m,&k); 36 LL ans=0; 37 for(int i=0;i<=m-k;i++) 38 { 39 if(i&1) ans-=c[m-k][i]*fac[n-k-i]%mod; 40 else ans+=c[m-k][i]*fac[n-k-i]%mod; 41 ans%=mod; 42 //printf("%lld ",ans); 43 } 44 ans=ans*c[m][k]%mod; 45 printf("Case %d: %lld ",cas++,(ans+mod)%mod); 46 } 47 //printf("time=%.3lf ",(double)clock()/CLOCKS_PER_SEC); 48 return 0; 49 }