题目链接

题意：

给f[1],f[2],n,f[i] = 2*f[i-2] + f[i-1] + i^4,求f[n]的值。

思路：

很容易想到矩阵，但是i^4不是线性的差评，我们可以拆一下

i^4=(i-1+1)^4,然后二项式展开即可

uva10870题目链接

题意：

f(n) = a1f(n − 1) + a2f(n − 2) + a3f(n − 3) + . . . + adf(n − d), for n > d

给出f[1]..f[d],a[1]..a[d],问 f[n]%m是多少。

思路：

构造矩阵，加速递推式。

题目链接

题意：

给出了一段程序，程序实际算的是f[n] = (f[n-1] + n%2)%m的值，其中f[1]=1,给出n,m(1E9)，问f[n]

思路：

显然是矩阵快速幂，终点在于构造矩阵。

hdu5015题目链接

题意：

给出矩阵的构造规则： a[0][j] (j>=1) 分别为233,2333,23333….给出a[i][0] (i>=1)，对于其余的i,j,a[i][j]=a[i-1][j] + a[i][j-1]

题意：M斐波那契数列F[n]是一种整数数列，它的定义如下：

F[0] = a F[1] = b F[n] = F[n-1] * F[n-2] ( n > 1 )

现在给出a, b, n，你能求出F[n]的值吗？

思路：观察发现。。。F[n] = a^(fib(n-1)) * b ^ (fib(n))