Lucas定理这里有详细的证明。
其实就是针对n, m很大时，要求组合数C(n, m) % p, 一般来说如果p <= 10^5,那么就能很方便的将n，m转化为10^5以下这样就可以按照乘法逆元的方法求解。
定义：
C(n, m) = C(n%p, m%p)*C(n/p, m/p) (mod p)
一种比较好理解的证明方式是这样的， 上面资料中有提到，
由p为质数，(1+x)^p = 1+x^p (mod p) p为质数，然后就是下面这幅图的内容了。
将n, m分别表示成p进制，n = n/p*p+a0, m = m/p*p+b0;
那么对于上面式子x^m的系数，左右两部分肯定是相等的，左边系数C(n, m) ， 而m = m/p*p+b0, 那么i和j分别对应m/p, 和bo
所以就可以得到证明：C(n, m) = C(n%p, m%p)*C(n/p, m/p) (mod p)。
下面就是具体题目了：
HDU 3037 Saving Beans
http://acm.hdu.edu.cn/showproblem.php?pid=3037
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std; #define N 100010 long long mod_pow(int a,int n,int p)
{
long long ret=;
long long A=a;
while(n)
{
if (n & )
ret=(ret*A)%p;
A=(A*A)%p;
n>>=;
}
return ret;
} long long factorial[N]; void init(long long p)
{
factorial[] = ;
for(int i = ;i <= p;i++)
factorial[i] = factorial[i-]*i%p;
//for(int i = 0;i < p;i++)
//ni[i] = mod_pow(factorial[i],p-2,p);
} long long Lucas(long long a,long long k,long long p) //求C(n,m)%p p最大为10^5。a,b可以很大！
{
long long re = ;
while(a && k)
{
long long aa = a%p;long long bb = k%p;
if(aa < bb) return ; //这个是最后的改动！
re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-,p)%p;//这儿的求逆不可先处理
a /= p;
k /= p;
}
return re;
} int main()
{
int t;
cin >> t;
while(t--)
{
long long n,m,p;
cin >> n >> m >> p;
init(p);
cout << Lucas(n+m,m,p) << "\n";
}
return ;
}
分析：
题意容易转化为x1+x2+...xn <= m的解，最后结果就是C(n+m, m)，但为什么呢？
我们可以这样分析：
每棵树上能够放的豆子数目i，然后用一个式子x^i表示，然后每棵树有0， 1， 2， m种可能的放置数目，用一个多项式(1+x^1+x^2+.....x^m)表示，等比数列求和(1-x^(m+1)/(1-x)，n棵树就是n次方。
即问题变成了，[1-x^(m+1)]^n*1/(1-x)^n的i<=m 的各个x^i的系数之和， 对于1/(1-x)^n， 借用无穷级数的直接结论 = ∑C(n+k-1, n-1)x^k , k >= 0,很显然前面部分[1-x^(m+1)]^n只能为最小幂次也就是x^0,后面就是x^i，问题变成了，C(n+k-1, n-1) 0 <= k <= m,化简一下就是C(n+m, n).
具体求解的时候，C(n, m) = C(n%p, m%p) * C(n/p, m/p) mod p ，一旦C(x, y) x < y 那么返回0， 而且求解的时候是直接乘以阶乘的逆元。
HDU 4349 Xiao Ming's Hope
http://acm.hdu.edu.cn/showproblem.php?pid=4349
#include <cstdio>
#include <iostream>
#define bug(x) printf("%d\n", (x));
#define in freopen("solve_in.txt", "r", stdin); using namespace std;
typedef long long LL;
int main(){ LL n;
while(scanf("%I64d", &n) == ){
int x = __builtin_popcount(n);
LL ans = , a = ;
while(x){
if(x&) ans = ans*a;
a = a*a;
x >>= ;
}
printf("%I64d\n", ans);
}
return ;
}
分析：
题目要求C(n, i) i <= n结果中奇数个数，很明显就是sum{C(n, i)%2| i <= n}， 模2的结果是0， 1， 最终结果只有C(1, 0) , C(1, 1) , C(0, 0)为1， C(0, 1)为0，n和i的二进制表示akak-1...a2a1a0和
bkbk-1...b2b1b0中，对应位置不能出现ai = 0, bi = 1，结果为0， 其余情况结果都会为1，那么问题就转为x = n中二进制位为1个数，答案是2^x。
451E - Devu and Flowers
http://codeforces.com/problemset/problem/451/E
#include <cstdio>
#include <iostream>
#define bug(x) printf("%d\n", (x));
#define in freopen("solve_in.txt", "r", stdin);
using namespace std;
typedef long long LL; const int maxn = ;
const int M = (int)1e9+; LL inv[maxn], fac[maxn];
LL powmod(LL a, LL b, LL c) {
LL res = ;
while(b) {
if(b&) res = res*a%c;
a = a*a%c;
b >>= ;
}
return res;
}
void pre() {
fac[] = ;
for(int i = ; i < maxn; i++) fac[i] = fac[i-]*i%M;
for(int i = ; i < maxn; i++) inv[i] = powmod(fac[i], M-, M);
}
LL nCr(LL n, LL m) {
n %= M;
m %= M;
if(m == ) return ;
if(n < m) return ;
LL res = ;
for(int i = ; i < m; i++)
res = res*(n-i)%M;
res = res*inv[m]%M;
return res;
}
LL f[maxn];
void solve(LL n, LL ss) {
LL ans = ;
for(int s = ; s < (<<n); s++) {
LL sum = ;
int tag = ;
for(int i = ; i < n; i++) if(s&(<<i)) {
sum += f[i];
if(sum > ss) break;
tag *= -;
} if(sum <= ss){
ans = (ans+nCr(n+ss-sum-, n-)*tag+M)%M;
}
}
if(ans < ) ans += M;
printf("%I64d\n", ans);
} int main() { pre();
LL n, s;
scanf("%I64d%I64d", &n, &s);
for(int i = ; i < n; i++) scanf("%I64d", f+i), f[i]++;
solve(n, s);
return ;
}
n个盒子每个盒子fi朵鲜花，选出s朵花，共有多少种选法？
分析：
每个盒子用(1+x^1+x^2..........x^fi)表示，总表达式∏(1+x^1+x^2..........x^fi) (0 <= i < n) = ∏(1-x^(fi+1)(0 <= i < n) * 1/(1-x)^n， 答案就是x^s的系数。
同样分成两部分 ∏(1-x^(fi+1)(0 <= i < n)和 1/(1-x)^n，后一部分很好求， x^k系数就是 C(n+k-1, n-1)，前一部分x^i通过二进制表示法求出， 二进制每个位为1则表示拿出-x^(fi+1)相乘。那么问题关键在于C(n+k-1， n-1)，对于C(n, m) = C(n%p, m%p)*C(n/p, m/p) mod p 由于m很小C(n/p, m/p)为1，那么C(n%p, m%p)很容易求得。