Reading comprehension HDU - 4990

Reading comprehension HDU - 4990

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;
}

InputMulti test cases，each line will contain two integers n and m. Process to end of file.
[Technical Specification]
1<=n, m <= 1000000000OutputFor each case，output an integer，represents the output of above program.Sample Input

1 10
3 100

Sample Output       1       5

   题意：就是上面的那个程序， 数据范围很大      思路： 妥妥的矩阵快速幂， Fn = Fn-1 + 2Fn-2 + 1;
   构造矩阵然后用模板就行。



代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<algorithm>
#define maxn 10010
#define INF 0x3f3f3f3f
#define eps 1e-8
#define MOD 1000000007
#define ll long long
using namespace std;


ll mod;
struct Node
{
    ll mat[3][3];
};
Node mul(Node a,Node b)
{
    Node ret;
    memset(ret.mat,0,sizeof ret.mat);
    for(int i=0;i<3;++i)
        for(int j=0;j<3;++j)
        {
            ret.mat[i][j]=0;
            for(int k=0;k<3;++k)
                ret.mat[i][j]=(ret.mat[i][j]+a.mat[i][k]*b.mat[k][j]%mod+mod)%mod;
        }
    return ret;
}
Node Pow(Node a,ll n)
{
    Node ret;
    memset(ret.mat,0,sizeof(ret.mat));
    for(int i=0;i<3;++i)    ret.mat[i][i]=1;
    Node tmp=a;
    while(n)
    {
        if(n&1)ret=mul(ret,tmp);
        tmp=mul(tmp,tmp);
        n>>=1;
    }
    return ret;
}

int main()
{
     ll n,m;
     Node A;
     memset(A.mat,0,sizeof A.mat);
     A.mat[0][0]=A.mat[0][2]=A.mat[1][0]=A.mat[2][2]=1;
     A.mat[0][1]=2;
     Node B;
     memset(B.mat,0,sizeof B.mat);
     B.mat[0][0]=1;B.mat[1][0]=0;B.mat[2][0]=1;
     while(scanf("%lld%lld",&n,&m)!=EOF)
     {
         mod=m;
         Node ans;
         memset(ans.mat,0,sizeof ans.mat);
         ans=mul(Pow(A,n-1),B);
         printf("%lld\n",ans.mat[0][0]);
     }
     return 0;
}