这个递推式如何优化?
  • 板块学术版
  • 楼主Error_666
  • 当前回复12
  • 已保存回复12
  • 发布时间2020/8/19 21:45
  • 上次更新2023/11/6 19:53:44
查看原帖
这个递推式如何优化?
91681
Error_666楼主2020/8/19 21:45

已知:

对于任意(i1)(i-1) % 4 != 0有:

fi=fi1+fi4f_{i} = f_{i-1} + f_{i-4}

对于任意(i1)(i-1) % 4 =0有:

fi=fi1+fi5f_{i} = f_{i-1} + f_{i-5}

特殊的,f1,f2,f3,f4,f5f_1, f_2, f_3, f_4, f_5题目将给出

fnf_n,保证n%4为0,n<=10910^9


O(n)被出题人卡了,感觉可以矩阵?但我构造不出/dk

2020/8/19 21:45
加载中...