首页 > 代码库 > hdu 4990 Reading comprehension
hdu 4990 Reading comprehension
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4990
思路:题目难点就是找矩阵。。。。。
code:
#include<cstdio> #include<iostream> #include<cstring> using namespace std; typedef long long LL; struct Matrix { LL x[5][5]; friend Matrix operator*(Matrix &a,Matrix &b); friend Matrix operator*(Matrix a,LL k); }; int n,mod; Matrix operator*(Matrix &a,Matrix &b) { Matrix c; int i,j,k; for(i=1;i<=3;i++) { for(j=1;j<=3;j++) { c.x[i][j]=0; for(k=1;k<=3;k++) { c.x[i][j]=(c.x[i][j]+(a.x[i][k]*b.x[k][j])%mod)%mod; } } } return c; } Matrix operator^(Matrix a,LL k) { Matrix unit; memset(unit.x,0,sizeof(unit.x)); for(int i=0;i<=3;i++) { unit.x[i][i]=1; } while(k>0) { if(k&1) unit=unit*a; a=a*a; k=k/2; //printf("AAAAA\n"); } return unit; } Matrix A,B; int main() { while(scanf("%d%d",&n,&mod)==2) { memset(A.x,0,sizeof(A.x)); A.x[1][2]=2,A.x[2][1]=1,A.x[2][2]=1; A.x[3][2]=A.x[3][3]=1; B.x[1][1]=1%mod; B.x[1][2]=2%mod; B.x[1][3]=1; if(n==1) printf("%lld\n",B.x[1][1]); else if(n==2) { printf("%lld\n",B.x[1][2]); } else { A=A^(n-2); B=B*A; printf("%lld\n",B.x[1][2]%mod); } } return 0; }
hdu 4990 Reading comprehension
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。