题目链接

题意

给定$c_0,c_1,求c_n(c_0,c_1,n\lt 2^{31})$，递推公式为

\[c_i=c_{i-1}+2c_{i-2}+i^4
\]

思路

参考

将递推式改写$$\begin{pmatrix}f(n)\f(n-1)\n^4\n3\n^{2\n\1\end{pmatrix}=\begin{pmatrix}1&2&1&4&6&4&1\1&0&0&0&0&0&0\0&0&1&4&6&4&1\0&0&0&1&3&3&1\0&0&0&0&1&2&1\0&0&0&0&0&1&1\0&0&0&0&0&0&1\end{pmatrix}\begin{pmatrix}f(n-1)\f(n-2)\(n-1)}4\(n-1)^3\(n-1)2\(n-1)\1\end{pmatrix}$$

然后上矩阵快速幂。

// 一开始令$d_i=c_i-2c_{i-1}$，推出了一个$d_i=(-1)^{i-2}(d_2-15)+\frac{1}{2}i^4+i^3-\frac{1}{2}i$，虽然接下来也好做但挺烦且容易算错。一上来就应该往矩阵快速幂的方向去想的。

Code

#include <bits/stdc++.h>

#define N 7

using namespace std;

typedef long long LL;

const LL mod = 2147493647;

typedef struct {

    LL mat[N][N];

    void init(LL x){

        memset(mat, 0, sizeof(mat));

        for(int i=0; i<N; i++) mat[i][i] = x;

    }

    void print() const {

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

            for (int j = 0; j < N; ++j) printf("%lld ", mat[i][j]); printf("\n");

        }

    }

} Matrix;

Matrix p = {1,2,1,4,6,4,1,

            1,0,0,0,0,0,0,

            0,0,1,4,6,4,1,

            0,0,0,1,3,3,1,

            0,0,0,0,1,2,1,

            0,0,0,0,0,1,1,

            0,0,0,0,0,0,1

           };

LL add(LL a, LL b) { return (a + b + mod) % mod; }

LL mul(LL a, LL b) { return a * b % mod; }

Matrix mulm(const Matrix& a, const Matrix& b) {

    Matrix temp;

    temp.init(0);

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

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

            for (int k = 0; k < N; ++k) temp.mat[i][j] = add(temp.mat[i][j], mul(a.mat[i][k], b.mat[k][j]));

        }

    }

    return temp;

}

Matrix poww(LL n) {

    Matrix a = p, ret;

    ret.init(1);

    while (n) {

        if (n & 1) ret = mulm(ret, a);

        a = mulm(a, a);

        n >>= 1;

    }

    return ret;

}

void work() {

    LL n, a, b;

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

    Matrix m = poww(n-2);

    LL ans = add(add(add(add(add(add(mul(b, m.mat[0][0]), mul(a, m.mat[0][1])), mul(16, m.mat[0][2])),

                  mul(8, m.mat[0][3])), mul(4, m.mat[0][4])), mul(2, m.mat[0][5])), m.mat[0][6]);

    printf("%lld\n", ans);

}

int main() {

    int T;

    scanf("%d", &T);

    while (T--) work();

    return 0;

}

巴特西

hdu 5950 Recursive sequence 递推式矩阵快速幂

题目链接

题意

思路

参考

Code

最新文章

热门文章

巴特西

hdu 5950 Recursive sequence 递推式 矩阵快速幂

题目链接

题意

思路

参考

Code

最新文章

热门文章

hdu 5950 Recursive sequence 递推式矩阵快速幂