这题求个题解【加米】

有个物种被创造后要hibernate 4天，hibernation结束后在接下来的4天中每天生成一个后代，然后永远休眠，求在N天时一共生成过有多少个？

首先用状态 s_1, ..., s_8 表示物种个体处于前8天中的第几天，用 s_h 表示8天后的休眠状态

定义 c(s, k) 为第k天时处于状态 s 的个体数量总和，那么

1. (1) 初始条件
   
2. 
   
3. c(s_1, 1) = 1
   
4. 
   
5. c(s_i, 1) = 0, for all 2 <= i <= 8
   
6. 
   
7. c(s_h, 1) = 0
   
8. 
   
9. (2) 状态转移方程
   
10. 
    
11. c(s_1, k) = c(s_4, k-1) + c(s_5, k-1) + c(s_6, k-1) + c(s_7, k-1)
    
12. 
    
13. c(s_i, k) = c(s_{i-1}, k-1), for all 2 <= i <= 8
    
14. 
    
15. c(s_h, k) = c(s_8, k-1) + c(s_h + k-1)
    
16. 
    
17. (3) 第N天的总数即是第N天处于各个状态的个体数量之和
    
18. 
    
19. c(s_1, N) + ... + c(s_8， N) + c(s_h, N)
    

复制代码

计算上可以 O(N) 递推，也可以写成矩阵幂形式，那么可以做到 O(log N）