首页 > 代码库 > hdu 1757 A Simple Math Problem (矩阵快速幂)
hdu 1757 A Simple Math Problem (矩阵快速幂)
和这一题构造的矩阵的方法相同。
需要注意的是,题目中a0~a9 与矩阵相乘的顺序。
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define N 10 using namespace std; int mod; typedef long long LL; struct matrix { LL a[10][10]; }origin; int n=10,m; matrix multiply(matrix x,matrix y) { matrix temp; memset(temp.a,0,sizeof(temp.a)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { for(int k=0;k<n;k++) { temp.a[i][j]+=x.a[i][k]*y.a[k][j]; temp.a[i][j]=(temp.a[i][j])%mod; } } } return temp; } matrix matmod(matrix A,int k) { matrix res; memset(res.a,0,sizeof res.a); for(int i=0;i<n;i++)res.a[i][i]=1; while(k) { if(k&1) res=multiply(res,A); k>>=1; A=multiply(A,A); } return res; } void print(matrix x) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cout<<" "<<x.a[i][j]; puts(""); } printf("---------------\n"); } int main() { int k; while(scanf("%d%d",&k,&mod)!=EOF) { memset(origin.a,0,sizeof origin.a); for(int i=0;i<10;i++) { origin.a[i][0]=i; } //print(origin); matrix res; memset(res.a,0,sizeof res.a); for(int i=0;i<9;i++)res.a[i][i+1]=1; for(int i=9;i>=0;i--)scanf("%d",&res.a[9][i]); //print(res); res=matmod(res,k); matrix ans = multiply(res,origin); printf("%d\n",ans.a[0][0]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。