level 13
轩轩醉了
楼主
两场比赛蒟蒻也就这题能AC了，现场还没AC掉，哭瞎了。。。
还是说解法吧
1.暴力模拟，20分
2.矩阵+高精度+快速幂，70～80分。
发现转移方式有两种，那么分开列矩阵。
A=|a b| \n |0 1|
B=|c d| \n |0 1|
C=|1| \n |1|
其中A是第一种递推的，B是第二种递推的C是最后乘的。
那么A^(n-1) 就是一行的转移，再乘B就是一整行的转移，记为X，那么X^(m-1) * C后就能得到结果。
然后要加高精度，可得70～80分。
3.矩阵+快速幂+费马小定理
(a,p)=1则a^(p-1)≡1(mod p)
那么将n对1000000006取模，再用2中说的快速幂，可得满分。
蒟蒻当时没想到费马小定理T_T
2013年07月18日 07点07分
1
还是说解法吧
1.暴力模拟，20分
2.矩阵+高精度+快速幂，70～80分。
发现转移方式有两种，那么分开列矩阵。
A=|a b| \n |0 1|
B=|c d| \n |0 1|
C=|1| \n |1|
其中A是第一种递推的，B是第二种递推的C是最后乘的。
那么A^(n-1) 就是一行的转移，再乘B就是一整行的转移，记为X，那么X^(m-1) * C后就能得到结果。
然后要加高精度，可得70～80分。
3.矩阵+快速幂+费马小定理
(a,p)=1则a^(p-1)≡1(mod p)
那么将n对1000000006取模，再用2中说的快速幂，可得满分。
蒟蒻当时没想到费马小定理T_T
![[委屈]](/static/emoticons/u59d4u5c48.png)
![[吐舌]](/static/emoticons/u5410u820c.png)
![[鬼脸]](/static/emoticons/u9b3cu8138.png)
蒟蒻表示矩阵最后优化成两个变量{a,b} 转移也是{x.a*y.a,x.b*y.a+y.b} 你还在用矩阵么
![[疑问]](/static/emoticons/u7591u95ee.png)
