lucas定理和组合数学

自湖南长沙培训以来的坑。。。一直未填,今天把这个问题解决掉。

参考:

1.http://www.cnblogs.com/Var123/p/5523068.html

2.http://blog.csdn.net/qzh_1430586275/article/details/51893154

3.http://blog.csdn.net/check_check_check/article/details/52101467

一、lucas定理的定义

(当且仅当p为质数)

很简短,下面看看应用和相关题目。

二、lucas定理的应用

1、[bzoj4591][Shoi2015][超能粒子炮·改]

题目描述:求 C(n,0)+C(n,1)+...+C(n,k)mod2333

推到过程:

易得,

原式=C(n/2333,0)∗C(nmod2333,0)+C(n/2333,0)∗C(nmod2333,1)+...+C(n/2333,k/2333)∗C(nmod2333,kmod2333)   mod 2333

也就是将原式中的各个mod 2333项拆分成两项再总体mod 2333

同类项合并,分两种部分考虑:

设k=k1*2333+k2 (0≤k1,k2)

1)对于k1部分

先考虑k1=0的情况,可以得出这些乘积的各个首项是C(n/2333,0),将其提出得到C(n/2333,0)*∑C(n%2333,i)(其中i∈[0,2333])

考虑k1=1的情况,可得C(n/2333,1)*∑C(n%2333,i)(其中i∈[0,2333])

考虑k1=2的情况,可得C(n/2333,2)*∑C(n%2333,i)(其中i∈[0,2333])

···  ···  ···  ···  ···  ···

提公因式→→→∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))

重复3遍

∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))

∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))

∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))

吼,各位就等了,看看k2部分吧

2)对于k2部分

原式=C(n/2333,k1)*C(n%2333,0)+C(n/2333,k1)*C(n%2333,1)+······+C(n/2333,k1)*C(n%2333,k%2333)

=C(n/2333,k1)*(∑C(n%2333,i))(其中i∈[0,k%2333])

综上,ans=∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))+C(n/2333,k1)*(∑C(n%2333,i))(其中i∈[0,k%2333])

说了这么多,那么这个定理的用法是什么?

显然是递归求解组合数的模数咯~

所以对于这道题,我们先预处理出一个S(n,k)=∑C(n,i) (i∈[0,k]) (当然最后都是mod p意义下的),ans=S(n%2333,2332)*(∑C(n/2333,j)) (j∈[0,k1)) + C(n/2333,k1)*S(n%2333,k%2333)

ans中的S()一定可以用二维的东西在规定时空内求出,而∑C(n/2333,j)就是我们超能粒子炮`改的子问题,递归求解即可,另,C(n/2333,k1)也可以用lucas定理递归来解

于是这道题就口头ac了。

时间: 01-10

lucas定理和组合数学的相关文章

组合数学lucas定理 BZOJ2982 combination

2982: combination Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 597  Solved: 357[Submit][Status][Discuss] Description LMZ有n个不同的基友,他每天晚上要选m个进行[河蟹],而且要求每天晚上的选择都不一样.那么LMZ能够持续多少个这样的夜晚呢?当然,LMZ的一年有10007天,所以他想知道答案mod 10007的值.(1<=m<=n<=200,000,000) Inpu

HDU 3037 Saving Beans (Lucas定理)

/*求在n棵树上摘不超过m颗豆子的方案,结果对p取模. 求C(n+m,m)%p. 因为n,m很大,这里可以直接套用Lucas定理的模板即可. Lucas(n,m,p)=C(n%p,m%p,p)*Lucas(n/p,m/p,p): ///这里可以采用对n分段递归求解, Lucas(x,0,p)=1: 将n,m分解变小之后问题又转换成了求C(a/b)%p. 而C(a,b) =a! / ( b! * (a-b)! ) mod p 其实就是求 ( a! / (a-b)!) * ( b! )^(p-2)

BZOJ 4403 2982 Lucas定理模板

思路: Lucas定理的模板题.. 4403 //By SiriusRen #include <cstdio> using namespace std; const int mod=1000003; #define int long long int cases,N,L,R,fac[mod],inv[mod]; int C(int n,int m){ if(n<m)return 0; if(n<mod&&m<mod)return fac[n]*inv[n-m]

HDU 3037 Saving Beans (数论,Lucas定理)

题意:问用不超过 m 颗种子放到 n 棵树中,有多少种方法. 析:题意可以转化为 x1 + x2 + .. + xn = m,有多少种解,然后运用组合的知识就能得到答案就是 C(n+m, m). 然后就求这个值,直接求肯定不好求,所以我们可以运用Lucas定理,来分解这个组合数,也就是Lucas(n,m,p)=C(n%p,m%p)* Lucas(n/p,m/p,p). 然后再根据费马小定理就能做了. 代码如下: 第一种: #pragma comment(linker, "/STACK:10240

HDU3037 Saving Beans(Lucas定理+乘法逆元)

题目大概问小于等于m个的物品放到n个地方有几种方法. 即解这个n元一次方程的非负整数解的个数$x_1+x_2+x_3+\dots+x_n=y$,其中0<=y<=m. 这个方程的非负整数解个数是个经典问题,可以+1转化正整数解的个数用插板法解决:$C_{y+n-1}^{n-1}=C_{y+n-1}^y$. 而0<=y<=m,最后的结果就是—— $$\sum_{i=0}^m C_{i+n-1}^i$$ $$C_{n-1}^0+C_{n}^1+C_{n+1}^2+\dots+C_{n-1

【Lucas定理/费马小定理/中国剩余定理/扩展欧几里得】[BZOJ 1951] 古代猪文

[Description] 求 [Solution] 容易得到, 所以,重点在怎么求 如果是p-1是个质数,我们可以用sqrt(n)的时间枚举所有d,用Lucas定理分别计算求和即可. 但是我们发现p-1=2*3*4679*35617,并不是一个质数,所以Lucas定理不能用了吗?并不,我们可以算出这个合式分别对2.3.4679.35617的模值,写出四个同余方程,再用孙子定理求解即可.注意特判g==p的情况,此时费马小定理不成立,ans=0. [Code] #include<cmath> #

[Swust OJ 247]--皇帝的新衣(组合数+Lucas定理)

题目链接:http://acm.swust.edu.cn/problem/0247/ Time limit(ms): 1000 Memory limit(kb): 65535 Description 在很久很久以前,有个臭美国王.一天,他得到了一件新衣,于是决定巡城看看老百姓的反应(囧).于是他命令可怜的宰相数一下他有多少种巡城方案. 城市是一个N*M的矩形,(N+1)*(M+1)条街把城市分成了N*M块.国王从左下角出发,每次只能向右或向上走,右上角是终点. 请你帮帮可怜的宰相. Input

Lucas定理学习(进阶中)

(1)Lucas定理:p为素数,则有: (2)证明: n=(ak...a2,a1,a0)p = (ak...a2,a1)p*p + a0 =  [n/p]*p+a0,m=[m/p]*p+b0其次,我们知道,对任意质数p有(1+x)^p=1+(x^p)(mod p) .我们只要证明这个式子:C(n,m)=C([n/p],[m/p]) * C(a0,b0)(mod p),那么就可以用归纳法证明整个定理.对于模p而言,我们有下面的式子成立: 上式左右两边的x的某项x^m(m<=n)的系数对模p同余.其

[Lucas定理]【学习笔记】

这种神奇的东西............... 参考资料:http://www.cnblogs.com/jianglangcaijin/p/3446839.html Lucas定理 适用于n很大p较小的时候 $ C_n^m\%p \ p \ is \ prime$ $ n=n_k*p^k+n_{k-1}*p^{k-1}+...+n_2*p^2+n_1*p+n_0 $ $ m=m_k*p^k+m_{k-1}*p^{k-1}+...+m_2*p^2+m_1*p+m_0 $ $ C_n^m=\prod\

FZU 2020 组合 (Lucas定理)

题意:中文题. 析:直接运用Lucas定理即可.但是FZU好奇怪啊,我开个常数都CE,弄的工CE了十几次,在vj上还不显示. 代码如下: #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #include <iostream>