主題

LeetCode - 1922. Count Good Numbers 解題心得

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

題目連結:


題目意譯:
一個數字字串為「好的」如果其位於偶數位置(索引值從 0 開始)之位數皆為偶數而位於奇數位置之位數為質數(2 、 3 、 5 或是 7)。

例如,"2582" 是好的因為位於偶數位置之位數(2 和 8)皆為偶數且位於奇數位置之位數(5 和 2)為質數。不過,"3245" 則不是好的,因為 3 在偶數位置但它不是偶數。

給定一整數 n,回傳長度 n 的好字串之數量。由於答案可能很大,將其模 10 ^ 9 + 7 後回傳。

一個數字字串為一由數字 0 到 9 組成的字串且可能含有前導零。

限制:
1 ≦ n ≦ 10 ^ 15



範例測資:
範例 1:
輸入: n = 1
輸出: 5
解釋: 長度 1 的好數字為 "0" 、 "2" 、 "4" 、 "6" 、 "8"。

範例 2:
輸入: n = 4
輸出: 400

範例 3:
輸入: n = 50
輸出: 564908303


解題思維:
一個長度為 n 的數字,其奇數位置有 floor(n ÷ 2) 個、偶數有 ceil(n ÷ 2) 個。其中 ceil 為上高斯函數(對於非負數等價於無條件進位到整數位)而 floor 為下高斯函數(對於非負數等價於無條件捨去小數點)。

而因為奇數位置的數字需要是質數,所以每個奇數位置會有 4 種選擇(2 、 3 、 5 、 7);偶數位置則需要是偶數,所以每個偶數位置會有 5 個選擇(0 、 2 、 4 、 6 、 8)。因此長度為 n 的好數字會有
4 ^ floor(n ÷ 2) × 5 ^ ceil(n ÷ 2)
這麼多個。

而因為我們需要快速得到一個形如 a ^ b 模 10 ^ 9 + 7 的值(直接求 a ^ b 再模 10 ^ 9 + 7 會太耗時),因此我們可以利用快速冪(如這題所述)來求得。




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

創作回應

相關創作

更多創作