→ DJYOSHITAKA: 然後記憶體懶管了 一生就這樣了 05/26 23:00
先看沒有A的case，然後分別看最後一個是LorP的組合數做DP
最後就乘乘加加
然後幹你娘
我一開始寫mod = 1e9+7
怎麼用都錯 然後都跟答案差那一點點 就感覺很莫名奇怪
才發現1e9+7是float有誤差
要寫10**9+7才會對
我真的是幹==
害我一直在算式裡到處亂加mod 瞎猜到底是哪裡錯
所以我的code裡面一堆mod 好白癡
幹 還我時間==
超級姆咪
def checkRecord(self, n: int) -> int:
if n == 1:
return 3
elif n == 2:
return 8
# mod = 1e9+7
mod = 10**9+7
dp_L = [0 for _ in range(n+1)] # LP only
dp_P = [0 for _ in range(n+1)] # LP only
dp_L[1] = 1
dp_P[1] = 1
dp_L[2] = 2
dp_P[2] = 2
for i in range(3, n+1):
dp_L[i] = ((dp_P[i-2]*2)%mod + dp_L[i-2]) % mod
dp_P[i] = (dp_P[i-1] + dp_L[i-1]) % mod
dp_LP = [(i+j)%mod for i,j in zip(dp_L,dp_P)]
dp_LP[0] = 1
ans = dp_LP[n] # 0A
for i in range(1,n+1):
ans = (ans + (dp_LP[i-1]*dp_LP[n-i])%mod)%mod #1A
return ans
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.79.72.110 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716735423.A.3E3.html
※ 編輯: DJYOSHITAKA (42.79.72.110 臺灣), 05/26/2024 22:58:49