Reading comprehension

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2072    Accepted Submission(s): 827 Problem Description Read the program below carefully then answer the question. #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include<iostream> #include <cstring> #include <cmath> #include <algorithm> #include<vector> const int MAX=100000*2; const int INF=1e9; int main() {   int n,m,ans,i;   while(scanf("%d%d",&n,&m)!=EOF)   {     ans=0;     for(i=1;i<=n;i++)     {       if(i&1)ans=(ans*2+1)%m;       else ans=ans*2%m;     }     printf("%d\n",ans);   }   return 0; }   Input Multi test cases，each line will contain two integers n and m. Process to end of file. [Technical Specification] 1<=n, m <= 1000000000   Output For each case，output an integer，represents the output of above program.   Sample Input 1 10 3 100   Sample Output 1 5  

思路：

先用源程序跑几个数出来！1， 2， 5， 10， 21， 42 好了，再用这几个数字找他们的通项式 #include <iostream> #include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <bitset> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <algorithm> #include <functional> #define PI acos(-1) #define eps 1e-8 #define inf 0x3f3f3f3f #define debug(x) cout<<"---"<<x<<"---"<<endl typedef long long ll; ll mod; struct matrix { ll mat[5][5]; matrix() { memset(mat, 0, sizeof(mat)); } int R, C; matrix operator*(matrix other); }; matrix matrix::operator*(matrix other) { matrix c; for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) for (int k = 1; k <= C; k++) { c.mat[i][j] = (c.mat[i][j] + mat[i][k] * other.mat[k][j] % mod) % mod; } c.R = R; c.C = other.C; return c; } matrix fast_mod(matrix base, int k) { matrix tmp; tmp.R = tmp.C = 3; for (int i = 1; i <= 3; i++) { tmp.mat[i][i] = 1; } while (k) { if (k & 1) { tmp = tmp * base; } base = base * base; k >>= 1; } return tmp; } int main() { int n; while (~scanf("%d%I64d", &n, &mod)) { matrix ans, base; ans.R = 1; ans.C = 1; base.R = base.C = 3; if (n == 1) { printf("%d\n", 1 % mod); } else if (n == 2) { printf("%d\n", 2 % mod); } else { ans.R = 1; ans.C = 3; ans.mat[1][1] = 1; ans.mat[1][2] = 2; ans.mat[1][3] = 1; base.mat[2][3] = base.mat[1][1] = base.mat[1][2] = base.mat[1][3] = 0; base.mat[2][1] = 2; base.mat[2][2] = 4; base.mat[3][1] = base.mat[3][3] = 1; base.mat[3][2] = 2; int k = (n - 2) / 2; if (n & 1) { base = fast_mod(base, k + 1); ans = ans * base; printf("%I64d\n", ans.mat[1][1]); } else { base = fast_mod(base, k); ans = ans * base; printf("%I64d\n", ans.mat[1][2]); } } } return 0; }