POJ-3233 Matrix Power Series 矩阵A^1+A^2+A^3...求和转化-白红宇

POJ-3233 Matrix Power Series 矩阵A^1+A^2+A^3...求和转化

阅读量：4601 次

发布时间：2019-06-09

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

S(k)=A^1+A^2...+A^k.

保利求解就超时了，我们考虑一下当k为偶数的情况，A^1+A^2+A^3+A^4...+A^k，取其中前一半A^1+A^2...A^k/2，后一半提取公共矩阵A^k/2后可以发现也是前一半A^1+A^2...A^k/2。因此我们可以考虑只算其中一半，然后A^k/2用矩阵快速幂处理。对于k为奇数，只要转化为k-1+A^k即可。n为矩阵数量，m为矩阵大小，复杂度O[(logn*logn)*m^3]

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #define LL long longusing namespace std;struct mx{    LL n, m;    LL c[35][35];//需要根据题目开大    void initMath(LL _n)//初始化方阵    {        m = n = _n;    }    void initOne(LL _n)//初始化单位矩阵    {        m = n = _n;        for (LL i = 0; i
            
             > t;    while (t--)    {        cin >> n >> k;        b.initMath(n);        ans.initMath(n);        a.initMath(n);        for(int i=0;i
             
              > a.c[i][j];            }        ans = s(k);        ans.print();    }    return 0;}

转载于:https://www.cnblogs.com/LukeStepByStep/p/7883057.html

你可能感兴趣的文章