2221. Find Triangular Sum of an Array

Find Triangular Sum of an Array

題目描述： 給定一個整數陣列 nums。反覆執行以下操作直到只剩一個元素：對相鄰元素求和並取模 10，生成新的陣列。最後剩下的元素即為三角和。

解題思路： 最直接的方式是模擬整個過程。每一輪將陣列長度減少 1。

1. 對長度為 n 的陣列，需要 n-1 輪操作。
2. 每一輪：for i in [0, len-2]，newArr[i] = (arr[i] + arr[i+1]) % 10。
3. 可以原地操作，省去額外陣列：每輪從前往後更新 arr[i] = (arr[i] + arr[i+1]) % 10。

由於 n 最大為 1000，總操作數約 n^2/2 ≈ 500000，完全可以接受。

時間複雜度：O(n^2) — 總共約 n*(n-1)/2 次加法和取模操作。

空間複雜度：O(1) — 原地修改陣列，不需要額外空間。

1. 組合數學法（Lucas 定理）：最終結果等於 sum(C(n-1, i) * nums[i]) % 10。其中 C(n-1, i) 是二項式係數。利用 Lucas 定理在模 2 和模 5 下分別計算組合數，再用中國剩餘定理合併。可達 O(n) 時間，但實作較複雜。

2. 遞迴法：遞迴地計算子陣列的三角和。每次遞迴生成新陣列，直到長度為 1。時間複雜度相同 O(n^2)，但需要 O(n) 額外空間存中間陣列。

1. 若取模數不是 10 而是質數 p，Lucas 定理的應用會有什麼簡化？
2. 若 n 非常大（如 10^6），O(n^2) 不可行，如何用組合數學法在 O(n) 或 O(n log n) 時間內求解？
3. 若操作改為相鄰元素的乘積取模，結果的計算方式會有什麼本質不同？