hdu-5015-233 Matrix-矩阵-白红宇

hdu-5015-233 Matrix-矩阵

阅读量：6270 次

发布时间：2019-06-22

本文共 1061 字，大约阅读时间需要 3 分钟。

非常显然矩阵的第一列为：

a[1]

a[2]

a[3]

a[4]

我们转化一下，转化为

a[1]

a[2]

a[3]

a[4]

那么由第一列转移到第二列则为

23*10+3

a[1]+23*10+3

a[2]+a[1]+23*10+3

a[3]+a[2]+a[1]+23*10+3

a[4]+a[3]+a[2]+a[1]+23*10+3

非常显然转移矩阵A就出来了：

10 0 0 0 0 1

10 1 0 0 0 1

10 1 1 0 0 1

10 1 1 1 0 1

10 1 1 1 1 1

0 0 0 0 0 1

那么最后一列就是A的m次方*第一列。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define maxn 110000#define mod 10000007#define LL __int64struct matrix{ LL mat[15][15]; matrix() { memset(mat,0,sizeof(mat)); }};int a[11];int n;matrix mul(matrix A,matrix B){ matrix C; int i,j,k; for(i=1; i<=n+2; i++) { for(j=1; j<=n+2; j++) { for(k=1; k<=n+2; k++) { C.mat[i][j]=(C.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod; } } } return C;}matrix powmul(matrix A,int k){ matrix B; for(int i=1;i<=n+2;i++)B.mat[i][i]=1; while(k>=1) { if(k&1)B=mul(B,A); A=mul(A,A); k=k/2; } return B;}void print(matrix A){ cout<<"matrix A"<