Lucas(卢卡斯)定理

栏目: IT技术 · 发布时间: 4年前

内容简介:$$C_n^m\%p=C_{n/p}^{m/p}*C_{n\%p}^{m\%p}\%p~~(p为素数)$$解析:m个相同的豆子,放到n个不同的树里,有多少种方法。有$C_{n+m}^m$种。具体详解请看下面的扩展中的插板法。

公式

$$C_n^m\%p=C_{n/p}^{m/p}*C_{n\%p}^{m\%p}\%p~~(p为素数)$$

代码如下

typedef long long ll;
ll mod_pow(ll x, ll n, ll mod)
{
	ll res = 1;
	while (n > 0)
	{
		if (n & 1)
			res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}
ll comb(ll n, ll m, ll p)
{
	if (m > n)
		return 0;
	ll a = 1, b = 1;
	m = min(n - m, m);
	while(m)
	{
		a = (a * n--) % p;
		b = (b * m--) % p;
	}
	return a * mod_pow(b, p - 2, p) % p;
}
ll Lucas(ll n, ll m, ll p)
{
	if (m == 0)
		return 1;
	return comb(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

例题

HDU 3037

解析:m个相同的豆子,放到n个不同的树里,有多少种方法。有$C_{n+m}^m$种。具体详解请看下面的扩展中的插板法。

代码如下:

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll mod_pow(ll x, ll n, ll mod)
{
	ll res = 1;
	while (n > 0)
	{
		if (n & 1)
			res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}
ll comb(ll n, ll m, ll p)
{
	if (m > n)
		return 0;
	ll a = 1, b = 1;
	m = min(n - m, m);
	while(m)
	{
		a = (a * n--) % p;
		b = (b * m--) % p;
	}
	return a * mod_pow(b, p - 2, p) % p;
}
ll Lucas(ll n, ll m, ll p)
{
	if (m == 0)
		return 1;
	return comb(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}
int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll T, n, m, p;
	cin >> T;
	while (T--)
	{
		cin >> n >> m >> p;
		cout << Lucas(n + m, m, p) << endl;
	}
	return 0;
}

Lucas(卢卡斯)定理

扩展

插板法

适用类型

一组相同的元素,分成若干不同的组,每组至少一个元素。

例题1

将8个相同的小球放到3个不同的盒子,每个盒子至少放一个球,一共有多少种方法。

解:8个盒子,有7个空,分到3个盒子,需要插2块板,$C_7^2=21$种。

对于不满足 每组至少一个元素 条件的,应该先 转化为标准形式。

例题2

将8个相同的小球放到3个不同的盒子,每个盒子至少放两个球,一共有多少种方法。

解析:先往每一个盒子里放一个小球。转化为:5个相同的小球放到不同的盒子,每个盒子至少放1个小球,一共有多少种方法。$C_4^2=6$种。

例题3

将8个相同的小球放到3个不同的盒子,有多少种方法。

解析:我们先让每个盒子吐出1个球,使得每个盒子至少一个球,分球的时候再让盒子吃回去。转化为:11个相同的球放到3个不同的盒子中,每个盒子至少一个,有多少种方法。$C_{10}^2=45$种。

例题4

$a+b+c=10$有多少组正整数解。

解析:转化为:10个相同的小球,放到不同的3个盒子中,每个盒子至少一个,有多少方法。$C_9^2=36$种。

例题5

$a+b+c=10$有多少组非负整数解。

解析:转化为:13个相同的小球,放到不同的3个盒子中,有多少方法。$C_{12}^2=66$种。

例题6

$a+b+c\leqslant 10$有多少组非负整数解。

解析1:转化为$a+b+c+d =10$,即10个相同的球,放到4个不同的盒子中,有多少方法。$C_{13}^3=286$种。

解析2:列举所有情况:$a+b+c=0(C_2^2)$,$a+b+c=1(C_3^2)$,$\cdots$,$a+b+c=10(C_{12}^2)$,$\sum\limits_{i=2}^{12}C_i^2=C_{13}^3=286$种。

注:$\sum\limits_{i=m}^nC_i^m=C_{n+1}^{m+1}$。

杨辉三角性质之一:斜线上数字的和等于其向左(从左上方到右下方的斜线)或向右拐弯(从右上方到左下方的斜线),拐角上的数字。


以上所述就是小编给大家介绍的《Lucas(卢卡斯)定理》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

自制搜索引擎

自制搜索引擎

[日]山田浩之、[日]末永匡 / 胡屹 / 人民邮电出版社 / 2016-1 / 39.00元

《自制搜索引擎》聚焦于Google和Yahoo!等Web搜索服务幕后的搜索引擎系统,首先讲解了搜索引擎的基础知识和原理,接着以现实中的开源搜索引擎Senna/Groonga为示例,使用该引擎的源代码引导读者亲自体验搜索引擎的开发过程。这部分讲解涉及了倒排索引的制作和压缩、检索的处理流程以及搜索引擎的优化等内容。又简单介绍了一些更加专业的搜索引擎的知识和要点,为读者今后进一步学习打下了基础。本书适合......一起来看看 《自制搜索引擎》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具