MediumRating 1369
3179. Find the N-th Value After K Seconds
arraymathsimulationcombinatoricsprefix-sum
解題說明
Find the N-th Value After K Seconds
題目描述：初始陣列 a 長度為 n，所有值為 1。每秒鐘，每個元素變成它自身加上前面所有元素的和（即做一次前綴和）。求 k 秒後陣列中第 n 個元素（索引 n-1）的值，答案取模 10⁹+7。
解題思路：每秒做一次前綴和操作。數學上，k 次前綴和後第 n 個位置的值等於組合數 C(n-1+k, k)。這是因為每次前綴和等價於一個上三角的 Pascal 矩陣乘法，k 次後的結果就是 Pascal 三角形對應位置的值。使用模運算下的階乘和逆元來計算組合數，或直接模擬 k 輪前綴和（因 n, k <= 1000，模擬也可接受）。
C++ 解法
複雜度分析
時間複雜度：O(n × k) — 模擬 k 輪，每輪計算 n 個前綴和。
空間複雜度：O(n) — 儲存長度為 n 的陣列。
虛擬碼
1. Initialize array a[0..n-1] = all 1s
2. For t = 1 to k:
a. For i = 1 to n-1:
a[i] = (a[i] + a[i-1]) % MOD
3. Return a[n-1]其他解法
組合數學公式 O(n + k)：答案為 C(n-1+k, k) mod p。用階乘預處理和費馬小定理求模逆元，可在 O(n+k) 時間內算出。當 n 或 k 很大時此方法更優。
矩陣快速冪 O(n³ log k)：將前綴和操作視為矩陣乘法，用矩陣快速冪加速。當 k 極大但 n 較小時適用，但實作複雜。
延伸思考
- 如果 n 和 k 的範圍增大到 10⁶，模擬法會超時，如何用組合數學公式在 O(n+k) 內求解？
- 如果初始陣列不全是 1 而是任意值，答案的公式如何推導？
- 如果操作改為「每個元素變成後綴和」，結果會有什麼不同？