【HDU - 4990】【Reading comprehension】

题目：

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

题意：优化题目中所给的代码。切忌千万不要直接粘上去，哇哈哈哈。

解题思路：由测试数据就可以得到一个递推公式 Fn = Fn-1 + 2 * Fn-2 + 1.

矩阵快速幂就可以写出来。

|Fn     |     |   1     2     1  |    | Fn-1 |

|Fn-1 |=    |  1    0      0   |*   |Fn-2 |

|1      |      |     0    0     1 |     |  1    |

 

ac代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define maxn 200000
using namespace std;
long long int m;
struct Mat{
	long long int mat[3][3];
};
Mat mul(Mat a,Mat b)
{
	Mat t;
	memset(t.mat,0,sizeof(t.mat));
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
		{
			for(int k=0;k<3;k++)
			{
				t.mat[i][j]+=(a.mat[i][k]*b.mat[k][j])%m;
				t.mat[i][j]%=m;
			}
		}
	return t;
}
Mat ksm(Mat a,long long int n)
{
	Mat tt;
	memset(tt.mat,0,sizeof(tt.mat));
	for(int i=0;i<3;i++)
		tt.mat[i][i]=1;
	while(n)
	{
		if(n&1) tt=mul(a,tt);
		a=mul(a,a);
		n>>=1; 
	}
	return tt;
}
int main()
{
	long long int n;
	while(scanf("%lld%lld",&n,&m)!=EOF)
	{
		Mat a;
		memset(a.mat,0,sizeof(a.mat));
		a.mat[0][0]=a.mat[1][0]=a.mat[0][2]=a.mat[2][2]=1;
		a.mat[0][1]=2;
		if(n==1)
			printf("%lld\n",1%m);
		else if(n==2)
			printf("%lld\n",2%m);
		else
		{
			a=ksm(a,n-2);
			printf("%lld\n",(a.mat[0][0]*2%m+a.mat[0][1]%m+a.mat[0][2]%m)%m);
		}
	}
	return 0;
}