【HDU 3037】Saving Beans

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3037
数据生成器：http://paste.ubuntu.com/22886753/

lucas定理 + 插板法

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int MAXN = 100000+9;

int f[MAXN];

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0', c=getchar();
	return ret;	
}

inline int quick_pow(int w, int t, int p) {
	int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret*w % p;
		w = (LL)w*w % p; t >>= 1;
	}
	return ret;
}

inline int C(int m,int n, int p) {
	if (n > m) return 0;
	else return (LL)f[m]*quick_pow(f[m-n],p-2,p)*quick_pow(f[n],p-2,p)%p;
}

int lucas(int m, int n, int p) {
	if (n == 0) return 1;
	else return ((LL)lucas(m/p,n/p,p) * C(m%p,n%p,p)) % p;
}

int main(){
	int T = read(); while (T--) {
		int n = read(),m = read(),p = read(); 
		f[0] = 1; for (int i=1;i<=p;i++) f[i] = (LL)f[i-1]*i % p;
		printf("%d\n",lucas(n+m,n,p));
	}
	return 0;
}

另外，lucas定理可以推广到整数域上,参见：
http://www.cnblogs.com/jianglangcaijin/p/3446839.html