lucas定理 学习笔记
目录介绍
lucas定理用于解决形如 \(C_n^m \mod p (p\in prime)\) 的问题。
设 \(n,m\) 用 \(p\) 进制来表示为：\((n_an_{a-1}\cdots n_0)_p , (m_am_{a-1}\cdots m_0)_p\)
则：
\[C_n^m = C_{n_a}^{m_a}*C_{n_{a-1}}^{m_{a-1}}\cdots C_{n_0}^{n_0} \]例如下面这道题 oj
combination
题目描述
LMZ有n个不同的基友，他每天晚上要选m个一起玩，而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢？当然，LMZ的一年有10007天，所以他想知道答案mod 10007的值。(1<=m<=n<=200,000,000)
输入格式
第一行一个整数t，表示有t组数据。(t<=200) 接下来t行每行两个整数n, m，如题意。
输出格式
T行，每行一个数，为C(n, m) mod 10007的答案。
样例
输入样例1
4
5 1
5 2
7 3
4 2
输出样例2
5
10
35
6
分析
显然，答案就是：\(C_n^m \mod 10007\)
但是我们的 \(fac[] , inv[]\) 开不了200,000,000，
所以我们就可以用 lucas 定理减小空间
code
#include <bits/stdc++.h>
#define LL long long
#define fu(x , y , z) for (int x = y ; x <= z ; x ++)
#define fd(x , y , z) for (int x = y ; x >= z ; x --)
using namespace std;
const int mod = 10007;
LL fac[mod + 5] , inv[mod + 5] , n , m;
LL ksm (LL x , LL y) {
if(!y)
return 1;
long long z = ksm (x , y / 2);
z = z * z % mod;
if (y & 1)
z = z * x % mod;
return z;
}
void pre () {
fac[0] = fac[1] = 1;
for(int i = 2 ; i <= mod - 1 ; i++)
fac[i] = fac[i - 1] * i % mod;
inv[mod - 1] = ksm (fac[mod - 1] , mod - 2);
for (int i = mod - 2 ; i >= 0 ; i --)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
LL C (LL x , LL y) {
if (x < y) return 0;
if (!y || x == y) return 1;
return fac[x] * inv[y] % mod * inv[x - y] % mod;
}
LL lucas (LL x , LL y) {
if (x < y) return 0;
if (!y) return 1;
if (x < mod && y < mod) return C (x , y);
return lucas (x / mod , y / mod) * C (x % mod , y % mod) % mod;
}
int main () {
pre ();
int T;
scanf ("%d" , &T);
while (T --) {
scanf ("%lld%lld" , &n , &m);
printf ("%lld\n" , lucas (n , m));
}
}
扩展lucas
未完待续
标签：inv,return,lucas,定理,样例,笔记,LL,mod From： https://www.cnblogs.com/2020fengziyang/p/17432748.html