【學習筆記】2021.10.5 - 清北學堂數論講解

ExGcd

gcd

輾轉相除法，即\(\gcd(a,b)=\gcd(b,a \mod b)\)。

lcm

\(lcm(a,b)=\frac{a \times b}{\gcd(a,b)}\)。

ExCrt

Excrt求解核心（合并方程）

大數翻倍法

void merge(int a1,int p1,int a2,int p2){
//x%p1=a1
//x%p2=a2
//x%p=a
  if(p1<p2) swap(a1,a2),swap(p1,p2);
//最壞複雜度是未翻倍的數，以上操作使得複雜度變為min(p1,p2) 
  int x=a1;
  while(x%p2!=a2) x+=p1;
//在方程一中，x對p1取模，是以加一點p1也無所謂，可以一隻加p1直到它滿足p2為止 
  return x%lcm(p1,p2); 
}
//卡掉以上代碼：當且僅當隻有兩個1e9以上的大質數      

計算取模（組合數）

n,m\(\leq\)2000,p不限

暴力。

n\(\leq 10^9\),m\(\leq 10^3\),p=\(10^9+7\)

逆元。

n\(\leq 10^9\),m\(\leq 10^3\),p=任意數

對于兩個階乘，暴力枚舉并約分，然後計算所有數的積。

n,m\(\leq 10^9\),p\(\leq\)100

使用盧卡斯定理，将n和m拆分成p進制，使得逆元得以産生，拆分後低位對齊，高位補零，然後對于每一位進行對應地運算。

容斥原理

給定若幹集合的大小及若幹集合交的大小，求若幹集合并的大小。

顯然，\(S_1 \bigcup S_2 = S_1+S_2-S_1 \bigcap S_2\) ，容斥原理的核心思想正是如此。

公式：\(\bigcup\limits_{1\le i\le n} S_i=\sum\limits_{S\in\left\{S_1,S_2,\cdots,S_n\right\}}{(-1)}^{\left|S\right|+1}\left|\bigcap\limits_{S_i\in S}S_i\right|\)

例1.n夫妻問題

現有n對夫妻做成一圈，對于每個方案（旋轉後相同認為是同一方案），要求沒有任意一對夫妻相鄰。

n對夫妻随便坐

圓排列，方案為\((2n-1)!\)。

處理

強制把一對夫妻綁在一起，此時這兩個人可以視為一個機關，那麼這些機關随便坐的方案為\((2n-1)!\)。

是以，拎出一對夫妻綁在一起再随便坐的方案為 \(C^m_n \times (2n-1)! \times 2^1\)。

但是，兩對夫妻綁在一起的會被減去兩次，要加回來。

然後，三對的會多加一次，要減回去。

四次加回來，五次減回去……

然後就是容斥，最終公式為 \(\sum\limits^n_{i=0}{C^m_n \times (2n-1-i)! \times 2^i \times (-1)^i}\)。

例2.FoxJumping

給定一個大小為\(n \times m\)的矩陣，要你從\((0,0)\)走R步到\((n,m)\)，每次可以從\((x,y)\)走到\((x+d_x,y+d_y)\)，要求 \(0 \leq d_x \leq T_x\)，\(0 \leq d_y \leq T_y\)，\(d_x+d_y \neq 0\) 且 \(\forall 1 \leq i \leq k,(d_{x_i},d_{y_i}) \neq (10 \times z_i,10 \times z_i) \)，\(n,m \leq 800\)。

設\(f[R][N]\)表示走R步x軸走到n的方案，\(g[R][M]\)表示走R步y走到m的方案（不考慮是否合法），最終總方案就是\(f[R][N] \times g[R][M]\)。

接下來考慮隻走不合法步驟的路徑，設 \(h[i][z]\) 表示隻走i步不合法，走到 \( (10 \times z_i,10 \times z_i) \) 的方案數。

是以總不合法的方案數為\(\sum\limits^k_{i=0}{(-1)^i \sum\limits^{\frac{min(n,m)}{10}}_{z=0}{h[i][z]}\times f[k-i][N-10z]\times g[k-i][M-10z]}\)。（i步不合法到某個\(z_i\)的位置的方案乘上剩下的步數的合法的方案）

​