C++14(g++5.4) 解法, 执行用时: 83ms, 内存消耗: 584K, 提交时间: 2019-04-14 19:53:02

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
#define ll long long 
#define maxn 5000300

ll p,k,S;

ll qpow(ll a,ll n){
	ll ret = 1;
	while(n){
		ret = n&1?ret*a%p:ret;
		a = a*a%p;
		n >>= 1;
	}
	return ret;
}

ll C(ll n,ll m){
	if(m>n || m<0)return 0;
	if(n==m || m==0 || n==1)return 1L;
	if(m>n-m)m=n-m;
	ll a=1,b=1;
	for(int i=0;i<m;i++){
		a = a*(n-i)%p;
		b = b*(i+1)%p;
	}
	return a*qpow(b,p-2)%p;
}

ll Cll(ll n,ll m){
	if(m>0)
		return ( Cll(n/p,m/p)*C(n%p,m%p) )%p;
	else
		return 1;
}

int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	while(cin>>k>>S>>p){
		ll ans = Cll(k+S,k+k);
		cout<<ans<<endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 60ms, 内存消耗: 488K, 提交时间: 2019-04-13 15:27:50

#include<stdio.h>
#define ll long long
ll p;

inline ll qpow(ll a,ll b){
    if(b==1) return a;
    ll t=qpow(a,b/2);
    t=t*t%p;
    if(b&1) t=t*a%p;
    return t;
}
inline ll C(ll n,ll m){
    if(n<m) return 0;
    if(m>n-m) m=n-m;
    ll a=1,b=1;
    for(int i=0;i<m;i++){
        a=(a*(n-i))%p;
        b=(b*(i+1))%p;
    }
    return a*qpow(b,p-2)%p;
}
inline ll Lucas(ll n,ll m){
    if(m==0) return 1;
    return Lucas(n/p,m/p)*C(n%p,m%p)%p;
}
ll n,m;
int T;
int main(){
        scanf("%lld%lld%lld",&n,&m,&p);
        printf("%lld\n",(Lucas(n+m,m-n))%p);
}