首页 > 代码库 > hdu 5015 233 Matrix (矩阵快速幂)
hdu 5015 233 Matrix (矩阵快速幂)
题意: 有一种矩阵,它的第一行是这样一些数:a 0,0 = 0, a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333... 除此之外,在这个矩阵里, 我们有 a i,j = a i-1,j +a i,j-1( i,j ≠ 0).现在给你 a 1,0,a 2,0,...,a n,0, 你能告诉我a n,m 是多少吗? n,m(n ≤ 10,m ≤ 10 9)输出 a n,m mod 10000007.
思路:首先我们观察n和m的取值范围,会发现n非常小而m却非常大,如果能从左往右递推就好了,然而我们是可以实现的
观察第一列 我们可以将其变化一下 那么第二列 我们再将他们看成新的ai
0 23 23*10+3 就可以进行递推了
a1 a1 23*10+3+a1
a2 a2 23*10+3+a1+a2
a3 a3 23*10+3+a1+a2+a3
a4 a4 23*10+3+a1+a2+a3+a4
... ... ...
an an 23*10+3+a1+..an
构造矩阵
anm 1 1 1 .......1 10 1 anm-1
an-1m 0 1 1 .......1 10 1 an-1m-1
an-2m 0 0 1 .......1 10 1 an-2m-1
an-3m = 0 0 0........1 10 1 an-3m-1
... ........................... ......
a0m 0 0 0 .......0 10 1 a0m-1
3 0 0 0 .......0 0 1 3
代码:
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define ll long long #define mod 10000007 using namespace std; int N,M,P; struct Matrix { ll m[12][12]; }; Matrix I,A; Matrix multi(Matrix a,Matrix b) { Matrix ans; for(int i=0;i<N;i++) { for(int j=0;j<M;j++) { ans.m[i][j]=0; for(int k=0;k<P;k++) { ans.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod; } ans.m[i][j]%=mod; } } return ans; } Matrix power(Matrix a,ll b) { Matrix ans=I; while(b) { if(b&1) { ans=multi(ans,a); } b=b/2; a=multi(a,a); } return ans; } int main() { int n,m; int a[12]; while(cin>>n>>m) { for(int i=0;i<n;i++) { cin>>a[i]; } memset(A.m,0,sizeof(A.m)); for(int i=0;i<=n+1;i++) { for(int j=i;j<=n+1;j++) { if(j!=n) A.m[i][j]=1; else A.m[i][j]=10; } } memset(I.m,0,sizeof(I.m)); for(int i=0;i<=n+1;i++) I.m[i][i]=1; N=M=P=n+2; Matrix ans=power(A,m); ll num=0; for(int i=0;i<n;i++) num=(num+(ans.m[0][i]*a[n-i-1])%mod)%mod; num=(num+(ans.m[0][n]*23)%mod)%mod; num=(num+(ans.m[0][n+1]*3)%mod)%mod; cout<<num<<endl; } return 0; }
hdu 5015 233 Matrix (矩阵快速幂)