Lucas定理及其应用

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)很容易求得。

巴特西

Lucas定理及其应用

最新文章

热门文章