卢卡斯定理与中国剩余定理
卢卡斯定理 卢卡斯定理主要是用来求组合数取模，即C(n,m)%p。其适用范围是:组合数很大，但p又不是很大且p是素数的情况(10^6+3也算是“不很大”) 。卢卡斯定理可以表达为:
Read more快速乘算法
原理与快速幂相似，利用二进制将两个数的乘法运算转化为加法运算。具体代码如下:
Read more
HDU5446-Unknown Treasure(卢卡斯定理，中国剩余定理)
题目链接:Unknown Treasure 这道题求得实际上是C(n,m)%M,M=p1·p2·p3···pk。又因为pi都是素数，故可用卢卡斯定理。但这里不可以直接用Lucas，因为Lucas的使用条件是“C(n,m)很大，但p不太大，同时p为素数”，而这里的M可能会很大。故我们可以先求C(n,m)%p1,C(n,m)%p2,C(n,m)%pk，然后再利用中国剩余定理得到最终答案。 代码如下: #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; typedef long long LL; //从n个苹果中挑出m个相互..
Read more
BZOJ4403-序列统计(组合数学，卢卡斯定理)
题目链接:序列统计 首先，L与R实际上是没太大意义的，因为我们需要的只是L和R之间含有多少个数，即R-L+1个数。其次，要注意一点，在一个序列中，数字是可以重复的。以样例中的2 4 5为例，符合要求的序列有{4},{5},{4,5},{4,4},{5,5}。事实上，问题可以转化为“有R-L+1个不同的盒子，若要将i(1<=i<=n)个相同的小球放进这些盒子里(某些盒子可以为空)，问对于所有的i，放法的总和是多少？”其中，不同的盒子代表着不同的数，在一个盒子中放入一个球，相当于选取一次该数字作为序列中的成员。再将问题抽象一下，即为“将i个小球划分成k堆(1<=k<=i)，问对于所有的i，划分方法的总和是多少？”对于这个问题，我们可以直接用C(m+n,n)求解(对于本题是C(seg..
Read moreHDU3037-Saving Beans(卢卡斯定理，组合数)
题目链接：HDOJ-3037 这道题关键之处在于式子的推导，只要把式子推导出来了，就可以直接套用Lucas的模板，从而求出答案。那么，公式要怎么求呢？ 首先，问题要求的是从n棵树中收集不超过m个果实(原本以为是将不多于m个果实放到n棵树中......这题目表达有问题啊！)。也就是说，问题其实是求方程x1+x2+x3+···+xn=m的非负整数解的个数。那么我们要怎求呢？ 首先，如果是求正整数解的个数，那我们可以直接用最简单的隔板法，即C(m-1,n-1);但这里求的是非负整数解，也就是说x1，x2，···,xn中的一个或多个可以为0。这种情况下，我们仍可以用隔板法来计算。方法是，将求非负整数解这一个问题转化为求正整数解，也就是将每一个x(x1,x2,···,xm)都加上1，构造一个新的方程y..
Read morePOJ1002-A+B Problem
大数相加，方法就是用字符串存数字，然后模拟手算的方法计算。虽是水题，但有些细节还是要注意。
Read morePOJ1182-食物链
题目链接：1182-食物链
Read morePOJ2159-Ancient Cipher
题目链接：Ancient Cipher
Read morePOJ1328-Radar Installation(贪心)
思路：以岛屿为圆心作半径为d的圆，则每个可以被覆盖的岛屿（即y<=d）都可以在x轴上形成一个或两个交点。也就是说，每个岛屿在画圆后都在x轴上形成一个长度大于或等于0的区间。这些区间即为安装雷达的地方。接下来要做的就是将这些区间的相交区间（即交集）找出来并计数。相交区间的数目即为雷达的数目。
Read moreUVa101-The Blocks Problem
题目链接：Uva101 也可以在这看：Vjudge
Read more