# Python-LeetCode 581 第七招 Math
本單元中介紹一些LeetCode中與「算術」有關的常見題型與需要的知識，這些大致可歸到數論與排列組合的範圍，包含質數篩檢、因數分解、最大公因數與最小公倍數、排容原理、排列組合以及快速冪與乘法反元素。以下我們以LeetCode中的題目為範例來講解所需的知識與技巧。
## 質數與因數分解
### 質數篩檢
在下面這題裡，我們要計算某數$n$以下(不含$n$)有幾個質數，是個質數篩檢的裸題。
[(題目連結) 204. Count Primes (Medium)](https://leetcode.com/problems/count-primes/)
質數篩檢是個很基本的問題，如果要問一個數字$n$是否是質數，我們可以從2開始做試除，嘗試找可以整除它的因數，如果找到因數，它就不是質數；反之如果找不到，就是質數。
```python=
for i in range(2,upper):
if n%i==0: return False
return True
```
從2開始，那要找的上限upper要給多少呢？這會直接影響執行效率。最天真的方法是$upper=n$；動一下腦筋會發現只要$upper = n//2+1$ 就可以了；仔細想一下，$upper = n**0.5+1$就夠了，因為如果$n=pq$，則$min(p,q)\leq \sqrt{n}$。
現在的狀況類似的略有不同，我們不是只要檢測一個數字是否為質數，而是要找出$n$以下的所有質數。如果直接用上面的方法對每一個數字做檢測，那麼需要的時間是$\sum_{i=2}^{n}\sqrt{i} = O(n^{3/2})$。
以下是[Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)篩檢質數的方法，其作法與道理很簡單。
我們準備好一張表格prime[$i$]表示$i$是否為質數，初始時全部設為1。位置[0]與[1]我們不裡它。從2開始，當我們碰到的數字是質數時，我們將它的倍數全部打叉註記為非質數。程式寫起來就像下面這樣。它的時間複雜度比較不容易精算，直接看起來有點嚇人，雙迴圈好像會跑到$O(n^2)$，但是沒那麼糟，因為只有質數才會做內迴圈，如果用粗估，內迴圈次數顯然不會多過$\sum_{i=2}^n \frac{n}{i} = O(n\log n)$。事實上，因為質數很稀疏，有人算出來它是$O(n\log\log n)$，這非常接近$O(n)$了。請注意$\log\log n$是$\log(\log(n))$，當$n=2^{64}$時，$\log\log n = 6$。
```python=
class Solution:
def countPrimes(self, n: int) -> int:
prime = [1]*n
for i in range(2,min(n,int(n**0.5)+2)):
if prime[i]:
for j in range(i+i,n,i):
prime[j] = 0
#end for
return sum(prime[2:])
```
### 質因數分解
我們要把一個整數做質因數分解時，直覺的方法是找出它的因數，再從中挑選質數。但這個方法並不好，我們可以用把它的因數從中**抽離**的概念來做。
若$p$是已經找到的$n$一個質因數，$n=pq$，那麼將$n$分解只需要再將$q$分解就可以了。
由$p=2$開始，我們檢測$p$是否是$n$的因數，保持以下迴圈不變性：$n$已經沒有小於$p$的因數，那麼，若$p$整除$n$，則$p$必為質數，否則$p$的因數必然可以整除$n$。以下是範例程式。
```python=
n = 24*5*5*19*7*7 # sample to test
result = [] # (prime, power)
p = 2
while p*p <= n:
i = 0
while n%p == 0:
n //= p
i += 1
if i: result.append((p,i))
p += 1
if n>1: result.append((n,1))
print(result)
```
下面這一題是質因數分解的直接應用，只是從題目也許不容易看出來題目要求的是什麼。
[(題目連結) 650. 2 Keys Keyboard (Medium)](https://leetcode.com/problems/2-keys-keyboard/)
題目是說一開始只有一個'A'，你只允許做下面兩種操作
1. 將目前的字串全部複製
2. 將複製的字串貼上
請問最少要幾次操作才能將字串變成$n$個'A'。最簡單的方法是複製之後貼上$n-1$次，那麼操作次數就是$n$，但不一定是最少次數。
定義$f(n)$所求最少次數。假設$n=pq$，我們先做出長度$p$，然後複製後貼上$q-1$次，那麼操作次數的遞迴式是
$$
f(n)=f(p)+1+(q-1)=f(p)+q
$$
當$p,q>1$且為整數時，我們很容易知道
$$
\begin{eqnarray}
&& (p-1)(q-1)> 0 \\
&\Rightarrow& pq-p-q \geq 0 \\
&\Rightarrow& pq \geq p+q
\end{eqnarray}
$$
也就是**能分解時就分解**會帶給我們最少的次數。
因此我們要做的就是將$n$做質因數分解，所求的答案就是質因數總和，但同一個質因數如果有大於一次，則每次都要加入答案中。例如$n = 3^3\times 7\times 13^2$，則答案就是$3\times 3+7+13\times 2=42$。以下是範例程式，與上面的質因數分解非常類似。
```python=
class Solution:
# n=p*q, f(n)=f(p)+1+(q-1), make p and copy q-1 times
# Then, answer is the sum of prime factors
def minSteps(self, n: int) -> int:
ans = 0
i = 2
while n>1 and i+i<=n:
while n%i==0:
ans += i
n //= i
i += 1
if n>1: ans += n
return ans
```
下面這一題有結合一些其他的技巧。
[(題目連結) 2521. Distinct Prime Factors of Product of Array (Medium)](https://leetcode.com/problems/distinct-prime-factors-of-product-of-array/)
題目是說有一個正整數陣列，請算出如果把這些數全部相乘之後，這個乘積有幾個相異的質因數。基本上要找出每一個數字的質因數，因為要找相異質因數的個數，所以重複相同的沒有意義，所以本質上是把每一個數字的質因數求聯集。
我們再看一下所給的參數範圍，有點怪。陣列長度可能達到$10^4$，但其中的數字在$[2,1000]$這個小區間。顯然當陣列大的時候會有很多重複的數字，我們應該要技巧的避免重覆計算。
要賴乾脆賴到底，我們在class之外把範圍內的數字全部做質因數分解後建表，以集合方式儲存。輸入進來之後，直接把每個數字的質因數聯集起來，其個數就是答案。
建表所用的方法與質數篩檢很像，找到質數時，將它的倍數設為非質數，同時把自己加入到它的質因數集合內。以下是範例程式。
```python=
pf = [set() for i in range(1001)]
prime = [True]*1001
for i in range(2,1001):
if not prime[i]: continue
pf[i].add(i)
for j in range(i+i,1001,i):
pf[j].add(i)
prime[j] = False
class Solution:
def distinctPrimeFactors(self, nums: List[int]) -> int:
mypf = set()
for k in nums:
mypf |= pf[k]
return len(mypf)
```
### LeetCode中的ugly number
LeetCode有好幾題都是以ugly number為名，跟因數是有關聯的，以下來看看這幾題。
這裡定義所謂Ugly number是質因數只有2,3,5的正整數，也就是由若干(可能0)個2、3、與5相乘所得到的數，例如1、6、20都是ugly number，但14不是。
[(題目連結) 263. Ugly Number (Easy)](https://leetcode.com/problems/ugly-number/)
第一個上場的是一個簡單題。本題中，輸入一個整數$n$，判斷它是否是ugly number。這題很簡單，不必去想著將$n$因數分解，我們只要把$n$的2,3,5的因數一直**拿掉**，如果會變成1，就是ugly number，否則便不是。
以下是範例程式。因為輸入可能是負的，我們先把負整數特判掉。接著跑一個迴圈把$p=2,3,5$都處理一次：當$n$可以被$p$整除時，就將它們相除，也就是把$p$從$n$中拿掉一次的意思。
```python=
class Solution:
def isUgly(self, n: int) -> bool:
if n<=0: return False
for p in (2,3,5):
while not n%p:
n //= p
return n==1
```
時間複雜度是$n$所擁有2,3,5因數的個數，不超過$O(\log n)$。接下來看一個稍微難一點的題目。
[(題目連結) 264. Ugly Number II (Medium)](https://leetcode.com/problems/ugly-number-ii/)
本題要找第$n$個ugly number，其中$1 \leq n \leq 1690$。
以下我們說明一種在$O(n)$時間複雜度可以找出第$n$個ugly number的方法。根據的是以下簡單的事實，假設$ugly[i]$表示第$i$個ugly number：
* $ugly[i]$一定是由2, 3 或5乘上$ugly[j]$，對於某個$j<i$。
我們將依序產生$ugly[i]$，在產生第$i$個時，對於2,3與5我們各紀錄一個$index$，$index(p) = k$ 表示$ugly[k-1]\times p < ugly[i]$，已經產生過了，而$ugly[k]\times p \geq ugly[i]$是第$i$個的候選人，其中$p\in \{2,3,5\}$。
每一回合我們在三個候選人中挑出最小的擔任第$ugly[i]$，對於被選任的候選人，我們要將他的繼任數字當作下一個的候選人。請注意，三位候選人中可能會有相同的，此時都需要將其移除並改下一任當候選人。以下用前幾個ugly number來演繹此程序，其中cand(2)表示2推出的候選人，候選人第一次出現時，其後方的括弧內是它所乘上的是第幾個ugly，例如4(2)是由2乘以ugly[2]。
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7|8|
| ---- | --|---|--- | - |-|-|-|-|
| ugly[i] | 1 | 2 | 3 | 4 | 5 | 6 |8|9|
|cand(2)| 2(1) | 4(2) | 4 | 6(3) | 6 | 8(4) |10(5)|10|
|cand(3)| 3(1) | 3 | 6(2) | 6 | 6 | 9(3) |9|12(4)|
|cand(5)| 5(1) | 5 | 5 | 5 | 10(2) | 10 |10|10|
以下是此程序的範例程式。
```python=
class Solution:
def nthUglyNumber(self, n: int) -> int:
ugly = [1]
p = [2,3,5]
cand = [2,3,5] # candidate for next ugly
idx = [1,1,1] # index to multiply
for it in range(n-1):
v = min(cand)
ugly.append(v)
for i in range(3): # possible duplicate
if cand[i]==v:
cand[i] = p[i]*ugly[idx[i]]
idx[i] += 1
return ugly[n-1]
```
時間複雜度$O(n)$，因為每一回合只是在三個數中挑選最小值，然後更新idx與cand。
醜一醜二不夠，下面這題是超級醜。
[(題目連結) 313. Super Ugly Number (Medium)](https://leetcode.com/problems/super-ugly-number/)
本題中將質因數不只侷限於2,3,5，而是輸入若干個質數，質因數都在給定的質數中的數字都稱為超級醜的數字。題目要求第$n$個超級醜的數字。這題用前一題的方法來做就可以了，只是質數擴充成不定個數。
時間複雜度是$O(nm)$，其中$n$是所求第$n$個，$m$是所給的質數個數。
```python=
class Solution:
# generate ugly one by one
# for each prime p, keep the next smallest ugly it should multiplies
# without PQ
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
ugly = [1] # generated
m = len(primes)
# candidate (value, from), list but not PQ
cand = primes[:]
inext = [1]*m # next to multiply
for it in range(1,n):
q = min(cand) # smallest in candidate
ugly.append(q)
for i in range(m): # possible duplicate
if cand[i] != q: continue
cand[i] = primes[i]*ugly[inext[i]]
inext[i] += 1
return ugly[-1]
```
所給的質數個數可能達到100，所以用PQ(優先佇列)來找候選人中的最小值可以加快速度，最小值有相同的時候都會出現在PQ的頂端，所以只要將PQ頂端等於最小值的都替換掉就好了。因為要知道候選人是誰推出的，我們放入PQ中的是一個tuple，第一欄位放值，第二欄位放它是誰推出的。
```python=
class Solution:
# generate ugly one by one
# for each prime p, keep the next smallest ugly it should multiplies
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
ugly = [1] # generated
# candidate (value, from), PQ
cand = [(p,i) for i,p in enumerate(primes)]
inext = [1]*len(primes) # next to multiply
for it in range(1,n):
q,pi = cand[0] # smallest in candidate
ugly.append(q)
while cand[0][0]==q: #pop duplicate
_,i = heappop(cand)
heappush(cand,(primes[i]*ugly[inext[i]],i))
inext[i] += 1
return ugly[-1]
```
## GCD and LCM
### 輾轉相除法(Euclidean algorithm)與Python函數
最大公因數(GCD)與最小公倍數(LCM)常出現在數論問題中。最大公因數的求法一般來說可以用質因數分解以及輾轉相除法。其中輾轉相除在基礎程式教學中，更是常常被用來當學習while迴圈與遞迴的範例。不過近年來好像許多中學生在中學並未學過(用紙筆)做輾轉相除法，讓很多大學教程式的老師(包含我)覺得疑惑。
輾轉相除法的道理很簡單:
「若$x$除以$y$得商$q$餘數$r$，也就是$x = q\times y+r$，則$\text{gcd}(x,y) = \text{gcd}(y,r)$。另，對任意正整數$x$，$\text{gcd}(x,0) = x$。
以遞迴來寫就直接照定義
```python
def gcd(x,y):
if y==0: return x
return gcd(y,x%y)
```
以Python 的while迴圈來寫，非常簡潔：
```python
def gcd(x,y):
while y:
x,y = y,x%y
return x
```
輾轉相除法跑起來很快，時間複雜度是log，從二進制去想很簡單，做兩次至少會減少一位。
最小公倍數LCM可以根據以下簡單的事實來計算，$x\times y=\text{gcd}(x,y)\times \text{lcm}(x,y)$。
Python目前在math中有現成的math.gcd與math.lcm可以直接叫用。允許多個輸入整數。以下是一些基本用法。
```python
import math
print(math.gcd(12,20),math.lcm(12,20))
print(math.gcd(60,150,200),math.lcm(60,150,200))
p = list(range(6,1000,6))
print(math.gcd(*p),math.lcm(*p))
```
### GCD範例
[(題目連結) 2447. Number of Subarrays With GCD Equal to K](https://leetcode.com/problems/number-of-subarrays-with-gcd-equal-to-k/description/)
這一題是GCD的直接運用裸題。給一個陣列以及一個整數$k$，請問有多少子陣列的GCD恰好等於$k$。陣列長度$\leq 1000$。
枚舉所有可能的左端，對於每一個左端，從小到大嘗試可能的右端，對於左右端之間的視窗，檢視目前的GCD，如果GCD已經不是$k$的倍數就可以終止這個左端的搜尋。請留意，右端滑動一格時，新的GCD可以由原來的GCD與新元素再取GCD，而不必把視窗內的元素全部都丟進math.gcd()內計算。
時間複雜度$O(n^2)$，但多數例子視窗範圍不會跑到底。
```python=
class Solution:
# enumerate each left, sweeping right until gcd not qk
# O(n^2)
def subarrayGCD(self, nums: List[int], k: int) -> int:
cnt,n = 0,len(nums)
for i in range(n):
curr_gcd = nums[i]
if curr_gcd==k: cnt += 1
j = i # [i,j]
while j<n-1 and curr_gcd%k==0:
j += 1
curr_gcd = gcd(curr_gcd,nums[j])
if curr_gcd==k: cnt += 1
#
return cnt
```
下面的題目中我們要做分數的加減法，分母通分時需要用到GCD與LCM。
[(題目連結) 592. Fraction Addition and Subtraction (Medium)](https://leetcode.com/problems/fraction-addition-and-subtraction/description/)
分數的加減法並不困難，這題的輸入與輸出都是字串的格式，要依照題目的輸入與輸出格式來處理也是需要一些字串操作的技巧。兩個分數相加減，就是將它們通分，然後把分子與分母的最大公因數約掉，所以需要用到gcd。我們可以將分數加減寫成一個副程式，初始一個分數$res=\frac{0}{1}$，然後將輸入字串中的分數一一解析出來與$res$相加。這裡我們每一個分數以一個tuple (分子,分母)來儲存表示。
要將字串中的分數抓出來有多種方式，以下我們利用python的string.split()來做。首先因為輸入中有加有減，我們將每一個'-'之前都多補上一個'+'，這樣全部都是相加，原來相減的變成後面取負值。如此做的原因是接下來我們可以用split('+')來將輸入字串切割成一個一個的term，每一個term是形如'2/5'或'-3/7'的樣子，我們再用split('/')將它的分子分母切開後分別轉整數，就可以得到我們需要的格式。要稍微留意，如果輸入的第一項是負的，我們的轉換後第一項會切割出一個空字串，所以要把它跳過。
以下是範例程式。
```python=
class Solution:
def fractionAddition(self, expression: str) -> str:
def fadd(p,q): # frac addition p[0]/p[1]+q[0]/q[1]
num = p[0]*q[1]+p[1]*q[0]
den = p[1]*q[1]
g = gcd(num,den)
return (num//g, den//g)
res = (0,1)
for term in expression.replace('-','+-').split('+'):
if not term: continue
res = fadd(res,tuple(int(x) for x in term.split('/')))
return str(res[0])+'/'+str(res[1])
```
我們也可以自己寫parsing的部分，因為輸入格式很固定，也不難寫。以下是範例程式。
第9行的$i$是我們目前處理到字串位置，迴圈會做到字串結束。進入迴圈先找'/'的位置$j$，那麼$[i:j]$就是分子的部分。接著從$j+1$開始找到第一個'+'或'-'或字串結束，這個部分就是分母了。
```python=
class Solution:
def fractionAddition(self, expression: str) -> str:
def fadd(p,q): # frac addition p[0]/p[1]+q[0]/q[1]
num = p[0]*q[1]+p[1]*q[0]
den = p[1]*q[1]
g = gcd(num,den)
return (num//g, den//g)
res = (0,1)
i,n = 0,len(expression)
while i<n:
j = expression.index('/',i+1)
p = int(expression[i:j]) # numerator
i = j+1 # find denominator
while i<n and expression[i] not in "+-":
i += 1
q = int(expression[j+1:i])
res = fadd(res,(p,q))
return str(res[0])+'/'+str(res[1])
```
### GCD與排容原理
下一個題目中，ugly的定義被更改成為可以被$a$,$b$或$c$整除的正整數，其中的$a,b,c$是輸入的正整數，未必為質數。
[(題目連結) 1201. Ugly Number III (Medium)](https://leetcode.com/problems/ugly-number-iii/)
這題與前面三個ugly number的題目是不一樣的，其實跟LCM有關，用的是不同的演算法，我們需要用到排容原理(Inclusion–exclusion principle)[(Wiki說明)](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle)
對於三個正整數$a,b,c$與$t$，要計算在$[1,t]$區間中有多少$a$或$b$或$c$的倍數，這其實是個簡單的中學的數學問題，利用排容原理，我們先求出三數中兩兩的最小公倍數(LCM)以及三者的最小公倍數，然後就可以簡單的計算出來，如下列程式碼中第8 ~ 10行的副程式ugly($t$)。請注意在Python中，我們可以直接使用math.lcm求得若干數字的LCM，LeetCode環境中已經import，直接寫lcm($a$,$b$)就可以。
會計算$t$以下的ugly數量並非本題的答案，我們要求的是第$n$個ugly number。我們採用「對答案二分搜」的策略來找尋。很明顯的，$t$越大時，$t$以下ugly的數量就會越多(非遞減)，我們找到最大的整數$p$，滿足在$[1,p]$區間內的ugly個數$<n$，那麼$p+1$即為所求。
這裡二分搜的寫法並非維護左右區間，而是維護兩變數：$p$是滿足所求的值，$jump$是目前跳躍距離，跳躍距離逐次減半，直到0，對於目前的跳躍距離，$p$如果可跳就跳，也就是若是$p+jump$如果滿足要求，就把$p$的值加上$jump$。
```python=
class Solution:
# inclusion-exclusion and binary search
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
ab = lcm(a,b)
ac = lcm(a,c)
bc = lcm(c,b)
abc=lcm(a,b,c)
def ugly(t): #number of ugly number <=t
return t//a+t//b+t//c-t//ab-t//bc \
-t//ac+t//abc
oo = 2*10**9
jump = oo//2
p = 0 # <n ugly in [1..p]
while jump:
while p+jump<=oo and ugly(p+jump)<n:
p+=jump
jump >>= 1
return p+1
```
時間複雜度是$O(\log R)$，$R$是值域的大小。
## 排列組合 Permutation and Combination
涉及排列組合的題目非常多，這裡提出的主要是與排列數與組合數有關的題目。
### 排列數與組合數的計算
#### 排列數
排列數是排列組合很基本的定理，$n$個相異物的排列方法數是$n!$，若其中取$k$個來排列的方法數則是
$$
P(n,k)=\frac{n!}{(n-k)!}=n\times (n-1)\times \ldots\times (n-k+1)
$$
例如$P(5,3)=5\times 4\times 3=60$。
排列數與階乘都是成長很快的函數，很多題目中都會超過$2^{32}$或$2^{64}$，所以$n$可能很小或者最後要求除以某數的餘數(LeetCode幾乎都是mod ($10^9+7$))
$n$很小的話，自己寫程式計算階乘或排列數都不是難事，Python中不像C與Java對整數範圍限制嚴格，所以更加的簡單。Python現在也有直接幫我們計算$P(n,k)$的函數math.perm($n$,$k$)，如果$k$不給就是算$n!$，以下是示範的程式。
```python=
from math import *
def P(n,k):
t = 1
for i in range(n,n-k,-1):
t *= i
return t
print( P(5,3)); print(P(5,5)); print(P(100,20))
print(perm(5,3))
print(perm(5))
print(perm(100,20))
```
#### 組合數
組合數$C(n,r)$是指$n$個相異物中取出$k$個，不計順序的情況下，有多少種組合。
$$
C(n,r)=\frac{n!}{r!\times(n-r)!}=\frac{n\times(n-1)\times\ldots\times(n-r+1)}{1\times 2\times\ldots\times r}
$$
也就是有$n$往下取$r$個數字相乘除以1到$r$的乘積。如果不考慮數字大小，直接照定義拉一個迴圈來計算是很簡單的。Python的math.comb($n$,$r$)也可以直接幫我們算出來。
```python=
from math import *
def cnr(n,r):
t = 1
for i in range(r):
t *= n-i
for i in range(2,r+1):
t //= i
return t
print(cnr(5,3))
print(cnr(100,20))
print(comb(5,3))
print(comb(100,20))
```
在自己寫的cnr中，我們先算分子再除以分母，來確保是可以整除的。
跟排列數一樣，組合數也很大，所以經常是取模運算。當$n$真的非常大的時候，Python上面的方法還是會出問題的，即使允許大數運算，但大整數的計算還是會比正常整數的計算花費較長時間，所以我們還是需要學一下在算法上對於這個問題的處理方式。這也是其他語言(如C++)的處理方式。
現在的問題是要算$C(n,r)\%p$，$p=10^9+7$是個質數。
一個方法是利用帕斯卡三角形的組合公式
$$
C(n,r)=C(n-1,r)+C(n-1,r-1)
$$
我們可以用DP的概念由小到大算出所要的組合數$C(n,r)$或是全部的$C(n,i)$對所有$i$。因為模運算下先加再取餘數等於先取餘數再加，所以只要計算的過程中一直取餘數就可以了。
此法的缺點是需要$O(n^2)$的時間複雜度，因為你可以看到表格的大小就是$O(n^2)$，所以除非我們需求所有的$C(n,i)$，例如要建表後多次使用，否則這個方法並不好。
直接照公式計算只需要$O(r)$個乘除法。但計算時的問題是**除法**。模運算(Modular arithmetic)在做加、減、乘法時都沒問題，先加減乘後再取餘數與先取餘數後再加減或是乘都是一樣的，但除法不行，解決的辦法是將除法改成乘以其**乘法反元素**，又稱**模逆元**。
對於正整數$k$，其模P的乘法反元素就是一正整數$h$滿足$h\times k = 1$ (mod $p$)。若$p$為質數，例如$p=10^9+7$，$[1,p-1]$之間每一個數的乘法反元素都唯一存在。且根據[費馬小定理](https://zh.wikipedia.org/zh-tw/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86)，$k$的乘法反元素為$k^{p-2}$ (mod $p$)，我們用快速冪(binary exponentiation)的方法可以在$O(\log p)$的時間內求出。
Python內建了快速冪pow()而且是模運算，甚至，pow(k,-1,p)直接算出$k$在模$p$的乘法反元素，也就是$k^{-1}$。
以下是示範的程式。處理除法的方法在類似問題中也會碰到，後面有個範例。
```python=
import math
p = 10**9+7
def cnr(n,r):
t = 1
for i in range(r):
t = t*(n-i)%p
for i in range(2,r+1):
t = t*pow(i,-1,p)%p
#t = t*pow(i,p-2,p)%p
return t
print(cnr(5,3))
print(cnr(100,20))
print(math.comb(5,3))
print(math.comb(100,20)%p)
```
### 排列組合範例
[(題目連結) 60. Permutation Sequence (Hard)](https://leetcode.com/problems/permutation-sequence/)
這一題是permutation unranking，也就是求$\{1,2,\ldots n\}$這$n$個相異物的第$k$小的排列。所謂第$k$小是指字典順序(lexicographic order)。
我們可以觀察到以下事實：以1開頭的排列個數有$(n-1)!$，這些排列比其它開頭的排列都要小。重複利用這個事實，排列可以看成一個進位系統，跟常見10進位系統不一樣的是，每一位數的進位條件都不一樣。從後往前看，最後一位只能有一個，所以逢1進位(永遠都是0)，倒數第2位則是逢2進位(只會是0或1)，...。
對於$0 \leq k < n!$，可以寫成
$$
k = d_{n-1}\times (n-1)! + d_{n-2}\times (n-2)! + \ldots + d_1\times 1! + d_0
$$
其中$0\leq d_i\leq i$。此表示法為唯一。假設我們從前往後看，$d_{n-1}$就表示在$[1,n]$中要挑選第$d_{n-1}$小的，而$d_{n-2}$就表示在剩下的物品中要挑選第$d_{n-2}$小的。根據這個特性程式就很容易寫了。要留意上述的說明中的rank是從0開始，本題定義是從1開始，所以一開始我們將$k$減去1。
我們需要計算$i!$，以下的範例程式直接呼叫Python中的math.perm($i$)來取得階乘值。此外我們需要在$n$個數字(初始為$[1,n]$)中每次挑選某個第$j$小的並將其移除，這裡我們直接用排好序的list，每次移除時用pop($j$)，因為$n$很小，所以時間上不是問題。
```python=
class Solution:
def getPermutation(self, n: int, k: int) -> str:
num = [i for i in range(1,n+1)]
ans = ""
k -= 1 # rank starting at 0
for i in range(n-1,-1,-1):
w = perm(i) # i!
j,k = k//w,k%w
ans += str(num[j])
num.pop(j)
return ans
```
如果不使用math.perm，排列數也很容易自己算。以下是範例程式。
```python=
class Solution:
def getPermutation(self, n: int, k: int) -> str:
pn = [1,1] # factorial
for i in range(2,n):
pn.append(pn[-1]*i)
num = [i for i in range(1,n+1)]
ans = ""
k -= 1 # rank starting at 0
for i in range(n-1,-1,-1):
j,k = k//pn[i],k%pn[i] # //i!
ans += str(num[j])
num.pop(j)
return ans
```
輸入整數$n$，下面這題要找在$[1,n]$區間中有多少個數具有重複數字，例如11, 212, 1030 都是有重複數字的整數，而10, 7, 152則沒有重複數字。
[(題目連結) 1012. Numbers With Repeated Digits (Hard)](https://leetcode.com/problems/numbers-with-repeated-digits/)
這題基本上是排列數$perm(n,k)$的運用，但題目比較繁瑣。題目是要求有重複的數，我們可以轉成找無重複的數，最後再用全部$n$個數減去無重複的數，就是答案。我們先將各位數字取出放在$dig[]$，長度是$nd$。要計算無重複的數字，我們分成兩組：
* 位數比$n$短以及位數相同但第一位比較小的。例如$n=354$有三位，那麼長度1與2的以及長度3但第一位$<3$，也就是1XX或2XX的樣子。
* 長度$<nd$的，數字可以隨便擺，但第一位不可以是0，否則會重複計算，所以長度$i$的數量有$9\times perm(9,i-1)$。
* 長度$=nd$，第一位可以擺$(dig[0]-1)$種，後面剩下$perm(9,nd-1)$。
* 第二組我們計算前$i$個位數與$n$相同的。首先我們要知道第$i+1$位可以有多少可能。例如$n=1854512, i=3$，也就是我們要找185開頭的，接下來要比4小，比4小數字本來有4個(0,1,2,3)，但必須扣除已經出現在prefix的(這個例子是1，所以剩下3種(0,2,3)。剩下的位數不重複的隨便擺有$perm(10-i-1, nd-i-1)$種。
* 如果在計算第二組的過程中發現$n$目前的字首已經重複，例如2474XXX，在算完前四位時發現4已經重複後面就不必算了，因為要找的等於是字首2473999。
* 最後要留心一點：若$n$本身是無重複數，那麼無重複的數量要加一，因為前面計算的是$<n$的，而題目是$\leq n$。
```python=
class Solution:
# count num without repeat
def numDupDigitsAtMostN(self, n: int) -> int:
if n<=10: return 0
dig = [int(d) for d in str(n)]
nd = len(dig) # nd >= 2
# k-digits without repeat = 9*P(9,k-1), no leading 0
total = 9*sum(perm(9,i-1) for i in range(1,nd))
# first digit<dig[0]
total += (dig[0]-1)*perm(9,nd-1)
# same prefix(i) as n
for i in range(1,nd):
# num of dig <dig[i] and not in dig[:i]
cnt = dig[i]-sum(1 for d in dig[:i] if d<dig[i])
total += cnt*perm(10-i-1, nd-i-1)
if dig[i] in dig[:i]: # like 2474XXX, repeated
break
# if n is non-repeated
if len(set(dig))==len(dig): total += 1
return n-total
```
下面這題挺有趣的，題目是說給一個正整數$k$，請問全部digit都是1可以被$k$整除的的最小整數$n$有幾位。
[(題目連結) 1015. Smallest Integer Divisible by K (Medium)](https://leetcode.com/problems/smallest-integer-divisible-by-k/)
這一題很像在模擬做除法，做除法時，如果沒有整除，我們會將餘數乘以10，然後繼續除，直到何時呢？直到整除了或者是餘數重複出現，當餘數重複出現，我們知道結果是個循環小數，永遠除不盡。
本題中我們也是從$n=1$開始，一直除，如果整除了就找到最短的$n$，如果除不盡餘數乘以10後加1，也就是把原來的$n$後面再補一個1，當餘數重複出現了就表示再下去也不可能整除。
以下是範例程式，一開始我們特判一下偶數是不可能整除的。為了偵測餘數是否重複，我們用set()。時間複雜度$O(k)$，因為除以$k$的餘數最多只有$k$種。
```python=
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
if k%2==0: return -1
occur = set()
n = 1
leng = 1
while n not in occur:
occur.add(n)
n %= k
if n==0: return leng
n = n*10+1
leng += 1
return -1
```
在下一題中，給一個rooted tree，找出滿足所有parent在它的child之前出現的排列(preorder)有多少種。
[(題目連結) 1916. Count Ways to Build Rooms in an Ant Colony (Hard)](https://leetcode.com/problems/count-ways-to-build-rooms-in-an-ant-colony/)
這是個排列組合的問題。樹狀圖的問題大多是DP類型，本題也可如是看，我們先找遞迴式。若$v$點的subtree的排列數為$p(v)$，$n(v)$為該點subtree的節點數，則
$p(v) = \left(\prod_{u \in child(v)} p(u)\right)\times (n(v)-1)! / \prod_{u \in child(v)}n(u)!$。
遞迴式的來源可以這樣理解：對於每一個孩子之下的排列與其它相混合時，看成是相同物。所以有
$(n(v)-1)! / \prod_{u \in child(v)}n(u)!$，減一是不包含$v$，因為$v$必須擺第一個。再乘上每一個child的排列數就是答案。
計算時的另一個問題是**除法**。在這個單元一開始計算組合數的章節中，我們已經介紹過利用乘法反元素處理模運算除法的問題，這裡就必須用到它。
還有一個重點：Python的math.perm()不可以當作$O(1)$，因為它本來就不是$O(1)$。所以在有很多排列數要計算的場合，還是要先打表再使用比較好。
最後一個重點，Tree的DP可以寫DFS，也可以老老實實寫bottom-up，LeetCode有幫Python的遞迴深度放寬，所以只要記憶體不暴的話，寫DFS遞迴的程式碼通常比較簡短，其實也沒差幾行。
以下是範例程式。我們把階乘與其反元素寫在class之外，是會讓程式跑的(總)時間小一點，LeetCode是計算所有測資的總時間，雖然在LeetCode上比絕對時間沒有太大意義，但是跑出來的排名百分比比較高還是會比較"爽"一點。
第11 ~ 13行將輸入的格式轉換為child，這是為DFS做準備。副程式DFS其實很簡單，根據上面推導出來的計算式，我們需要child的點數與排列數，所以我們回傳這兩個數，每呼叫一個child，就把它的回傳值乘到我們的計算式中，在分母的就用反元素。同時我們將節點數累加，最後再去乘總結點數的階乘。
```python=
mod = 10**9+7
fac = [1,1] #factorial
for i in range(2,100001): fac.append(fac[-1]*i%mod)
inv_fac = [pow(i,mod-2,mod) for i in fac] #inverse of n!
class Solution:
# tree number of preorder
# p(v) = prod(p(u) for u in child(v))*(n(v)-1)!/prod(n(u)!)
# dfs using perm and pow
def waysToBuildRooms(self, prevRoom: List[int]) -> int:
n = len(prevRoom)
child = [[] for i in range(n)]
for i,p in enumerate(prevRoom[1:],start=1):
child[p].append(i)
def dfs(v): # return (num of nodes, num of permutation)
nnode,dp = 1,1
for u in child[v]:
k,s = dfs(u)
nnode += k
dp = dp*s*inv_fac[k]%mod
return nnode, dp*fac[nnode-1]%mod
return dfs(0)[1]
```
下面這之範例程式是Bottom-up的，而且沒有做寫減少時間的取巧行為。Tree的Bottom-up與DAG(directed acyclic graph)的topological sort是類似的方法，將來會有專門的單元討論Tree。
```python=
class Solution:
# tree number of preorder
# p(v) = prod(p(u) for u in child(v))*(n(v)-1)!/prod(n(u)!)
#using pow
def waysToBuildRooms(self, prevRoom: List[int]) -> int:
n,mod = len(prevRoom),1000000007
fac = [1,1] #factorial
for i in range(2,n+1): fac.append(fac[-1]*i%mod)
def inv(p): #inverse of p
return pow(p,mod-2,mod)
inv_fac = [1,1]+[inv(i) for i in fac[2:]] #inverse of n!
num,dp = [1]*n, [1]*n # num descendents
deg = [0]*n
for p in prevRoom[1:]:
deg[p] += 1
que = [v for v in range(n) if deg[v]==0]; head = 0
while head < len(que):
v = que[head]; head += 1
dp[v] = dp[v]*fac[num[v]-1]%mod
p = prevRoom[v] # parent
if p<0: break
num[p] += num[v]
dp[p] = dp[p]*dp[v]*inv_fac[num[v]]%mod
deg[p] -= 1
if deg[p]==0: que.append(p)
return dp[0]
```
#### 快速冪(binary exponentiation)
下面這個題目中定義了所謂一個good number是偶數位數是偶數，奇數位數是質數(2,3,5,7)。要求$n$位數的整數中有多少good number，允許有leading 0。
[(題目連結) 1922. Count Good Numbers (Medium)](https://leetcode.com/problems/count-good-numbers/)
看起來很簡單，長度$n$位的數字字串，因為是0-index，所以奇數位數有$odd=n//2$個，那麼偶數位數就有$even=n-n//2$個。偶數位數可以是任意偶數，就有5種選擇；奇數位數必須是質數，所以有4種選擇。答案就是$5^{\text{even}}\times 4^{\text{odd}}$。
但是，且慢，
這題的$n$大到$10^{15}$，直接寫
```python
return (5**even)*(4**odd)%mod
```
是不行的。這題是要考快速冪。
不過呢！Python內建快速冪了，而且也支援模運算，還是高效率的，所以直接用pow函數還是很簡單。
為了提供讀者參考起見，我們還是把快速冪的寫法提供在下面的範例程式中，包含非遞迴寫法與遞迴寫法。其實，快速冪從英文binary exponentiation應該比較容易知道它的意思。這是一種倍增法的概念，將指數部分以二進位表示，例如$x^{41} = x^{32}\times x^{8}\times x^{1}$。我們每次讓$x$自乘，依序產生$x, x^2, x^4, x^8,\ldots$，然後依照指數的二進位表示法就可以知道產生出來的冪次中哪一些要乘到最後的結果中。
用遞迴的觀念就更直接了，指數$e$如果是奇數，就先算出$x^{e-1}$再乘一次$x$；如果是偶數就先求出$x^{e/2}$後再平方。當然這些都是在模運算下。這三種方法跑出來都差不多快。
但是我們特別要提醒一下，遞迴的寫法中第17行那個寫法是複雜度壞掉的寫法。
```python=
class Solution:
# 5**(num of even)*4**(num of odd)
def countGoodNumbers(self, n: int) -> int:
mod = 1000000007
def exp(b,e): # b**e%mod
r = 1
while e:
if e&1: r = r*b%mod
b = b*b%mod
e >>= 1
return r
def rexp(b,e): # recursive exponentiation
if e==0: return 1
if e&1: return b*rexp(b,e-1)%mod
# even e
# return rexp(b,e>>1)*rexp(b,e>>1)%mod TLE bad
t = rexp(b,e>>1)
return t*t%mod
odd = n//2
even = n-odd
#return pow(5,even,mod)*pow(4,odd,mod)%mod
#return exp(5,even)*exp(4,odd)%mod
return exp(5,even)*exp(4,odd)%mod
```
## 結語
程式解題中可能涉及的數學太多了，本單元中我們說明了在LeetCode中常見簡單的數學知識與例題。Python對於最大公因數(gcd)、最小公倍數(lcm)、排列數(perm)、組合數(comb)、指數計算(pow)都有現成的函數可以呼叫，而且效率很好。雖然如此，對於一些基本的觀念還是要有，否則也不會運用或者用了錯誤的方式運用。
除了本單元中所示範的題目，LeetCode中當然還有很多相關的題目，許多題目也都是結合了其他主題。排列組合還有很多題型，有些會在DP與暴搜枚舉的主題中再看到。
Python雖然有現成的pow()函數可以快速的算指數，但是快速冪的方法還是值得一學，特別是矩陣的快速冪是1d0d的DP的優化方法，例如快速的求Fibonacci數。
Sign in with Wallet
Connect another wallet