首页 > 代码库 > Hdu 5015 233 Matrix 矩阵快速幂
Hdu 5015 233 Matrix 矩阵快速幂
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5015
题目大意:给你一个n*m(n<=10,m<=10^9)的矩阵,第一行的元素为233,2333,23333.。。。,第一列的元素为 给定的已知的元素,求a[n][m],其中a[i][j]=a[i-1][j]+a[i][j-1];
解题思路:由于n较小,所以我们可以一列一列的推,即矩阵递推如下:
/** 本题是一个n * m的矩阵(m比较大) a[0][1]=233 a[0][2]=2333 ... a[1][0] a[1][1] a[2][0] a[2][1] a[3][0] a[3][1] a[4][0] a[4][1] . . { 10 0 0 0 1 } . { 1 1 0 0 0 } {2333,a[1][1],a[2][1],a[3][1],.....,3}= {233,a[1][0],a[2][0],a[3][0],.....,3} * { 1 1 1 0 0 } ; { 1 1 1 1 0 } { 0 0 0 0 1 } **/代码如下:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long int n,m; struct mat { LL ma[12][12]; }; mat init(mat x) { memset(x.ma,0,sizeof(x.ma)); x.ma[0][0]=10; x.ma[0][n+1]=1; for(int i=1;i<=n;i++) for(int j=0;j<=i;j++) x.ma[i][j]=1; x.ma[n+1][n+1]=1; return x; } mat cal(mat a,mat b) { mat c; memset(c.ma,0,sizeof(c.ma)); for(int i=0;i<=(n+1);i++) for(int k=0;k<=(n+1);k++) for(int j=0;j<=(n+1);j++) c.ma[i][j]=(c.ma[i][j]+a.ma[i][k]*b.ma[k][j])%10000007; return c; } mat pow(mat a,int k) { mat e; memset(e.ma,0,sizeof(e.ma)); for(int i=0;i<=n+1;i++) e.ma[i][i]=1; while(k>0) { if(k&1) e=cal(e,a); a=cal(a,a); k>>=1; } return e; } int main() { int a[13]; while(~scanf("%d%d",&n,&m)) { a[0]=233; for(int i=1;i<=n;i++) scanf("%I64d",&a[i]); a[n+1]=3; mat x; x=init(x); x=pow(x,m); LL ans=0; for(int i=0;i<=n+1;i++) ans=(ans+x.ma[n][i]*a[i])%10000007; printf("%I64d\n",ans); } return 0; }
Hdu 5015 233 Matrix 矩阵快速幂
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。