推 oin1104: 養我 09/10 00:05
推 pyrogenlisa: 好強 09/10 00:05
2327. Number of People Aware of a Secret
用一個矩陣A來記錄第i天可以分享祕密的人
另一個矩陣B來記錄第i天知道秘密的人
當A[i]>0, 表示會有A[i]個人在i+delay後能開始分享祕密
並在i+forget會忘記秘密
然後B[i]會等於前一天知道秘密的B[i-1]加上這一天能分享祕密的A[i]
最後回傳B[n-1]就好
golang code :
func peopleAwareOfSecret(n int, delay int, forget int) int {
canShare, arr, mod := make([]int, n), make([]int, n), 1_000_000_007
if forget < n {
arr[forget], canShare[forget] = -1, -1
}
if delay < n {
canShare[delay] = 1
}
arr[0] = 1
for i := 1; i < n; i++ {
canShare[i] += canShare[i-1]
if i+forget < n && canShare[i] > 0 {
canShare[i+forget] = (canShare[i+forget] - canShare[i] + mod) % mod
arr[i+forget] = (arr[i+forget] - canShare[i] + mod) % mod
}
if i+delay < n && canShare[i] > 0 {
canShare[i+delay] = (canShare[i+delay] + canShare[i]) % mod
}
arr[i] = (arr[i] + arr[i-1] + canShare[i]) % mod
}
return arr[n-1] % mod
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1757433855.A.645.html