hdu 4990 Reading comprehension (构造矩阵，快速幂)
题意：
给出了一段程序，程序实际算的是f[n] = (f[n-1] + n%2)%m的值，其中f[1]=1,给出n,m(1E9)，问f[n]
思路：
显然是矩阵快速幂，终点在于构造矩阵。
通过经验可得（这次真的是经验了。。。其实也挺容易的，要点大概在于先把需要的项列在一起，然后增加0或者多个，为了转移需要的辅助项。
根据当前列和下一列，手动构造转移矩阵）
转移矩阵M为
[2, 1,0]
[0,-1,1]
[0,0 ,1]
4A..都是一个原因。。矩阵乘法那里。。。就算你%了m..也是两个1E9在相乘。。。然后就炸了23333,改成LL即可。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年09月30日 星期六 19时08分59秒
4File Name :4990.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;le
34int n;
35LL mod;
36struct Mat
37{
38 LL mat[8][8];
39 void clear()
40 {
41 ms(mat,0);
42 }
43}M,M1;
44
45Mat operator * (Mat a,Mat b)
46{
47 Mat c;
48 c.clear();
49 for ( int i = 0 ; i < 3 ; i++)
50 for ( int j = 0 ; j < 3 ; j++)
51 for ( int k = 0 ; k < 3 ; k++)
52 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k]%mod*b.mat[k][j]%mod)%mod;
53 return c;
54}
55Mat operator ^ (Mat a,int b)
56{
57 Mat ret;
58 ret.clear();
59 for ( int i = 0 ; i < 3 ; i++) ret.mat[i][i] = 1;
60
61 while (b>0)
62 {
63 if (b&1) ret = ret * a;
64 a = a * a;
65 b=b>>1;
66 }
67 return ret;
68}
69LL solve()
70{
71 M.clear();
72 M1.clear();
73 M.mat[0][0]=2;
74 M.mat[0][1]=1;
75 M.mat[1][1]=-1;
76 M.mat[1][2]=1;
77 M.mat[2][2]=1;
78
79 M1.mat[0][0]=1;
80 M1.mat[2][0]=1;
81
82 Mat ans;
83 ans.clear();
84 ans = (M^(n-1))*M1;
85 return ans.mat[0][0]%mod;
86}
87int main()
88{
89 #ifndef ONLINE_JUDGE
90 //freopen("./in.txt","r",stdin);
91 #endif
92 while (~scanf("%d %lld",&n,&mod))
93 {
94 LL ans = solve();
95 ans = (ans % mod + mod)%mod;
96 printf("%lld\n",ans);
97 }
98
99
100 #ifndef ONLINE_JUDGE
101 fclose(stdin);
102 #endif
103 return 0;
104}