hdu 4291 A Short problem (成都网络赛 矩阵乘法 递推式 求 循环节)
http://acm.hdu.edu.cn/showproblem.php?pid=4291
题意：
A Short problem
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 739Accepted Submission(s): 277
Problem Description According to a research, VIM users tend to have shorter fingers, compared with Emacs users.
Hence they prefer problems short, too. Here is a short one:
Given n (1 <= n <= 1018), You should solve for
g(g(g(n))) mod 109 + 7
where
g(n) = 3g(n - 1) + g(n - 2)
g(1) = 1
g(0) = 0
Hence they prefer problems short, too. Here is a short one:
Given n (1 <= n <= 1018), You should solve for
where
Input There are several test cases. For each test case there is an integer n in a single line.
Please process until EOF (End Of File).
Please process until EOF (End Of File).
Output For each test case, please print a single line with a integer, the corresponding answer to this case.
Sample Input
0 1 2Sample Output0 1 42837题解： 首先 看到 它是 三层 求 g(n); 因为 每一层 g(g(n)) 与 g(g(n)% 10^9 + 1) 不一定相同 ，所以 我们要 求出 内层的 循环节；
在 最外层 为 10^9 + 7 的情况下 ，我们 可以 求出 次外 层的 循环节 是 222222224 在将 222222224 带入 可以求出 最内层的 循环节 ，为183120 ；
1//求循环节
2#include<cstdio>
3#include<set>
4const__int64M=222222224;
5usingnamespacestd;
6__int64a[4],b[4];
7
8intmain()
9{
10set<__int64>se;
11__int64i;
12__int64f1=1,f0=0;
13for(i=2;;++i)
14{
15__int64f2=(3*f1+f0)%M;
16if(f1==0&&f2==1)break;
17f0=f1;f1=f2;
18}
19printf("%I64d\n",i-1);
20return0;
21}在 矩阵乘法 时由于 将 成的 次数 忘了 变为 long long 的 错了 好几次 。。。。。。。。。。。。。。。。
1#include<cstdio>
2#include<cstring>
3#include<cmath>
4#include<iostream>
5#include<algorithm>
6#include<set>
7#include<map>
8#include<queue>
9#include<vector>
10#include<string>
11#defineMin(a,b)a<b?a:b
12#defineMax(a,b)a>b?a:b
13#defineCL(a,num)memset(a,num,sizeof(a));
14#defineeps1e-12
15#defineinf10000000
16
17
18//freopen("data.txt","r",stdin);
19constdoublepi=acos(-1.0);
20typedef__int64ll;
21constintmaxn=101000;
22usingnamespacestd;
23structmatrix
24{
25llm[2][2];
26
27};
28intn=2;
29llmod;
30matrixe;
31voidinit()
32{
33e.m[0][0]=1;
34e.m[0][1]=0;
35e.m[1][0]=0;
36e.m[1][1]=1;
37}
38
39matrixmtmul(matrixa,matrixb)
40{
41
42matrixc;
43inti,j,k;
44for(i=0;i<n;i++)
45{
46for(j=0;j<n;j++)
47{
48c.m[i][j]=0;
49for(k=0;k<n;k++)
50{
51c.m[i][j]+=a.m[i][k]*b.m[k][j];
52c.m[i][j]%=mod;
53}
54}
55}
56
57
58returnc;
59}
60matrixmtpow(matrixd,llk)
61{matrixa;
62
63
64a=e;//e为单位矩阵
65while(k)
66{
67if(k&1)
68{
69a=mtmul(a,d);
70}
71k/=2;
72d=mtmul(d,d);
73}
74returna;
75
76}
77
78intmain()
79{
80llnum;
81init();
82//freopen("data.txt","r",stdin);
83
84//freopen("out.txt","w",stdout);
85while(cin>>num)
86{
87
88if(num==0){printf("0\n");continue;}
89if(num==1){printf("1\n");continue;}
90
91matrixa,c,d,b;
92
93a.m[0][0]=3;
94a.m[0][1]=1;
95a.m[1][0]=1;
96a.m[1][1]=0;
97
98b.m[0][0]=1;
99b.m[0][1]=0;
100b.m[1][0]=0;
101b.m[1][1]=0;
102mod=183120;
103c=mtpow(a,num-1);
104num=c.m[0][0];
105
106
107if(c.m[0][0]==0){printf("0\n");continue;}
108if(c.m[0][0]==1){printf("1\n");continue;}
109
110
111
112
113mod=222222224;
114c=mtpow(a,num-1);
115
116num=c.m[0][0];
117
118
119if(c.m[0][0]==0){printf("0\n");continue;}
120if(c.m[0][0]==1){printf("1\n");continue;}
121
122
123
124
125mod=1000000007;
126c=mtpow(a,num-1);
127
128
129num=c.m[0][0];
130if(c.m[0][0]==0){printf("0\n");continue;}
131if(c.m[0][0]==1){printf("1\n");continue;}
132
133
134cout<<num<<endl;
135
136}
137} 优质内容筛选与推荐>>
1、Ambari安装常见问题
2、C#3.0语言层面的增强
3、[设计模式]在CodeDom代码生成中使用Decorator模式实现类型创建
4、超级好用的grep
5、解决【win10管理员已阻止程序运行】问题时有感