hdu 5015 233 Matrix(构造矩阵) - c++编程基础

TOP

hdu 5015 233 Matrix(构造矩阵)

2015-07-20 17:39:51 来源: 作者: 【大中小】浏览:2次

因为是个二维的递推式，当时没有想到可以这样构造矩阵。从列上看，当前这一列都是由前一列递推得到。根据这一点来构造矩阵。令b[i]代表第i列，是一个(n+2)*1的矩阵,即b[1] = [1,233......]，之所以在加了两行，是要从前一个矩阵b[i-1]得到b[i]中的第二个数2333...，再构造一个转换矩阵a,它是一个（n+2）*（n+2）的矩阵，那么a^(m-1) * b就是第m列。

/*
a矩阵：
1 0 0 0 0...
3 10 0 0 0...
3 10 1 0 0...
3 10 1 1 0...
3 10 1 1 1...
..

b矩阵：第1列

*/
#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #define LL __int64 //#define LL long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int mod = 10000007; struct matrix { LL mat[15][15]; void init() { memset(mat,0,sizeof(mat)); for(int i = 0; i < 15; i++) { mat[i][i] = 1; } } }a,b,res; int n,m; matrix mul(matrix a, matrix b) { matrix ans; memset(ans.mat,0,sizeof(ans.mat)); for(int i = 0; i < n+2; i++) { for(int k = 0; k < n+2; k++) { if(a.mat[i][k] == 0) continue; for(int j = 0; j < n+2; j++) { ans.mat[i][j] += (a.mat[i][k] * b.mat[k][j])%mod; ans.mat[i][j] %= mod; } } } return ans; } matrix pow(matrix a, int n) { matrix ans; ans.init(); while(n) { if(n&1) ans = mul(ans,a); n >>= 1; a = mul(a,a); } return ans; } int main() { int x; while(~scanf(%d %d,&n,&m)) { memset(b.mat,0,sizeof(b.mat)); b.mat[0][0] = 1; b.mat[1][0] = 233; for(int i = 2; i < n+2; i++) { scanf(%d,&x); b.mat[i][0] = (b.mat[i-1][0] + x%mod)%mod; } memset(a.mat,0,sizeof(a.mat)); a.mat[0][0] = 1; for(int i = 1; i < n+2; i++) { a.mat[i][0] = 3; a.mat[i][1] = 10; for(int j = 2; j <= i; j++) a.mat[i][j] = 1; } res = pow(a,m-1); LL anw = 0; for(int i = 0; i < n+2; i++) { anw += (res.mat[n+1][i] * b.mat[i][0])%mod; anw %= mod; } printf(%I64d ,anw); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：OpenGL之路（五）制作旋转飞机模型	下一篇：POJ 2420 A Star not a Tree? 费..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: