首页 > 代码库 > [矩阵快速幂] hdu 5015 233 Matrix
[矩阵快速幂] hdu 5015 233 Matrix
之前各种犯傻 推了好久这个东西。。
后来灵关一闪 就搞定了。。
矩阵的题目,就是构造矩阵比较难想!
题意:给出一个矩阵的第一列和第一行(下标从0开始),(0,0)位置为0,
第一行为,233,2333,23333...一次加个3,
第一列为输入的n个数。
然后从(1,1)位置开始,等于上面的数加左边的数,问(n+1,m+1)的数是多少,也就是右下角的数
思路:
把矩阵画出来:
| 0 233 2333 |
| b0 b1 b2 |
| c0 c1 c2 |
| d0 d1 d2 |
b1=233+b0,c1=b1+c0=233+b0+c0, d1=c1+d0=233+b0+c0+d0。
那么我们不妨设233为a0,a1=a0*10+3
这样每一项就都是由前面的项的得到了,因为有个常数3,所以再设一个常数1
那么我们就可以构造一个这样的矩阵
| 1 3 0 0 0 |
| 0 10 1 1 1 |
| 1 233 b0 c0 d0 | * | 0 0 1 1 1 | = | 1 2333 b1 c1 d1 |
| 0 0 0 1 1 |
| 0 0 0 0 1 |
这样就是递推下去,前面的乘上后面矩阵的m次方,输出ans.mat[0][n+1] 就ok了!
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"stack" #include"algorithm" #include"iostream" using namespace std; int m=10000007; struct matrix { __int64 mat[15][15]; }; matrix matmul(matrix a,matrix b,int n,int m) //矩阵乘法 n阶矩阵a、b相乘对m取模 { int i,j,k; matrix c; memset(c.mat,0,sizeof(c.mat)); for(i=0;i<n;i++) { for(j=0;j<n;j++) { for(k=0;k<n;k++) { c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; c.mat[i][j]%=m; } } } return c; } matrix matpow(matrix a,int k,int n,int m) //矩阵快速幂取模 n阶矩阵a的k次方对m取模 { matrix b; int i; memset(b.mat,0,sizeof(b.mat)); for(i=0;i<n;i++) b.mat[i][i]=1; while(k) { if(k&1) b=matmul(a,b,n,m); a=matmul(a,a,n,m); k>>=1; } return b; } int main() { int n,k; while(scanf("%d%d",&n,&k)!=-1) { int i,j; matrix a,b,ans; memset(a.mat,0,sizeof(a.mat)); memset(b.mat,0,sizeof(b.mat)); for(i=0;i<n;i++) scanf("%I64d",&a.mat[0][i+2]); a.mat[0][0]=1; a.mat[0][1]=233; b.mat[0][0]=1; b.mat[0][1]=3; b.mat[1][1]=10; for(i=2;i<=n+1;i++) { for(j=1;j<1+i;j++) b.mat[j][i]=1; } ans=matmul(a,matpow(b,k,n+2,m),n+2,m); printf("%I64d\n",ans.mat[0][n+1]); } return 0; }
[矩阵快速幂] hdu 5015 233 Matrix