HDUOJ 4990 Reading comprehension
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
看到n,m的范围立刻想到要用矩阵快速幂，为理解透彻，我将两种类型的矩阵都打了出来：
n为奇数时变换矩阵A：
[Fn1]=[2011][Fn−11]
n为偶数时变换矩阵B：
[Fn1]=[2001][Fn−11]
那么我们不难发现，只要把这两个矩阵乘起来 A∗B 就是总的变换矩阵，变换次数即为 n/2，但要注意 n 为奇数时要再左乘一次 A，注意左右乘即可，AC代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2;//矩阵的大小
ll n,mod;
struct mat
{
ll m[N][N];
}odd,even,a,ans;
mat mul(mat a,mat b)
{
mat tmp;
memset(tmp.m,0,sizeof(tmp.m));
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
{
tmp.m[i][j]=(tmp.m[i][j]%mod+a.m[i][k]*b.m[k][j]%mod)%mod;
if(tmp.m[i][j]<0) tmp.m[i][j]=(tmp.m[i][j]+mod)%mod;//防越界
}
return tmp;
}
void mat_pow(mat a,ll k)
{
memset(ans.m,0,sizeof(ans.m));
ans.m[0][0]=0,ans.m[1][0]=1;
while(k>0)
{
if(k&1) ans=mul(a,ans);
a=mul(a,a);
k>>=1;
}
}
int main(){
while(cin>>n>>mod){
n++;
even.m[0][0]=2,even.m[0][1]=1,even.m[0][2]=0,even.m[0][3]=1;
odd.m[0][0]=2,odd.m[0][1]=0,odd.m[0][2]=0,odd.m[0][3]=1;
a=mul(even,odd);
mat_pow(a,n/2);
if(n%2) ans=mul(odd,ans);
cout<<ans.m[0][0]<<endl;
}
}