HDU5950 矩阵快速幂（巧妙的递推）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5950
题意：f[n] = 2*f[n-2] + f[n-1] + n^4
思路：对于递推题而言，如果递推n次很大，则考虑矩阵快速幂的方式推出递推式，计算出累乘的矩阵
本题递推式：本题的递推式子虽然已经给出，但是由于n^4的关系，直接是无法使用这个f[n] = 2*f[n-2] + f[n-1] + n^4递推完成矩阵的推导的，而是可以先处理一下，如下：
f[n] = 2*f[n-2] + f[n-1] + n^4
f[n+1] = 2*f[n-1] + f[n] + n^4 + 4*n^3 + 6*n^2 + 4*n + 1
f[n+2] = 2*f[n] + f[n+1] + (n+1)^4 + 4*(n+1)^3 + 6*(n+1)^2 + 4*(n+1)+ 1
此时，我们发现从n+1项开始包括n+1项，都是由7个部分组成的多项式，则我们可以利用n+1项和n+2项的多项式进行矩阵快速幂的递推矩阵的推导，由于矩阵乘法的性质，对于一个1X7的矩阵A，要求相乘另一个矩阵B之后，还是一个1X7的矩阵，则矩阵B的规模必须是7X7，下面是推导， 对于黄色的一行乘绿色一列，得到橙色的一个数
完成矩阵的递推之后，就很简单了，用矩阵的快速幂计算即可，需要注意的是对于n>=3，我们才需要进行矩阵相乘的运算，而初始的时候，我们需要计算出黄色矩阵代表的部分，本题就是将n==2代入，算出初始换色矩阵为[a, b, 16, 8, 4, 2, 1]
代码：
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 5 const long long mod = 2147493647; 6 struct mat{ 7 long long m[7][7]; 8 }; 9 10 mat operator * (mat a, mat b){ //重载乘号，同时将数据mod10000 11 mat ret; 12 for(int i = 0; i < 7; i++){ 13 for(int j = 0; j < 7; j++){ 14 long long temp = 0; 15 for(int k = 0; k < 7; k++){ 16 temp += a.m[i][k] * b.m[k][j]; 17 temp %= mod; 18 } 19 ret.m[i][j] = temp; 20 } 21 } 22 return ret; 23 } 24 25 mat pow_mat(int f1, int f2, mat a, int n){ //矩阵快速幂和快速幂相同（广义快速幂的思想） 26 mat res; 27 res.m[0][0] = f1,res.m[0][1] = f2,res.m[0][2] = 16,res.m[0][3] = 8,res.m[0][4] = 4,res.m[0][5] = 2,res.m[0][6] = 1; 28 while(n){ 29 if(n&1) res = res * a; 30 a = a*a; 31 n >>= 1; 32 } 33 return res; 34 } 35 36 int main(){ 37 int t; 38 scanf("%d", &t); 39 while(t--){ 40 int n, a, b; 41 scanf("%d%d%d", &n, &a, &b); 42 if(n == 1) printf("%d\n", a); 43 else if(n == 2) printf("%d\n", b); 44 else{ 45 mat x; 46 x.m[0][0] = 0,x.m[0][1] = 2,x.m[0][2] = 0,x.m[0][3] = 0,x.m[0][4] = 0,x.m[0][5] = 0,x.m[0][6] = 0; 47 x.m[1][0] = 1,x.m[1][1] = 1,x.m[1][2] = 0,x.m[1][3] = 0,x.m[1][4] = 0,x.m[1][5] = 0,x.m[1][6] = 0; 48 x.m[2][0] = 0,x.m[2][1] = 1,x.m[2][2] = 1,x.m[2][3] = 0,x.m[2][4] = 0,x.m[2][5] = 0,x.m[2][6] = 0; 49 x.m[3][0] = 0,x.m[3][1] = 4,x.m[3][2] = 4,x.m[3][3] = 1,x.m[3][4] = 0,x.m[3][5] = 0,x.m[3][6] = 0; 50 x.m[4][0] = 0,x.m[4][1] = 6,x.m[4][2] = 6,x.m[4][3] = 3,x.m[4][4] = 1,x.m[4][5] = 0,x.m[4][6] = 0; 51 x.m[5][0] = 0,x.m[5][1] = 4,x.m[5][2] = 4,x.m[5][3] = 3,x.m[5][4] = 2,x.m[5][5] = 1,x.m[5][6] = 0; 52 x.m[6][0] = 0,x.m[6][1] = 1,x.m[6][2] = 1,x.m[6][3] = 1,x.m[6][4] = 1,x.m[6][5] = 1,x.m[6][6] = 1; 53 mat ans = pow_mat(a, b, x, n-2); 54 printf("%d\n", ans.m[0][1]); 55 } 56 } 57 return 0; 58 }
版权声明：本文为findview原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。