HDU 5950：Recursive sequence（矩阵快速幂）

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

题意：给出 a，b，n，递推出 f(n) = f(n-1) + f(n-2) * 2 + n ^ 4. f(1) = a, f(2) = b.

思路：在比赛时候知道是矩阵快速幂，可是推不出矩阵.那个n^4不知道怎么解决。结束后问其他人才知道要构造一个7 * 7的矩阵，而不是3 * 3的..

转自：http://blog.csdn.net/spring371327/article/details/52973534

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <cmath>

 #include <queue>

 #include <vector>

 using namespace std;

 #define N 1010

 #define INF 0x3f3f3f3f

 #define MOD 2147493647

 typedef long long LL;

 struct matrix

 {

     LL a[][];

     void init() {

         memset(a, , sizeof(a));

         for(int i = ; i < ; i++) a[i][i] = ;

     }

     matrix operator * (matrix b) {

         matrix ans;

         LL tmp;

         for(int i = ; i < ; i++) {

             for(int j = ; j < ; j++) {

                 ans.a[i][j] = ;

                 for(int k = ; k < ; k++) {

                     tmp = a[i][k] * b.a[k][j] % MOD;

                     ans.a[i][j] = (ans.a[i][j] + tmp % MOD) % MOD;

                 }

             }

         }

         return ans;

     }

 };

 matrix q_pow(matrix a, LL b)

 {

     matrix ans;

     ans.init();

     while(b) {

         if(b & ) ans = ans * a;

         b >>= ;

         a = a * a;

     }

     return ans;

 }

 int main()

 {

     matrix mo;

     memset(mo.a, , sizeof(mo.a));

     mo.a[][] = ;

     mo.a[][] = ; mo.a[][] = , mo.a[][] = , mo.a[][] = , mo.a[][] = , mo.a[][] = , mo.a[][] = ;

     mo.a[][] = , mo.a[][] = , mo.a[][] = , mo.a[][] = , mo.a[][] = ;

     mo.a[][] = , mo.a[][] = , mo.a[][] = , mo.a[][] = ;

     mo.a[][] = , mo.a[][] = , mo.a[][] = ;

     mo.a[][] = , mo.a[][] = ;

     mo.a[][] = ;

     int t;

     scanf("%d", &t);

     while(t--) {

         long long n, a, b;

         scanf("%I64d%I64d%I64d", &n, &a, &b);

         if(n == ) printf("%I64d\n", a);

         else if(n == ) printf("%I64d\n", b);

         else {

             matrix ans = q_pow(mo, n - );

             LL sum = ;

             sum = (sum + ans.a[][] * a) % MOD;

             sum = (sum + ans.a[][] * b) % MOD;

             sum = (sum + ans.a[][] * ) % MOD;

             sum = (sum + ans.a[][] * ) % MOD;

             sum = (sum + ans.a[][] * ) % MOD;

             sum = (sum + ans.a[][] * ) % MOD;

             sum = (sum + ans.a[][]) % MOD;

             printf("%I64d\n", sum);

         }

     }

     return ;

 }

巴特西

HDU 5950：Recursive sequence（矩阵快速幂）

最新文章

热门文章