对于2113n不大，可以5261直接用递推来解决

 

 
 

 但是这道题目n比较大是165310^10
 
 

 直接这么跑的话，时间有点接受不了
 
 

 那么就要高一点手段了。
 
 

 可以寫出一下两个等式：
 
 

 
 

 
 

 
 

 这么表示的意义在于可以写成一个转移矩阵：
 
 

 
 
 

 
 

 
 
 

 现在我们只需要能快速地处理中间那个矩阵的n-2次方
 
 

 就可以快速求出数列的第n项了
 
 

 假如要求a的b次方（这里写成a^b）：
 
 

 
 

 11表示成二进制为1011
 
 

 
 
 

 
 

 
 
 

 所以，只需将a不断平方在二进制那一位是1的乘到结果里就可以了
 
 

 这段的C代码昰这样的（为了不溢出，中间mod66666）
 
 

下载百度知道APP抢鲜体验

使用百度知道APP，立即抢鲜体验你的手机镜头里或许有别人想知道的答案。