POJ 3233 Matrix Power Series 二分+矩阵乘法-白红宇

POJ 3233 Matrix Power Series 二分+矩阵乘法

阅读量：5943 次

发布时间：2019-06-19

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

链接：

题意：给一个N*N的矩阵（N<=30)，求S = A + A^2 + A^3 + … + A^k(k<=10^9)。

思路：非常明显直接用矩阵高速幂暴力求和的方法复杂度O(klogk)。肯定会超时。我採用的是二分的方法， A + A^2 + A^3 + … + A^k=(1+A^(k/2)) *(A + A^2 + A^3 + … + A^(k/2))。这样就能够提出一个(1+A^(k/2))，假设k是奇数，单独处理A^k。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define PI acos(-1.0)#define maxn 35#define maxm 35#define INF 10005#define eps 1e-8typedef long long LL;typedef unsigned long long ULL;using namespace std;int k,mm;struct Matrix{ int n,m; int a[maxn][maxm]; void init() { n=m=0; memset(a,0,sizeof(a)); } Matrix operator +(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0; i
                  
                   >=1; m=m*m; } return tmp;}int main(){ Matrix A,ans,In,res; while(~scanf("%d%d%d",&A.m,&k,&mm)) { ans.init(); res.init(); res.m=res.n=ans.m=ans.n=In.m=In.n=A.n=A.m; for(int i=0; i

转载地址：http://adwxx.baihongyu.com/

你可能感兴趣的文章