MediumRating 1894
2327. Number of People Aware of a Secret
dynamic-programmingqueuesimulation
解題說明
Number of People Aware of a Secret
題目描述： 在第 1 天，一個人發現了一個秘密。每個知道秘密的人會在知道秘密 delay 天後開始向一個新人分享秘密，直到知道秘密 forget 天後忘記秘密。給定天數 n、delay 和 forget，求第 n 天有多少人知道秘密（對 10^9 + 7 取模）。
解題思路： 使用動態規劃。定義 dp[i] 為第 i 天「新知道秘密」的人數。第 1 天 dp[1] = 1。對於第 i 天，所有在第 j 天知道秘密（j 滿足 j + delay <= i 且 j + forget > i）的人都會在第 i 天分享秘密，因此 dp[i] = Σ dp[j]，其中 max(1, i-forget+1) <= j <= i-delay。
最終答案為所有在第 n 天還記得秘密的人數，即 Σ dp[j]，其中 j + forget > n（即 j > n - forget）。
可以用前綴和優化為 O(n)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 一次遍歷加上滑動窗口
空間複雜度：O(n) — dp 陣列
虛擬碼
1. Initialize dp[1] = 1, share = 0 2. For day i from 2 to n: a. If i - delay >= 1: share += dp[i - delay] (new sharers) b. If i - forget >= 1: share -= dp[i - forget] (people who forgot) c. dp[i] = share (new people learning secret today) 3. Sum dp[j] for all j where j + forget > n (people who still remember) 4. Return sum mod 10^9 + 7
其他解法
-
差分陣列法：用差分陣列標記每個人從何時開始分享到何時停止。可以避免滑動窗口的邊界處理，但本質時間複雜度相同 O(n)。
-
矩陣快速冪法：將轉移方程寫成矩陣形式，使用矩陣快速冪將時間複雜度降至 O(forget^3 * log n)。當 n 很大但 forget 很小時有優勢。
延伸思考
- 如果每個知道秘密的人每天可以分享給 k 個新人（而非 1 個），答案如何變化？
- 如果有人可能選擇不分享（每天分享的機率為 p），如何計算期望知道秘密的人數？
- 如果 n 可以到 10^18，如何用矩陣快速冪優化？