先看没有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