Given a set S = {1, 2, ..., n}, number m and p, your job is to count how many set T satisfies the following condition:
There are multiple cases, each contains 3 integers n ( 1 <= n <= 109 ), m ( 0 <= m <= 104, m <= n ) and p ( p is prime, 1 <= p <= 109 ) in one line seperated by a single space, proceed to the end of file.
Output the total number mod p.
5 1 11 5 2 11
5 6
由于m<=10^4,所以只需要一个for循环计算sum1,sum2就可以了。
和fzu 2020是一样的。
方案数目为C(n-k+1,k)种。
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 typedef long long LL; 7 8 LL pow_mod(LL a,LL n,LL p) 9 { 10 LL ans=1; 11 while(n) 12 { 13 if(n&1) ans=(ans*a)%p; 14 n=n>>1; 15 a=(a*a)%p; 16 } 17 return ans; 18 } 19 LL C(int n,int m,int p)/**Cnm %p **/ 20 { 21 int i; 22 LL sum1=1,sum2=1; 23 for(i=1;i<=m;i++) 24 { 25 sum1=(sum1*(n-i+1))%p; 26 sum2=(sum2*i)%p; 27 } 28 sum1=(sum1*pow_mod(sum2,p-2,p))%p; 29 return sum1; 30 } 31 void solve(int n,int m,int p) 32 { 33 LL ans=1; 34 while(n&&m&&ans) 35 { 36 ans=(ans*C(n%p,m%p,p))%p; 37 n=n/p; 38 m=m/p; 39 } 40 printf("%lld\n",ans); 41 } 42 int main() 43 { 44 int n,m,p; 45 while(scanf("%d%d%d",&n,&m,&p)>0) 46 { 47 n=n-m+1; 48 if(n<m){ 49 printf("0\n"); 50 continue; 51 } 52 else if(n==m){ 53 printf("1\n"); 54 continue; 55 } 56 if(m>n-m) m=n-m; 57 solve(n,m,p); 58 } 59 return 0; 60 }
zoj 3557 How Many Sets II,布布扣,bubuko.com
原文：http://www.cnblogs.com/tom987690183/p/3720219.html