acdream 1060 递推数 （矩阵快速幂+循环节）

acdream 1060 递推数 （矩阵快速幂+循环节）

链接：​​click here~~​​

题意：

递推数 Problem Description 已知A(0) = 0 , A(1) = 1 , A(n) = 3 * A(n-1) + A(n-2) (n ≥ 2)    求 A(A(A(A(N)))) Mod (1e9 + 7) Input 第一行一个整数 T (T ≤ 10000) 代表数据组数 每组数据占一行，一个整数 n (1 ≤ n ≤ 1e12) Output 对于每组测试数据输出一个整数。 Sample Input 4 1 23574 27870 913 Sample Output 1 0 0 1

【解题思路】：

个人赛第八场的题目，当时没有做出来，赛后做了一下，发现此题需要处理循环节的问题

循环节：当对一个数取摸的操作中，必然会出现循环节的问题，比如要对5取摸，当数超过5个的时候

比如说6，那么1对5取模和6是一样的结果。

这种题，简单来说就是看嵌套有几层，循环节就要找几个，

第一次是MOD1=1000000007 找出循环节是222222224

第二次是MOD2=222222224，找出循环节183120

第三次是MOD3=183120，找出循环节240

找循环节暴力找就可以了，矩阵乘法找循环节比较慢。

Matrix p1= {0,1,1,3};公式矩阵怎么来的呢？

由题目给出关系：A(n) = 3 * A(n-1) + A(n-2)

构造矩阵：（A(n),A(n-1)）=(A(n-1).A(n-2))*(3 0

1 1)

//寻找循环节代码：

#include#include#include#includeusing namespace std;int main(){ long long int g3,g2=1,g1=0; for(int i=2;;i++) { g3=(3*g2+g1)%1000000007; if(g3==1&&g2==0) { printf("循环节L1：%lld\n", i - 1); break; } g1=g2; g2=g3; } long long int gg3,gg2=1,gg1=0; for(int i=2;;i++) { gg3=(3*gg2+gg1)%222222224; if(gg3==1&&gg2==0) { printf("循环节L2：%lld\n", i - 1); break; } gg1=gg2; gg2=gg3; } long long int ggg4,ggg3=3,ggg2=1,ggg1=0; for(int i = 2; ; i++) { ggg4= (3 * ggg3 + ggg2) %183120 ; if(ggg4== 1 && ggg3 == 0) { printf("循环节L3：%lld\n", i - 1); break; } ggg2 = ggg3; ggg3= ggg4; }}

代码：

#include #include #include #include #include using namespace std;#define LL long longconst long long mod1=1e9+7;//循环节const long long mod2=222222224;const long long mod3=183120;const long long mod4=240;struct Matrix{ long long mapp[2][2];};Matrix p= {0,1,1,0}; //左边矩阵Matrix p1= {0,1,1,3};//公式矩阵Matrix unin= {1,0,0,1};//单位矩阵Matrix powmul(Matrix a,Matrix b,long long mod){ Matrix c; for(int i=0; i<2; i++) for(int j=0; j<2; j++) { c.mapp[i][j]=0; for(int k=0; k<2; k++) c.mapp[i][j]+=(a.mapp[i][k]*b.mapp[k][j])%mod; c.mapp[i][j]%=mod; } return c;}Matrix powexp(long long n,long long mod)//关键点{ Matrix m=p1,b=unin; while(n) { if(n&1) b=powmul(b,m,mod); n>>=1; m=powmul(m,m,mod); } return powmul(p,b,mod);}long long n;int main(){ int T; scanf("%d",&T); while(T--) { scanf("%lld",&n); Matrix ans; ans=powexp(n,mod4);//从里面往外面推出 ans=powexp(ans.mapp[0][0],mod3); ans=powexp(ans.mapp[0][0],mod2); ans=powexp(ans.mapp[0][0],mod1); printf("%lld\n",ans.mapp[0][0]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。