主題
題目連結：
題目意譯：
你被給定兩整數 n 和 maxValue，其被用來描述一個理想的陣列。
一個索引值從 0 開始的且長度為 n 之陣列 arr 如果滿足以下條件，則將被視為是理想的：
每個 arr[i] 為一個 1 到 maxValue 的數值，其中 0 ≦ i < n、
每個 arr[i] 可以被 arr[i - 1] 所整除，其中 0 ≦ i < n。
回傳長度為 n 的相異理想陣列之數量。由於答案可能很大，將其模 10 ^ 9 + 7 後再回傳。
限制：
2 ≦ n ≦ 10 ^ 4
1 ≦ maxValue ≦ 10 ^ 4
範例測資：
範例 1：
輸入： n = 2, maxValue = 5
輸出： 10
解釋： 下列為可能的理想陣列：
- 以數字 1 作為開頭的陣列（有 5 個）：[1,1] 、 [1,2] 、 [1,3] 、 [1,4] 、 [1,5]
- 以數字 2 作為開頭的陣列（有 2 個）：[2,2] 、 [2,4]
- 以數字 3 作為開頭的陣列（有 1 個）：[3,3]
- 以數字 4 作為開頭的陣列（有 1 個）：[4,4]
- 以數字 5 作為開頭的陣列（有 1 個）：[5,5]
總計有 5 + 2 + 1 + 1 + 1 = 10 個相異理想陣列。
範例 2：
輸入： n = 5, maxValue = 3
輸出： 11
解釋： 下列為可能的理想陣列：
- 以數字 1 作為開頭的陣列（有 9 個）：
- 沒有其他相異數值者（有 1 個）：[1,1,1,1,1]
- 有第二種相異數值 2 者（有 4 個）：[1,1,1,1,2] 、 [1,1,1,2,2] 、 [1,1,2,2,2] 、 [1,2,2,2,2]
- 有第二種相異數值 3 者（有 4 個）：[1,1,1,1,3] 、 [1,1,1,3,3] 、 [1,1,3,3,3] 、 [1,3,3,3,3]
- 以數字 2 作為開頭的陣列（有 1 個）：[2,2,2,2,2]
- 以數字 3 作為開頭的陣列（有 1 個）：[3,3,3,3,3]
總計有 9 + 1 + 1 = 11 個相異理想陣列。
解題思維：
首先我們來仔細揣摩一下「每個 arr[i] 可以被 arr[i - 1] 所整除」代表著什麼意義：
假設 arr[i] 質因數分解後得到 P1 ^ C1 × P2 ^ C2 × …… 、
而 arr[i - 1] 質因數分解得到 P1' ^ C1' × P2' ^ C2' × ……、
其中 Pi 、 Pi' 皆是質數，且 Ci 、 Ci' > 0。
則 arr[i] 被 arr[i - 1] 所整除則代表著，P1 = P1' 、 P2 = P2' 、…… 且 C1 ≧ C1' 、 C2 ≧ C2' 、……。
而這對 arr 整體代表著什麼意思？其代表著如果有一個新的質因數 P 出現了在 arr[i] 的質因數分解（也就是 P 這個質數沒有出現在這之前又或是比之前多出現若干次，即對於 arr[0] 、 arr[1] 、 …… 、 arr[i - 1] 來說，P 不存在或是 P 的次方部分增加了）之中，則這代表著這之後（即 arr[i + 1] 、 arr[i + 2] 、 ……）P 都會出現在它們的質因數分解之中。
因此雖然範例中是使用開頭數字來作為分類，但是這實際上不會幫助到我們（因為從 arr[i - 1] 到 arr[i]，我們完全無法期待會出現什麼質因數）。在此我們改以結尾數字來分類，因此範例 1 將有：
- 以數字 1 作為結尾的陣列（有 1 個）：[1, 1]
- 以數字 2 作為結尾的陣列（有 2 個）：[1, 2] 、 [2, 2]
- 以數字 3 作為結尾的陣列（有 2 個）：[1, 3] 、 [3, 3]
- 以數字 4 作為結尾的陣列（有 3 個）：[1, 4] 、 [2, 4] 、 [4, 4]
- 以數字 5 作為結尾的陣列（有 2 個）：[1, 5] 、 [5, 5]
這樣一來，我們在從左至右掃過 arr 的陣列時可以期望著出現結尾數字的質因數出現（結尾是 4 的陣列來說，即是 2 這個質數）。
更甚者，我們可以觀察出以某個數字結尾的陣列之總數即為該數字的質因數在陣列中的位置上排列組合的方法數。把上例中每個數字都替換成質因數分解的結果會更好觀察（質因數之次方值為 1 者將只寫下質因數本身）：
- 以數字 1 作為結尾的陣列（有 1 個）：[1, 1]
- 以數字 2 作為結尾的陣列（有 2 個）：[1, 2] 、 [2, 2]
- 以數字 3 作為結尾的陣列（有 2 個）：[1, 3] 、 [3, 3]
- 以數字 4 作為結尾的陣列（有 3 個）：[1, 2 ^ 2] 、 [2, 2 ^ 2] 、 [2 ^ 2, 2 ^ 2]
- 以數字 5 作為結尾的陣列（有 2 個）：[1, 5] 、 [5, 5]
然後我們把數字 1 或是那些與前一個位置之數值沒有差的位置替換成「X」當作佔位子用的，並且把每一個位置之值替換成與前一個位置（沒有前一個就當作其值是 1）質因數之差別：
- 以數字 1 作為結尾的陣列（有 1 個）：[X, X]
- 以數字 2 作為結尾的陣列（有 2 個）：[X, 2] 、 [X, 2]
- 以數字 3 作為結尾的陣列（有 2 個）：[X, 3] 、 [X, 3]
- 以數字 4 作為結尾的陣列（有 3 個）：[X, 2 ^ 2] 、 [2, 2] 、 [2 ^ 2, X]
- 以數字 5 作為結尾的陣列（有 2 個）：[X, 5] 、 [5, 5]
以數字 4 作為結尾的陣列們作為例子就很明顯——4 = 2 ^ 2，因此 4 有兩個質因數 2 可以在陣列的位置上任意出現（記得，一旦每個質因數出現在某位置上後同時也會自動出現在之後的所有位置）。兩個相同的質數 2 在兩個不同位置選地方放的方法數為 C(3, 2) = 3 個（參見維基頁面說明）。
而一般化的情形為：如果現在只單看以數字 k 作為結尾且長度為 n 的陣列，而已知 k 的質因數分解為 P1 ^ C1 × P2 ^ C2 × ……，則其方法數為
C(n + C1 - 1, C1) × C(n + C2 - 1, C2) × ……
而上式只是對於 k 這個數字而已，我們要對 1 ～ maxValue 中的每個數字都做相同的事情。最後把它們的方法數全部加起來即是所求。
不過當然由於過程中需要對 10 ^ 9 + 7 取模，因此需要牽涉到求組合數的模反元素之運算（可以參見這題）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
