矩阵快速幂(hdu4990)
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
思路:可以得出下面的地推公式
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define eps 1e1000000000000
using namespace std;
typedef long long LL;
struct Matrix
{
LL m[5][5];
}I,B,A,T;//I单位矩阵,B原始矩阵,A取N次幂,T存储结果
LL a,b,n,mod;
int ssize=3;
Matrix Mul(Matrix a,Matrix b)
{
int i,j,k;
Matrix c;
for(i=1;i<=ssize;i++)
{
for(j=1;j<=ssize;j++)
{
c.m[i][j]=0;
for(k=1;k<=ssize;k++)
{
c.m[i][j]+=(a.m[i][k]*b.m[k][j]);
c.m[i][j]%=mod;
}
}
}
return c;
}
Matrix quickpow(Matrix A,int n)
{
Matrix m=A,b=I;
while(n)
{
if(n&1)
b=Mul(b,m);
m=Mul(m,m);
n>>=1;
}
return b;
}
int main()
{
LL x,y;
while(cin >> x >> y)
{
memset(I.m,0,sizeof(I.m));
memset(A.m,0,sizeof(A.m));
memset(B.m,0,sizeof(B.m));
for(int i=0;i<=ssize;i++)
{
I.m[i][i]=1;
}
if(x==1)
{
cout << 1%mod << endl;
continue;
}
else if(x==2)
{
cout << 2%mod << endl;
continue;
}
mod=y;
n=x;
B.m[1][1]=1;
B.m[1][2]=2;
B.m[1][3]=A.m[2][1]=A.m[2][2]=A.m[3][2]=A.m[3][3]=1;
A.m[1][2]=2;
Matrix tmp;
tmp=quickpow(A,n-2);
B=Mul(B,tmp);
cout << B.m[1][2]%mod << endl;
}
return 0;
}