POJ 3233 Matrix Power Series - c++编程基础

TOP

POJ 3233 Matrix Power Series

2015-07-20 17:43:14 来源: 作者: 【大中小】浏览:1次

Tags：POJ 3233 Matrix Power Series

矩阵快速幂+二分求前n项和

矩阵快速幂是有模板的，多做几道题就会理解，前提是要会快速幂取模；

之所以用二分是因为求和的过程：A^1+A^2...+A^（k-1）+A^k， k是1e9的，所以暴力求和肯定会TLE，在网上找到

了二分求矩阵和的方法；

公式为（1+A^(k/2)）*(A+A^2+..+A^k/2) 的，所以可以写成二分递归，如果k为奇数的话，sum就加上A^k（k为当

前的k值，不再是最初的值），反正是个公式，你要不信的话可以证明一下，所以就贴代码了，感觉到姿势不够优美

呀。

#include 
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #define maxn 50 #define ll long long using namespace std; int n,k,m; struct Matrix { ll v[maxn][maxn]; } matrix; Matrix Mul(Matrix u,Matrix uu) { Matrix c; memset(c.v,0,sizeof(c.v)); for(int i=0; i
           
            >1)); pp=Mul(pp,sum(ff,dd>>1)); if(dd&1) pp=pl(pp,tul(ff,dd)); return pp; } int main() { scanf("%d%d%d",&m,&n,&k); for(int i=0; i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Leetcode dfs&dp Triangle	下一篇：ZOJ 3812 We Need Medicine 01背..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: