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

矩阵快速幂

 #include<stdio.h>
#include<string.h>
typedef long long ll;
int mod;
struct mat{
int r,c;
ll m[][];
void clear(){
for(int i=;i<=r;i++)memset(m[i],,sizeof(m[i]));
}
}; mat MatMul(mat m1,mat m2){
mat tmp;
tmp.r=m1.r;
tmp.c=m2.c;
int i,j,k;
for(i=;i<=tmp.r;i++){
for(j=;j<=tmp.c;j++){
ll t=;
for(k=;k<=m1.c;k++){
t=(t+(m1.m[i][k]*m2.m[k][j])%mod)%mod;
}
tmp.m[i][j]=t;
}
}
return tmp;
} mat MatQP(mat a,int n){
mat ans,tmp=a;
ans.r=ans.c=a.r;
memset(ans.m,,sizeof(ans.m));
for(int i=;i<=ans.r;i++){
ans.m[i][i]=;
}
while(n){
if(n&)ans=MatMul(ans,tmp);
n>>=;
tmp=MatMul(tmp,tmp);
}
return ans;
} int main(){
mat a;
a.r=;a.c=;
a.m[][]=;
a.m[][]=;
a.m[][]=;
mat t;
t.r=;
t.c=;
t.clear();
t.m[][]=;
t.m[][]=;
t.m[][]=;
t.m[][]=;
t.m[][]=;
int n;
while(scanf("%d%d",&n,&mod)!=EOF){
mat tmp=MatQP(t,n/);
tmp=MatMul(tmp,a);
printf("%lld\n",tmp.m[n%+][]);
}
return ;
}
上一篇:hdu 4990 Reading comprehension(等比数列法)


下一篇:最短路 HDU 2544