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.
Lucas定理p为质数情况裸题
因为是选的元素不能连续，我们先把选的元素拿出来，剩下的元素有n-m+1个空，选m个插进去行了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,m,P;
ll Pow(ll a,ll b){
ll ans=;
for(;b;b>>=,a=a*a%P)
if(b&) ans=ans*a%P;
return ans;
}
ll Inv(ll a){return Pow(a,P-);}
ll C(ll n,ll m){
if(n<m) return ;
ll x=,y=;
for(ll i=n-m+;i<=n;i++) x=x*i%P;
for(ll i=;i<=m;i++) y=y*i%P;
return x*Inv(y)%P;
}
ll Lucas(ll n,ll m){
if(n<m) return ;
ll re=;
for(;m;n/=P,m/=P) re=re*C(n%P,m%P)%P;
return re;
}
int main(){
//freopen("in","r",stdin);
while(scanf("%lld%lld%lld",&n,&m,&P)!=EOF)
printf("%lld\n",Lucas(n-m+,m));
}
BZOJ 2982: combination
模数10007很小，可以直接线性预处理阶乘和逆元，48ms-->4ms
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=;
inline ll read(){
char c=getchar();ll x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
ll n,m,P=;
ll inv[N],fac[N],facInv[N];
void getInv(int n){
inv[]=fac[]=facInv[]=;
for(int i=;i<=n;i++){
if(i!=) inv[i]=-P/i*inv[P%i]%P;
inv[i]+=inv[i]<?P:;
fac[i]=fac[i-]*i%P;
facInv[i]=facInv[i-]*inv[i]%P;
}
} ll C(ll n,ll m){
if(n<m) return ;
return fac[n]*facInv[m]%P*facInv[n-m]%P;
}
ll Lucas(ll n,ll m){
if(n<m) return ;
ll re=;
for(;m;n/=P,m/=P) re=re*C(n%P,m%P)%P;
return re;
}
int main(){
freopen("in","r",stdin);
getInv(N-);
int T=read();
while(T--){
n=read();m=read();
printf("%lld\n",Lucas(n,m));
}
}