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 ;

 }

巴特西

hdu4990 Reading comprehension 矩阵快速幂

最新文章

热门文章