HDU 1588 Gauss Fibonacci（矩阵快速幂+二分等比序列求和）

ACM

题目地址：HDU 1588 Gauss Fibonacci

题意：
g(i)=k*i+b;i为变量。
给出k,b,n,M，问( f(g(0)) + f(g(1)) + ... + f(g(n)) ) % M的值。

分析：
把斐波那契的矩阵带进去，会发现这个是个等比序列。
推倒：

  

   
S(g(i))
   
= F(b) + F(b+k) + F(b+2k) + .... + F(b+nk)
   
// 设 A = {1,1,0,1}, （花括号表示矩阵...）
   
// 也就是fib数的变化矩阵，F(x) = (A^x) * {1,0}
   
= F(b) + (A^k)F(b) + (A^2k)F(b)+….+(A^nk)F(b)
   
// 提取公因式 F(b)
   
= F(b) [ E +A^k + A^2k + ….+ A^nk] // (E表示的是单位矩阵)
   

   
// 令 K = A^k 后
   
E +A^k + A^2k + ….+ A^nk 变成 K^0+K^1+K^2+…+K^n
  

然后等比数列是可以二分求和的：数论_等比数列二分求和

代码：

/*
*  Author:      illuz 
  
   
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        1588.cpp
*  Create Date: 2014-08-04 16:13:51
*  Descripton:  Matrix
*/

#include 
   
     #include 
    
      #include 
     
       #include