POJ 3233 (矩阵)-白红宇

POJ 3233 (矩阵)

阅读量：6284 次

发布时间：2019-06-22

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

题意：对于矩阵A，求A^1 + ...... + A^k

按照的思路大致做了下。

在k为奇数时： A^（ k / 2+1）+ 1） * （A^1 + ....... A^(k/2)） + A^（k/2+1）

k为偶数时：（A^（k/2） + 1 ）* （A^1 + ................A^（k/2））

但是超时了，应该是没二分的问题。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long ll;const int maxn=5e5;map
                  
                   has;struct Matrix{ int xmap[30][30];};int siz;Matrix mat;int n,mod;Matrix Mul(const Matrix &a,const Matrix &b){ Matrix c; for(int i=0; i
                   
                    >1); return Mul(tmp,tmp); }}Matrix Add(const Matrix &a,const Matrix &b){ Matrix c; for(int i=0; i