题目链接 题意： 给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,然后二项式展开即可 i^4=(i-1)^4 + 4*(i-1)^3 + 6(i-1)^2 + 4(i-1) + 1 所以为了维护i^4这一项，需要(i-1)^4,(i-1)^3,(i-1)^2,(i-1),1, 再加上f[i-1]和f[i-2]两项，一共7项。 然后构造矩阵为 16沈阳 onsite的题，当时好像写了一个小时，现在看来，果然是个人尽皆知的傻逼题orz /* …

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的递推式，因 …

题目链接 题意： 给出了一段程序，程序实际算的是f[n] = (f[n-1] + n%2)%m的值，其中f[1]=1,给出n,m(1E9)，问f[n] 思路： 显然是矩阵快速幂，终点在于构造矩阵。 通过经验可得（这次真的是经验了。。。其实也挺容易的，要点大概在于先把需要的项列在一起，然后增加0或者多个，为了转移需要的辅助项。 根据当前列和下一列，手动构造转移矩阵） 转移矩阵M为 [2, 1,0] [0,-1,1] [0,0 ,1] 4A..都是一个原因。。矩阵乘法那里。。。就算你%了m..也是两个1E9在相乘。。。然后就炸了23333,改成LL即可。 /* …

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] 现在问a[n][m] 在% 1E7+7 下的值是多少 （n<=10,m<=1E9） 思路： 显然矩阵快速幂，但是不会构造矩阵，放弃。 看了很多题解...发现都是“显然”构造出矩阵。。。似乎是直接凑出来的。。。 可能需要积累一点经验。 对于这道题，我们观察到n很小 所以一个直觉就是从n-1列推到第n列，推到n+1列这样地推。 初始第一列的信息是（假设n为3） [a1] [a2] …

题意：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)) 此处要用到指数循环节的知识： 111qqz_指数循环节学习笔记 a^n ≡ a^(n % Phi(M) + Phi(M)) (mod M) (n >= Phi(M)) 然后 因为1000000007是质数，对于任意的x,有gcd(x,1000000007) = 1，所以可以结合费马小定理化简上式： a^n ≡ …