转自：http://blog.csdn.net/u012061345/article/details/52224623

简单的例子

Fibonacci数列

考虑 Fibonacci 数列，

F (n) = F (n - 1) + F (n - 2)

将右边两项看做是一个列向量的形式，令

X n - 1 = {F n - 1 F n - 2}

很容易得到

Xn 的形式，即

X n = {F n F n - 1}

现在的任务就是找到一个系数矩阵

A ，使得

AXn−1=Xn ，且

A 需与

n 无关。
如果能够找到这个

A ，则易知

An−1X1=Xn ，于是可以利用矩阵快速幂计算出

Xn 。这样就可以在

O(logn) 的时间内计算出指定的

Fibonacci 数。
这个矩阵很容易找，观察易得

A = {1110} (1)

Fibonacci数列变种

推广一下，如果令 Fn=aFn−1+bFn−2 ，则系数矩阵为

A = {a 1 b 0} (2)

利用二项式展开构造矩阵

计算k次方和

Fibonacci 数列只是最简单的例子，对于稍微复杂一点的例子，二项式展开是常用的一项技术。
考虑计算：

S n = \sum i = 1 n i k

易得

S n = n k + S n - 1

如果仿照

Fibonacci 数列，令

X n - 1 = {n k S n - 1}

则

X n = {(n + 1) k S n}

此时，可求出

A = ⎧ ⎩ ⎨ ⎪ ⎪ (n + 1 n) k 1 01 ⎫ ⎭ ⎬ ⎪ ⎪

这个系数矩阵很明显是不能用的，因为它与

n 有关，无法将递推公式转化为矩阵的幂运算。
这里需要使用二项式展开。

S n = (n - 1 + 1) k + S n - 1 = C 0 k (n - 1) k + C 1 k (n - 1) k - 1 + \dots + C k k + S n - 1

此时，如果令

X n - 1 = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ (n - 1) k (n - 1) k - 1 ⋮ (n - 1) 0 S n - 1 ⎫ ⎭ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪

则有

X n = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ n k n k - 1 ⋮ n 0 S n ⎫ ⎭ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪

现在的任务与刚才一样，找到一个系数矩阵

A ，使得

AXn−1=Xn ，且

A 需与

n 无关。
有关

Sn 的递推公式实际上就指明了

A 的最后一行。而利用二项式展开很容易得到其他行。
有

A = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ C 0 k 0 ⋮ 0 C 0 k C 1 k C 0 k - 1 ⋮ \dots C 1 k \dots \dots ⋱ \dots \dots C k k C k - 1 k - 1 ⋮ C 00 C k k 00 ⋮ 01 ⎫ ⎭ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ (3)

最后有

A n - 1 X 1 = X n

且

X 1 = {11 \dots 1} T

利用该系数矩阵可以在

O(k3logn) 时间内计算出

k 次方的和。

更一般的例子

再考虑一个一般情况：

S n = \sum i = 1 n (a i + b) k

与刚才几乎一模一样，有

S n = [a (n - 1) + (a + b)] k + S n - 1 = C 0 k a k (n - 1) k + C 1 k a k - 1 (a + b) (n - 1) k - 1 + \dots + C k k (a + b) k + S n - 1

剩下的步骤，也几乎完全与之前的一样，令

X n - 1 = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ (n - 1) k (n - 1) k - 1 ⋮ (n - 1) 0 S n - 1 ⎫ ⎭ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪

则

X n = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ n k n k - 1 ⋮ n 0 S n ⎫ ⎭ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪

同样，有关

Sn 的递推公式实际上就指明了

A 的最后一行，其他行则利用二项式展开得到。
有

A = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ C 0 k 0 ⋮ 0 C 0 k a k C 1 k C 0 k - 1 ⋮ \dots C 1 k a k - 1 (a + b) \dots \dots ⋱ \dots \dots C k k C k - 1 k - 1 ⋮ C 00 C k k (a + b) k 00 ⋮ 01 ⎫ ⎭ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ (4)

更复杂的例子

假设要计算如下和式：

S n = \sum i = 1 n i k k i

同样，将其写成递推公式，有

S n = n k k n + S n - 1 = (n - 1 + 1) k k (n - 1) + 1 + S n - 1 = C 0 k (n - 1) k k (n - 1) + 1 + C 1 k (n - 1) k - 1 k (n - 1) + 1 + \dots + C k k k (n - 1) + 1 + S n - 1

将与

n 有关的项抽出来作为列向量，令

X n - 1 = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ (n - 1) k k (n - 1) + 1 (n - 1) k - 1 k (n - 1) + 1 ⋮ (n - 1) 0 k (n - 1) + 1 S n - 1 ⎫ ⎭ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪

则

X n = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ n k k n + 1 n k - 1 k n + 1 ⋮ n 0 k n + 1 S n ⎫ ⎭ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪

同样，有关 Sn 的递推公式说明了系数矩阵 A 的最后一行。而其他行仍然可以由二项式展开得到，只是相差了一个系数 k 而已，这很容易解决。
最后，有

A = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ k C 0 k 0 ⋮ 0 C 0 k k C 1 k k C 0 k - 1 ⋮ \dots C 1 k \dots \dots ⋱ \dots \dots k C k k k C k - 1 k - 1 ⋮ k C 00 C k k 00 ⋮ 01 ⎫ ⎭ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ (5)

部分题目

POJ3070利用了矩阵1，hdu3369利用了矩阵3和4，hdu3483利用了矩阵5。

秒客网

根据递推公式构造系数矩阵用于快速幂