网站上的销售怎么做,万网网站空间服务范围,潍坊网站制作报价,注册网站账号违法吗求通项和斐波那契数列的方法一样#xff0c;矩阵快速幂。 这道题麻烦在套了三层。 但其实取模这种操作肯定会出现循环的#xff0c;可以先本地暴出循环节#xff0c;1000000007对应的循环节是222222224#xff0c;222222224对应的循环节是183120。 最外层的结果是对1000000…求通项和斐波那契数列的方法一样矩阵快速幂。 这道题麻烦在套了三层。 但其实取模这种操作肯定会出现循环的可以先本地暴出循环节1000000007对应的循环节是222222224222222224对应的循环节是183120。 最外层的结果是对1000000007取模它的内层对222222224取模可以得到相等的答案那么222222224的内层对183120取模也能得到相等的答案这样就是分别对三个模数做矩阵快速幂内层得到的结果返回给外层作为指数。 1 #includestdio.h2 #includestdlib.h3 #includestring.h4 typedef __int64 LL;5 struct Matrix6 {7 LL Mt[2][2];8 void init0(){memset(Mt, 0, sizeof(Mt));}9 void init1() {init0(), Mt[0][0] Mt[1][1] 1;}
10 Matrix(){init0();}
11 Matrix(LL num) {init0();Mt[0][0] Mt[1][1] num;}
12 Matrix(LL a, LL b, LL c, LL d){Mt[0][0] a, Mt[0][1] b, Mt[1][0] c, Mt[1][1] d;}
13 Matrix Mul(const Matrix b, LL mod)
14 {
15 int i, j, k;Matrix res;
16 for(i 0; i 2; i)
17 for(j 0; j 2; j)
18 for(k 0; k 2; k)
19 res.Mt[i][j] (res.Mt[i][j] Mt[i][k] * b.Mt[k][j]) % mod;
20 return res;
21 }
22 Matrix Rep(LL p, LL mod)
23 {
24 Matrix b *this, res(1);
25 if(p 0) return res;
26 if(p 1) return b;
27 while(p 1)
28 {
29 if(p 1) res res.Mul(b, mod);
30 b b.Mul(b, mod);
31 p 1;
32 }
33 return b.Mul(res, mod);
34 }
35 };
36 LL Cal(LL n, LL mod)
37 {
38 Matrix mm(3, 1, 1, 0), ori(1, 0, 0, 0);
39 if(!n) return 0;
40 return ori.Mul(mm.Rep(n - 1, mod), mod).Mt[0][0];
41 }
42 int main()
43 {
44 LL n;
45 while(scanf(%I64d, n) ! EOF)
46 printf(%I64d\n, Cal(Cal(Cal(n, 183120), 222222224), 1000000007));
47 return 0;
48 } 转载于:https://www.cnblogs.com/CSGrandeur/archive/2012/09/16/2687739.html
