Catalan Number & Lucas定理 & 中國剩餘定理（CRT）

時間 2020-10-03 標籤 catalan number lucas 定理中國剩餘定理 crt

又雙叒叕來水數論了
今天來學習$Lucas \:\ \& \:\ Catalan Number$
二者有着密切的聯繫（固然還有CRT），因此放在一塊兒學習一下ios

Catalan Number

定義

卡特蘭數（Catalan Number）又稱卡塔蘭數，是組合數學中一個常常出如今各類計數問題中的數列
$1,2,5,14,42,132,429,1430,4862,16796,58786,208010,742900$
啊這
其實跟$Lucas$沒有什麼太大的聯繫
只有其中一個求$Catalan Number$的公式可能會用到$Lucas$定理算法

性質

上面提到說其中一個公式，也就是說求$Catalan Number$有不少方法數組

遞歸公式1

\[f(n) = \sum_{i=0}^{n-1}f(i)*f(n-i-1) \]

遞歸公式2

\[f(n)=\frac {f(n-1)*(4*n-2)} {n+1} \]

組合公式1（就是這個的分子可能會用到$Lucas$突然找不到手頭作過的那道題了）固然這個式子也是它的通項公式

\[f(n)= \frac {C_{2n}^n} {n+1} \]

組合公式2（同上）

\[f(n) = C_{2n}^n - C_{2n}^{n-1} \]

應用背景

通常用來解決一些現實問題，很複雜的題目被看破以後直接用公式算出來便可
舉個例子，合法的入棧出棧序列有多少種就是卡特蘭數。咱們能夠把0當作入棧操做，1當作出棧操做，即0的累計個數不小於1的排列有多少種。
還有不少其餘的問題都是卡特蘭數，如括號匹配，二叉樹的個數，有序樹的個數，多邊形分紅三角形的個數等。學習

n+1 個葉子節點的二叉樹的數量
ui
n*n的方格地圖中，從一個角到另一個角，不跨越對角線的路徑數
spa
n+2條邊的多邊形，能被分割成三角形的方案數
code

實現過程

來看一道例題作入門吧blog

題目描述

衆所周知，在中國古代算籌中，紅爲正，黑爲負……
給定一個$1*(2n)$的矩陣，現讓你自由地放入紅色算籌和黑色算籌，使矩陣平衡[即對於全部的$i(1<=i<=2n)$，使第$1-i$格中紅色算籌個數大於等於黑色算籌]
問有多少種方案知足矩陣平衡。遞歸

輸入格式

正整數 nget

輸出格式

方案數t對100取模

輸入輸出樣例

Input

Output

樣例解釋

紅黑紅黑
紅紅黑黑

solution

將紅看作入棧操做，黑看爲出棧操做，問題即爲求不一樣的合法的入棧出棧序個數
咱們能夠考慮用遞推式(1)求卡特蘭數，取模更容易

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    long long ctl[110],i,j,k,n;
    memset(ctl,0,sizeof(ctl));
    ctl[0]=ctl[1]=1;
    ctl[2]=2;
    scanf("%lld",&n);
    for(i=3;i<=n;++i)
        for(j=0;j<i;++j){
            ctl[i]+=ctl[j]*ctl[i-j-1];
            ctl[i]%=100;
        }
    printf("%lld\n",ctl[n]);
    return 0;
}

這裏只給出了第一個式子的應用，更多的請自行查找題進行思惟練習。

Lucas

定義&性質

$Lucas$定理是用來求 $ C_n^m mod p $ 的值。
其中$n$和$m$是非負整數，$p$是素數。
通常用於$m,n$很大而$p$很小，抑或是$n,m$不大可是大於$p$的狀況下來求結果。

用處&背景

目前咱們學過幾個用來求組合數的方法

最暴力的楊輝三角，用二維數組解決，複雜度 $O(n^2)$ 效率低下並且因爲數組的緣由只能處理很小的數據
將組合式$C_{n+m}^n \% mod$轉換爲$\frac {(m+n)!} {n! m!} \%mod$，因爲除法不能夠邊除邊取$mod$因此在處理分母的時候選用了費馬小定理，運用逆元的乘法解決。
看分子的話，$(m+n)!$在遍歷的時候如有元素$i>mod$，那麼取$mod$以後整個式子的值就會變成0，而$Lucas$的出現，就是爲了解決這一問題

引入

針對上述第二種狀況，咱們先來看一道例題

旗木雙翼

題目描述

菲菲和牛牛在一塊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 $

solution

能夠看到題目當中直接給出了$mod$爲一個大質數
並且$m+n$最大也才二十萬，遠遠小於$mod$的數值
因此不會出現取完$mod$爲$0$的狀況，因此運用逆元求解便可

\[C_{n+m}^m =\frac {(m+n)!} {n!*m!} \% mod \]

Code

#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$定理了

性質

性質1

\[Lucas(n,m,p)=cm(n\%p,m\%p)*Lucas(\frac n p,\frac m p,p) \]

\[Lucas(x,0,p) =1 \]

其中

\[cm(a,b)=a!*(b!*(a-b)!)^{p-2} (mod \:\ p) \]

$ :\ :\ :\ :\ :\ :\ :\ :\ :\ $ $(a-b)!^{p-2}$爲$a-b$的逆元，因此能夠除一下把式子變成

\[(a!/(a-b)!)*(b!)^{p-2}(mod \:\ p) \]

性質2

\[C_n^mmod p\equiv C_{n\mod p}^{m\mod p}*C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}mod p \]

就是一個$a,b$能夠拆成$P$進制下的乘積

證實

目標方程：

\[\dbinom n m\equiv\dbinom {n\%p} {m\%p} \dbinom {n/p}{m/p}(mod p) \]

顯然右側能夠遞歸處理，咱們只須要推左邊就好
證實過程：
設

\[n=sp+q,m=tp+r,(q,r<p) \]

則目標方程變成

\[\dbinom {sp+q} {tp+r} \equiv \dbinom {s} {t} \dbinom {q} {r} (mod p) \]

下面利用二項式定理&費馬小證實一個引理

\[(1+x)^n \equiv (1+x)^{ps} * (1+x)^q (mod \:\ p) \]

\[(1+x)^n\equiv[\sum_{t=0}^p \dbinom p i x^i]^s(mod \:\ p) \]

根據上面的那個性質

\[\equiv (1+x)^q*(1+x^p)^s(mod p) \]

\[\equiv \sum_{i=0}^s \binom s i x^{pt} * \sum_{j=0}^q \binom q j x^j(mod p) \]

則有

\[(1+x)^{sp+q} \equiv\sum_{i=0}^s \binom s i x^{pt} * \sum_{j=0}^q\binom q j x^j(mod p) \]

\[\sum_{k=0}^{sp+q}\binom {sp+q} {k} x^k\equiv\sum_{i=0}^s \binom s i x^{pt} * \sum_{j=0}^q\binom q j x^j(mod p) \]

左邊$x^{tp+r}$的係數爲$\binom {sp+q}{tp+r}$

右邊$x^{tp+r}$的係數爲$\binom s t\binom q r$

故係數相等，原命題得證