How Many Sets II
Time Limit: 2 Seconds Memory Limit: 65536 KB
Given a set S = {1, 2, ..., n}, number m and p, your job is to count how many set T satisfies the following condition:
- T is a subset of S
- |T| = m
- T does not contain continuous numbers, that is to say x and x+1 can not both in T
Input
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
Output the total number mod p.
Sample Input
5 1 11
5 2 11
Sample Output
5
6
由于m<=10^4,所以只需要一个for循环计算sum1,sum2就可以了。
和fzu 2020是一样的。
方案数目为C(n-k+1,k)种。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL; LL pow_mod(LL a,LL n,LL p)
{
LL ans=;
while(n)
{
if(n&) ans=(ans*a)%p;
n=n>>;
a=(a*a)%p;
}
return ans;
}
LL C(int n,int m,int p)/**Cnm %p **/
{
int i;
LL sum1=,sum2=;
for(i=;i<=m;i++)
{
sum1=(sum1*(n-i+))%p;
sum2=(sum2*i)%p;
}
sum1=(sum1*pow_mod(sum2,p-,p))%p;
return sum1;
}
void solve(int n,int m,int p)
{
LL ans=;
while(n&&m&&ans)
{
ans=(ans*C(n%p,m%p,p))%p;
n=n/p;
m=m/p;
}
printf("%lld\n",ans);
}
int main()
{
int n,m,p;
while(scanf("%d%d%d",&n,&m,&p)>)
{
n=n-m+;
if(n<m){
printf("0\n");
continue;
}
else if(n==m){
printf("1\n");
continue;
}
if(m>n-m) m=n-m;
solve(n,m,p);
}
return ;
}