解題說明
Count Vowels Permutation
題目描述：
給定整數 n，計算長度為 n 的字串中，由母音字母 (a, e, i, o, u) 組成且滿足以下規則的排列數量（結果取模 10^9+7）：
- a 後面只能接 e
- e 後面只能接 a 或 i
- i 後面不能接 i
- o 後面只能接 i 或 u
- u 後面只能接 a
解題思路：
這是一道典型的動態規劃（DP）問題。定義 dp[c] 為以字元 c 結尾的合法字串數量。根據規則，反推每個字元可以由哪些字元接過來：
- 以 a 結尾：前一個可以是 e, i, u
- 以 e 結尾：前一個可以是 a, i
- 以 i 結尾：前一個可以是 e, o
- 以 o 結尾：前一個可以是 i
- 以 u 結尾：前一個可以是 i, o
初始化長度 1 時每個字元的計數為 1，然後迭代 n-1 次，每次根據轉移規則更新。最後將五個字元的計數加總即為答案。
C++ 解法
複雜度分析
時間複雜度：O(n) — 迭代 n-1 次，每次做常數次運算。
空間複雜度：O(1) — 只使用五個變數。
虛擬碼
1. Initialize a = e = i = o = u = 1 (base case: strings of length 1) 2. For step from 1 to n-1: a. new_a = (e + i + u) % MOD b. new_e = (a + i) % MOD c. new_i = (e + o) % MOD d. new_o = i % MOD e. new_u = (i + o) % MOD f. Update a, e, i, o, u with new values 3. Return (a + e + i + o + u) % MOD
其他解法
矩陣快速冪 O(log n)：將轉移規則表示為 5x5 矩陣，使用矩陣快速冪在 O(5^3 log n) = O(log n) 時間內求解。適合 n 極大的情況，但實作較複雜。
記憶化遞迴 O(5n)：dp(pos, lastChar) 表示從位置 pos 開始、上一個字元為 lastChar 的方案數。時間空間皆 O(5n) = O(n)，直覺但遞迴開銷稍大。
延伸思考
- 若規則改變（例如新增限制或移除某些限制），如何快速調整轉移方程？
- 當 n 極大（例如 10^18）時，如何利用矩陣快速冪加速？
- 若不只有五個母音，而是任意字母集合與任意轉移規則，如何泛化此解法？