Python 代码
n, k = map(int, input().split())
mod = 5000011
dp = [[0, 0] for _ in range(n+1)] # dp[i][0] 代表i头牛,最后为牝牛的方案数,dp[i][1]代表最后为牡牛的方案数。
dp[0] = [1, 0]
for i in range(1, n+1):
dp[i][0] = (dp[i-1][1] + dp[i-1][0]) % mod
if i-k-1 > 0:
dp[i][1] = (dp[i-k-1][1] + dp[i-k-1][0]) % mod
else:
dp[i][1] = 1
print(sum(dp[n])%mod)
tql
呜呜呜,我终于找到状态机的写法了!!!