HDU 5015 233 Matrix 矩阵快速幂 - c++编程基础

TOP

HDU 5015 233 Matrix 矩阵快速幂

2015-07-20 17:40:22 来源: 作者: 【大中小】浏览:3次

题意：给一个n*m的矩阵(n ≤ 10,m ≤ 10⁹)，给出矩阵中的A10,A20,A30...，矩阵中的A01=233,A02=2333,A03=23333...对于Aij来说，Aij=Ai-1j+Aij-1，问矩阵中的Anm是多少。

思路：行数只有10，所以可以进行逐列的递推，进行10⁹的递推需要用矩阵快速幂。

递推矩阵：初始矩阵：

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #define eps 1e-8 #define INF 0x7fffffff #define maxn 10005 #define PI acos(-1.0) #define seed 31//131,1313 typedef long long LL; typedef unsigned long long ULL; using namespace std; #define MOD 10000007 #define maxn 15 #define maxm 15 struct Matrix { int n,m; LL a[maxn][maxm]; void init() { n=m=0; memset(a,0,sizeof(a)); } void change(int c,int d) { n=c; m=d; } Matrix operator +(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0; i
                
                 >=1; m.Copy(m*m); } return tmp; } int main() { #ifdef LOCAL freopen(in.txt, r, stdin); //freopen(out.txt, w, stdout); #endif Matrix A,B; int n,m; while(~scanf(%d%d,&n,&m)) { A.init(); B.init(); A.n=n+2; A.m=n+2; A.a[0][0]=10; A.a[0][n+1]=1; for(int i=1; i<=n; i++) { A.a[i][0]=10; for(int j=1; j<=i; j++) A.a[i][j]=1; A.a[i][n+1]=1; } A.a[n+1][n+1]=1; A=M_quick_pow(A,m); B.n=n+2; B.m=1; B.a[0][0]=23; for(int i=1; i<=n; i++) { scanf(%I64d,&B.a[i][0]); B.a[i][0]%=MOD; } B.a[n+1][0]=3; B.Copy(A*B); if(n==0&&m==0) { puts(0); continue; } printf(%I64d ,B.a[n][0]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 3070 矩阵快速幂简单题	下一篇：5进程原语：execl(),execlp(),exe..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: