首页 > 其他分享 >卢卡斯定理

卢卡斯定理

时间：2024-02-21 15:44:20浏览次数：22  
标签：ch int 定理 long 卢卡斯 include bmod

公式

若n,m为整数，p为质数

\[C_{n}^{m}\bmod p= C_{n\bmod p}^{m\bmod p}\times C_{n/p}^{m/p}\bmod p \]

这个式子有什么作用呢，最简单的一种就是求组合数。
有时候n,m过大，可能是p的倍数，这时候n,m对于p没有逆元，自然没办法用费马小定理求逆元。这个时候我们就需要卢卡斯定理了

求组合数步骤

  • 1.求\(C_{n\bmod p}^{m\bmod p}\)
    n,m显然比p小，直接费马小定理求
  • 2.递归求\(C_{n/p}^{m/p}\)

就是这么简单，很好理解。

P3807 【模板】卢卡斯定理/Lucas 定理

模板题：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,p;
int t;
int pre[100010];

void prev(){//lucas()前面都是常规的费马小定理求组合数
	pre[0]=1;
	for(int i=1;i<=100000;i++){
		pre[i]=(pre[i-1]*i);
		pre[i]%=p;
	}
}

int qpow(int aa,int bb){
	int vl=1,hl=aa;
	hl%=p;
	while(bb){
		if(bb%2){
			vl*=hl;
			vl%=p;
		}
		hl*=hl;
		hl%=p;
		bb/=2;
	}
	return vl;
}

int C(int aa,int bb){
	if(aa<bb) return 0;
	int ans=pre[aa];
	ans*=qpow(pre[aa-bb],p-2);
	ans%=p;
	ans*=qpow(pre[bb],p-2);
	ans%=p;
	return ans;
}

int lucas(int aa,int bb){
	if(bb==0) return 1;
	int val=C(aa%p,bb%p);
	val*=lucas(aa/p,bb/p);
	val%=p;
	return val;
}

signed main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>p;
		prev();
		cout<<lucas(n+m,m)<<endl;
	}
	return 0;
}

POJ - 3219 Binomial Coefficients

这道题当然可以把模数设成2，直接求，看结果是0还是1，但是这样显得太没水平，也很无聊。
考虑有没有单次O(1)的做法。
我们回到卢卡斯定理的式子：

\[C_{n}^{m}\bmod p= C_{n\bmod p}^{m\bmod p}\times C_{n/p}^{m/p}\bmod p \]

观察前面一项，不难发现\(n\bmod p\)即为n在p进制下的最后一位，后一项递归下去的结果就是把n,m在p进制下的每一位拆出来，分别计算组合数并相乘。

有了这一点以后我们发现p=2,也就是n,m在p进制下的每一位都是0或1，其每一位的组合数只可能是下面几种：

1.\(C_{0}^{0}=1\)
2.\(C_{0}^{1}=0\)
3.\(C_{1}^{0}=1\)
4.\(C_{1}^{1}=1\)

于是我们发现只要出现存在\(C_{0}^{1}\),整体结果为0，否则为1。而\(C_{0}^{1}\)意味着2进制下有一位上n[i]=0,m[i]=1。

如果对于所有i使得m[i]=1,有n[i]=1,则一定有(n-m)&m==0（正好n-m把那些位置减掉了），此时结果为偶数，否则为奇数。

#include<iostream>
using namespace std;
int main(){
    int n,m;
    while(cin>>n>>m){
        if((n-m)&m) cout<<0<<endl;
        else cout<<1<<endl;
    }
}

HDU - 3304 Interesting Yang Yui Triangle

分析思路和上一题差不多。反方向计算不被p整除的数量。此时p进制下n的每一位，必定大于等于m这一位，否则其值为0（这是显然的，比如不可能从两个里选出三个），那么对于n的p进制下的每一位合法的m[i]满足0<=m[i]<=n[i]，再乘法原理把每一为的方案数相乘即可

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

int main(){
    int p,n;
    int cas=1;
    while(scanf("%d %d", &p, &n)!=EOF){
        if(p==0 && n==0) break;
        int sum=1;
        while(n){
            sum*=n%p+1;
            n/=p;
        }
        printf("Case %d: %04d\n", cas++, sum%10000);
    }
    return 0;
}

HDU - 3037 Saving Beans

题目里说的是不超过m颗松子，发现固定松子个数可以用插板法计算，列出计算公式:

\[\sum_{i=0}^{m} C_{i+n-1}^{n-1} \]

也就是这样一个式子：

\[c(n-1,n-1)+c(n,n-1)+...+c(n+m-1,n-1) \]

(c(i,j)表示\(C_{i}^{j}\))

我们人为凑一个\(c(n-1,n-2)\)上去（反正是0），就会发现可以一直杨辉三角合并下去（\(c(i,j)+c(i,j+1)=c(i+1,j+1)\)）,最后得到\(c(n+m,m)\)

#include<iostream>
#define int long long
using namespace std;
int n,m,p;
int t;
int pre[100010];

inline int read(){
	char ch;int x=0;bool f=false;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f) x=-x;
	return x;
}

void pref(int p){
	for(int i=1;i<=p;i++){
		pre[i]=pre[i-1]*i;
		pre[i]%=p;
	}
}

int qpow(int a, int b)//快速幂
{
	int res = 1;
	for(; b; b>>=1, a=a*a%p)
		res = res * (b&1?a:1) % p;
	return res;
}

int C(int aa,int bb){
	if(aa<bb) return 0; 
	int val=pre[aa];
	val*=qpow(pre[aa-bb],p-2);
	val%=p;
	val*=qpow(pre[bb],p-2);
	val%=p;
	return val; 
}

int lucas(int aa,int bb){
	if(bb==0) return 1;
	int val=C(aa%p,bb%p);
	val*=lucas(aa/p,bb/p);
	val%=p;
	return val;
}

int solve(int aa,int bb){
	if(aa<0 || bb<0) return 0;
	int sum=0;
	for(int i=0;i<=bb;i++){
		sum+=lucas(aa,i);
		sum%=p;
		sum+=lucas(aa,i+1);
		sum%=p;
		//sum-=lucas(aa,i+1);
		//sum+=p;
		//sum%=p;
	}
	return sum;
}

signed main(){
	//p=1000000000;
	//cout<<qpow(2,3)<<endl;
	pre[0]=1;
	t=read();
	while(t--){
		cin>>n>>m>>p;
		pref(p);
		cout<<lucas(n+m,m)<<endl;
	}
	return 0;
}

HDU - 5226 Tom and matrix

和上一题差不多的处理思路，每一列凑一个值，最后算出来只剩两项，再减去凑的值（作者一直T，好心人帮忙调调代码T^T）

#include<iostream>
#define int long long
using namespace std;
int a,b,c,d,p;
int pre[100010];

inline int read(){
	char ch;int x=0;bool f=false;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f) x=-x;
	return x;
}

void pref(int p){
	for(int i=1;i<=p;i++){
		pre[i]=pre[i-1]*i;
		pre[i]%=p;
	}
}

int qpow(int aa,int bb){
	int vl=1,hl=aa;
	hl%=p;
	while(bb){
		if(bb%2){
			vl*=hl;
			vl%=p;
		}
		hl*=hl;
		hl%=p;
		bb/=2;
	}
	return vl;
}

int C(int aa,int bb){
	if(aa<bb) return 0;
	if(bb==0) return 1;
	int val=pre[aa];
	val*=qpow(pre[aa-bb],p-2);
	val%=p;
	val*=qpow(pre[bb],p-2);
	val%=p;
	return val; 
}

int lucas(int aa,int bb){
	if(aa<p &&bb<p) return C(aa,bb);
	int val=C(aa%p,bb%p)*lucas(aa/p,bb/p);
	val%=p;
	return val;
}

signed main(){
	pre[0]=1;
	while(cin>>a>>b>>c>>d>>p){
		pref(p);
		if(p==1){
			cout<<0<<"\n";
			continue;
		}
		int ans=0;
		for(int i=b;i<=d;i++){
			ans+=lucas(c,i);
			ans+=lucas(c,i+1);
			ans-=lucas(a,i+1);
			ans+=p;
			ans%=p;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

标签：ch,int,定理,long,卢卡斯,include,bmod
From： https://www.cnblogs.com/wangwenhan/p/18025391

相关文章

  • 算术基本定理
    算术基本定理可表述为：任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为N的标准分解式。最早证明是由欧几里得给出的，由陈述证明。此定理可推广至更一般的交......
  • 带通采样定理
    对信号进行处理时，要通过采样、量化、编码将模拟信号转换为数字信号，其中采样最为关键，只有经过模数转换和数模转换后信号还能保持不变的通信才算完整可靠。采样定理说明了采样频率和信号频谱之间的关系，是模拟信号数字化的基本依据。低通采样定理（奈奎斯特采样定理）$$f_s\geq2f_h$......
  • 概率论中的60个概念和定理
    概念：1.概率（Probability）：描述事件发生的可能性大小的数值。通常用�(�)P(A)表示事件�A的概率，取值范围在0到1之间。2.随机变量（RandomVariable）：描述随机试验结果的数学对象。随机变量可以是离散型的（取值有限或可数无限）或连续型的（取值为某个区间）。3.概率分布（Probabilit......
  • 对二项式定理求导
    \[\begin{aligned}(x+1)^n&=\sum_{i=0}^n\binomnix^i\\(x+1)^n&=\sum_{i=0}^n\binomnix^i\\((x+1)^n)'&=(\sum_{i=0}^n\binomnix^i)'\\n(x+1)^{n-1}&=\sum_{i=0}^n\binomniix^{i-1}\\2^{n-1}n&=\sum_{i=0}^ni\bin......
  • Matrix-Tree 定理
    不会线性代数。行列式定义对一个\(n\timesn\)的矩阵\(A\)，其\(n\)阶行列式写作\(\mathrm{det}(A)\)或\(|A|\)，定义为\[\mathrm{det}(A)=|A|=\sum_{p}(-1)^{\tau(p)}\prod_{i=1}^{n}a_{i,p_i}\]所有的\(p\)形成\(1\)到\(n\)的全排列，\(\tau(p)\)表示排列\(p\)......
  • 修塔（gcd+裴蜀定理）
    第3题   修塔查看测评数据信息有编号1~n的n个塔,除了两个塔a和b是好的不用修以外,其他都需要重修。james和jordan展开修塔比赛，规则是轮流修，每次可以修第j+k或j-k号塔，其中j和k是已经修好的任意两个塔，如果不能修塔，就输了。给出n,a,b，从james开始，问最后谁赢了。 输入......
  • 伪随机数（gcd+裴蜀定理）
    第2题   伪随机数查看测评数据信息一个生成伪随机数的函数，seed(a+1)=[seed(a)+STEP]%MOD,为了能产生0~MOD-1的所有数,需要设定合适的STEP和MOD。例如,STEP=3，MOD=5，产生0,3,1,4,2，这是正确的设定;若STEP=15,MOD=20,只能产生0,15,10,5,这是错误的设定。 输入格式 ......
  • 数论-裴蜀定理
    原文 如果a与b均为整数，则存在整数x和y满足ax+by=(a,b)。由定理6容易证明正确性。 下面用扩展欧几里得算法(exgcd)求出满足ax+by=(a,b)的一个特解。例如：a=99,b=78,令d=(a,b)=(99,78)=3，求99x+78y=3的一个特解。在调用exgcd的时候，从后往前依次构造......
  • 费马小定理
    费马小定理如果\(p\)是质数，则对任意整数\(a\),有\[a^p\equiva(\bmod\p)\Rightarrow\gcd(a,p)=1\]前提：\(p\)是质数\(gcd(a,p)=1\)证明：有数列\(S=\{1,2,3,\cdotsp-1\}\)，将\(S\timesa\Rightarrow\{a,2a,3a,\cdots,(p-1)a\}\)\[(S\timesa)\bmod\......
  • [数论学习笔记01]完系/同余最短路/费马小定理/扩欧/中国剩余定理
    #[数论学习笔记01]完系/同余最短路/费马小定理/扩欧/中国剩余定理###每日蒟蒻小故事(1/1)蒟蒻带了一本崭新的笔记本到S组.他发现这一节课居然在学习数论."听不懂,求讲解!"蒟蒻说.大佬邪魅一笑,并未理会.蒟蒻只能一边听着老师的讲解,一边努力地记着笔记."什么是完全剩余系......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99