POJ 3233 Matrix Power Series(矩阵高速功率+二分法)-白红宇

POJ 3233 Matrix Power Series(矩阵高速功率+二分法)

阅读量：5306 次

发布时间：2019-06-14

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

职务地址：

题目大意：给定矩阵A，求A + A^2 + A^3 + … + A^k的结果（两个矩阵相加就是相应位置分别相加）。输出的数据mod m。

k<=10^9。

这道题两次二分，相当经典。首先我们知道，A^i能够二分求出。

然后我们须要对整个题目的数据规模k进行二分。比方，当k=6时，有：

A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)

应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3。就可以得到原问题的答案。

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;int mod;int n;struct matrix{ int ma[40][40];}init, res;matrix Mult(matrix x, matrix y){ int i, j, k; matrix tmp; memset(tmp.ma,0,sizeof(tmp.ma)); for(i=0;i
                
                 >=1; } return tmp;}matrix add(matrix x, matrix y){ int i, j; matrix tmp; for(i=0;i