又双叒叕来水数论了
今天来学习\(Lucas \:\ \& \:\ Catalan Number\)
两者有着密切的联系（当然还有CRT），所以放在一起学习一下
证明\(Lucas\)几乎花了半天的时间，呼，终于懂了
希望读者能有收获
有疑问评论区见，蟹蟹
\(Lucas\) 定理是用来求 \(C_n^m mod p\) 的值。
其中\(n\)和\(m\)是非负整数，\(p\)是素数。
一般用于\(m,n\)很大而\(p\)很小，抑或是\(n,m\)不大但是大于\(p\)的情况下来求结果。
目前我们学过几个用来求组合数的方法
针对上述第二种情况，我们先来看一道例题
菲菲和牛牛在一块n行m列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。
棋局开始时，棋盘上没有任何棋子，两人轮流在格子上落子，直到填满棋盘时结束。落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。
_Itachi听说有不少学弟在省选现场AC了D1T1，解决了菲菲和牛牛的问题，但是_Itachi听说有的人认为复杂度玄学，_Itachi并不想难为学弟学妹，他想为大家节约时间做剩下的题，所以将简化版的D1T1带给大家。
_Itachi也在一块n行m列的棋盘上下棋，不幸的是_Itachi只有黑棋，不过幸好只有他一个人玩。现在，_Itachi想知道，一共有多少种可能的棋局（不考虑落子顺序，只考虑棋子位置）。
_Itachi也不会为难学弟学妹们去写高精度，所以只需要告诉_Itachi答案mod 998244353（一个质数）的结果。
第一行包括两个整数n,m表示棋盘为n行m列。
一个整数表示可能的棋局种数。
10 10
184756
对于 \(20\%\)的数据$n,m \leq10 $
对于 \(30\%\)的数据$n,m\leq20 $
另有 \(20\%\)的数据$n\leq5 $
另有 \(20\%\)的数据$m\leq5 $
对于\(100\%\)的数据$n,m\leq100000 $
可以看到题目当中直接给出了\(mod\)为一个大质数
而且\(m+n\)最大也才二十万，远远小于\(mod\)的数值
所以不会出现取完\(mod\)为\(0\)的情况，所以运用逆元求解即可
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
inline int read(){
int x = 0, w = 1;
char ch = getchar();
for(; ch > ‘9‘ || ch < ‘0‘; ch = getchar()) if(ch == ‘-‘) w = -1;
for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) x = x * 10 + ch - ‘0‘;
return x * w;
}
const int mod = 998244353;
inline int power(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = (ans % mod) * (a % mod) % mod;
a = (a % mod) * (a % mod) % mod;
b >>= 1;
}
ans %= mod;
return ans;
}
signed main(){
int n = read(), m = read();
int tmp = 1;
for(int i = m + n; i >= 1; i--){
tmp *= i;
tmp %= mod;
}
int n1 = 1;
int m1 = 1;
for(int i = 1; i <= n; i++){
n1 *= i;
n1 %= mod;
}
for(int i = 1; i <= m; i++){
m1 *= i;
m1 %= mod;
}
int ans = (tmp % mod) * power(n1 ,mod - 2) % mod * power(m1, mod - 2) % mod;
ans %= mod;
cout << ans << endl;
return 0;
}
如果\(mod\)很小
上述算法显然在求阶乘的时候会变成\(0\)
这就需要\(Lucas\)定理了
其中
\((a-b)!^{p-2}\)为\(a-b\)的逆元，所以可以除一下把式子变成
就是一个\(a,b\)可以拆成\(P\)进制下的乘积
目标方程：
显然右侧可以递归处理，我们只需要推左边就好
证明过程：
设
则目标方程变成
下面利用二项式定理&费马小证明一个引理
根据上面的那个性质
则有
左边\(x^{tp+r}\)的系数为\(\binom {sp+q}{tp+r}\)
右边\(x^{tp+r}\)的系数为\(\binom s t\binom q r\)
故系数相等，原命题得证
即
即
（以上证明结束）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
inline int read(){
int x = 0, w = 1;
char ch = getchar();
for(; ch > ‘9‘ || ch < ‘0‘; ch = getchar()) if(ch == ‘-‘) w = -1;
for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) x = x * 10 + ch - ‘0‘;
return x * w;
}
int n, m, p;
inline int power(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = (ans % p) * (a % p) % p;
a = (a % p) * (a % p) % p;
b >>= 1;
}
ans %= p;
return ans;
}
inline int getc(int n, int m){
if(n < m) return 0;
if(m > n - m) m = n - m;
int s1 = 1, s2 = 1;
for(int i = 0; i < m; i++){
s1 = s1 * (n - i) % p;//(n-m)!/n!
s2 = s2 * (i + 1) % p;//m!
}
return s1 * power(s2, p - 2) % p;
}
inline int lucas(int n, int m){
if(m == 0) return 1;
return getc(n % p, m % p) * lucas(n / p, m / p) % p;
}
signed main(){
int t = read();
while(t--){
n = read(), m = read(), p = read();
cout << lucas(n + m, m) << endl;
}
return 0;
}
Lucas定理 & Catalan Number & 中国剩余定理（CRT）
原文：https://www.cnblogs.com/rui-4825/p/13340278.html