首页 > 代码库 > HDU 5015 233 Matrix --矩阵快速幂
HDU 5015 233 Matrix --矩阵快速幂
题意：给出矩阵的第0行（233,2333,23333,...）和第0列a1,a2,...an（n<=10，m<=10^9），给出式子： A[i][j] = A[i-1][j] + A[i][j-1]，要求A[n][m]。
解法：看到n<=10和m<=10^9 应该对矩阵有些想法，现在我们假设要求A[a][b],则A[a][b] = A[a][b-1] + A[a-1][b] = A[a][b-1] + A[a-1][b-1] + A[a-2][b] = ...
这样相当于右图：
，红色部分为绿色部分之和，而顶上的绿色部分很好求，左边的绿色部分(最多10个)其实就是：A[1][m-1],A[2][m-1]..A[n][m-1],即对每个1<=i<=n, A[i][m]都可由A[1][m-1],A[2][m-1]..A[n][m-1]，于是建立12*12的矩阵：
，将中间矩阵求m-1次幂，与右边[A[0][1],A[1][1]..A[n][1],3]^T相乘，结果就可以得出了。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define Mod 10000007#define SMod Mod#define lll __int64using namespace std;int n,m;lll a[100006],sum[100005];struct Matrix{ lll m[13][13]; Matrix() { memset(m,0,sizeof(m)); for(int i=1;i<=n+2;i++) m[i][i] = 1LL; }};Matrix Mul(Matrix a,Matrix b){ Matrix res; int i,j,k; for(i=1;i<=n+2;i++) { for(j=1;j<=n+2;j++) { res.m[i][j] = 0; for(k=1;k<=n+2;k++) res.m[i][j] = (res.m[i][j]+(a.m[i][k]*b.m[k][j])%SMod + SMod)%SMod; } } return res;}Matrix fastm(Matrix a,int b){ Matrix res; while(b) { if(b&1) res = Mul(res,a); a = Mul(a,a); b >>= 1; } return res;}int main(){ int i,j; while(scanf("%d%d",&n,&m)!=EOF) { sum[0] = 0; for(i=1;i<=n;i++) { scanf("%I64d",&a[i]); sum[i] = (sum[i-1] + a[i]); } lll suma = sum[n]; if(m == 1) { printf("%I64d\n",(233LL+suma)%Mod); continue; } Matrix base; memset(base.m,0,sizeof(base.m)); for(i=1;i<=n+1;i++) base.m[i][1] = 10LL; for(i=2;i<=n+1;i++) { for(j=2;j<=n+1;j++) { if(i >= j) base.m[i][j] = 1LL; } } for(i=1;i<=n+2;i++) base.m[i][n+2] = 1LL; Matrix Right; memset(Right.m,0,sizeof(Right.m)); Right.m[1][1] = 233LL; for(i=2;i<=n+1;i++) Right.m[i][1] = (233LL+sum[i-1])%Mod; Right.m[n+2][1] = 3LL; Matrix ans = fastm(base,m-1); ans = Mul(ans,Right); printf("%I64d\n",ans.m[n+1][1]%Mod); } return 0;}
HDU 5015 233 Matrix --矩阵快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。