题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4471

题目意思：

求f(n).

当n为特殊点nk时

解题思路：

当x不为特殊点时，直接用基本的矩阵快速幂，求出f[x],当x为特殊点时，用另外一个矩阵，左乘转移一下。

也就是按特殊点nk,将1-n分成很多区段，一个区段一个特殊点这样来回求。

两点优化：

1、因为要多次用到同一矩阵的快速幂，所以先预处理该矩阵的2K次幂，免的计算每个区间的时候，都要计算该矩阵的2K次幂。

2、矩阵相乘的时候，把K作为主要控制元，一次计算 a[i][k]*a[k][j] ,当有a[i][k]等于0时，直接跳出来。

注意：

矩阵大小的选取，位置的选放。

c1 c2 c3 ... ct    f(n-1)                  f(n)

 1  0   0   ... 0     f(n-2)                  f(n-1)

 0  1   0   ... 0     f(n-3)                  f(n-2)

 0  0   1   ... 0     ...                        ...

...   ....     ... .       ...                       ...

 0  0   0  ..1 0     f(n-t)                  f(n-t+1)

话不多说。

代码解释的很详细：