主題

LeetCode - 1175. Prime Arrangements 解題心得

Not In My Back Yard | 2021-03-31 00:00:11 | 巴幣 0 | 人氣 53

題目連結:


題目意譯:
回傳數字 1 ~ n 的排列方法數,其使得質數會排在質數索引值(從 1 開始算)上。

(回想一下,一個整數為質數若且唯若該數 > 1 且不能表示為兩個小於該數的正整數之乘積)

因為答案可能很大,所以將答案模 10 ^ 9 + 7 後回傳。

限制:
1 ≦ n ≦ 100



範例測資:
範例 1:
輸入: n = 5
輸出: 12
解釋: 例如 [1,2,5,4,3] 是一個合法排列,而 [5,2,3,4,1] 則不是因為質數數字 5 位於索引值 1。

範例 2:
輸入: n = 100
輸出: 682289015


解題思維:
這題可以考慮建表,寫法可以參見這題,而質數的篩法可以參見這題

我們定義 P[i] 為 1 ~ i 的所求方法數,而我們在建表的時候可以順便求出 P[i] 之值:
首先,將 P[i] 之值設為 P[i - 1] (P[0] = P[1] = 1);

接著判斷完現在的數字 i 是否為質數。如果是,我們將 i 納入質數表後,此時將 P[i] 乘以質數表目前有的質數數量(記得取 10 ^ 9 + 7 的餘數);如果不是質數,則將 P[i] 乘以 (i - 當前質數表質數數量) 取 10 ^ 9 + 7 之餘數。

這樣做便可以在建完質數表後,也一併求出 1 ≦ n ≦ 100 時的 P[n] 了。



而為何在計算 P[i] 時需要做以上操作呢?假設 1 ~ n 有 p 個質數,因此所求 P[n] 會是 p! × (n - p)! 。

因為質數固定在質數索引值上排列組合,而非質數則會在剩下的位置排列組合。

所以當 n 為質數時,P[n] 可以寫為
P[n - 1] × p
而當 n 不為質數時,P[n] 可以表為
P[n - 1] × (n - p)
而上面的遞迴式即是我們在建表時所寫的東西,因此本題也同時是一題典型的動態規劃(Dynamic Programming)之題型。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作