111qqz的小窝

老年咸鱼冲锋!

uva 10870 – Recurrences (矩阵加速线性递推式)

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是多少。

思路:

构造矩阵,加速递推式。

趁着这道题说一下一般的构造法。

转移矩阵M(d*d)的构造方法是,最后一行倒序写a[1]..a[d], 除去第一列和最后一行外,用1填充对角线,其余的为0.

初始矩阵M1(d*1)的构造方法是从上到下,f[1]..f[d]即可。

需要注意的是

最后答案是 (M^(n-d))*M1.mat[d-1][0] (由于经常出现的是d=2的递推式,因此注意不要把此式子的d,写成不够一般化的错误的2

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz