hdu5950

题意

\(给出 f_1 ， f_2 ，以及递推式 f_n = 2 * f_{n-2} + f_{n-1} + n^4 ，求 f_n (mod=2147493647)\)

推导一下。

\[\begin{Bmatrix}
f_n\\
f_{n-1}\\
f_{n-2}\\
(n+1)^4\\
(n+1)^3\\
(n+1)^2\\
(n+1)\\
1
\end{Bmatrix} =
\begin{Bmatrix}
1 & 2 & 0 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 4 & 6 & 4 & 1\\
0 & 0 & 0 & 0 & 1 & 3 & 3 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 2 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{Bmatrix} *
\begin{Bmatrix}
f_{n-1}\\
f_{n-2}\\
f_{n-3}\\
n^4\\
n^3\\
n^2\\
n\\
1
\end{Bmatrix}\]

矩阵快速幂即可。

code

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<iostream>

#define ll long long

using namespace std;

const ll MOD = 2147493647;

const int SIZE = 11;

ll n;

//定义结构体

struct Matrix

{

    ll mat[SIZE][SIZE];

    Matrix()

    {

        memset(mat, 0, sizeof mat);

    }

};

//矩阵乘法 重载 * 操作符

Matrix operator * (Matrix a, Matrix b)

{

    Matrix c;

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

    for(int i = 0; i < SIZE; i++)

    {

        for(int j = 0; j < SIZE; j++)

        {

            for(int k = 0; k < SIZE; k++)

                c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;

        }

    }

    return c;

}

//矩阵快速幂 重载 ^ 操作符

Matrix operator ^ (Matrix a, ll k)

{

    Matrix t;

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

    for(int i = 0; i < SIZE; i++) // 单位矩阵

        t.mat[i][i] = 1;

    while(k)

    {

        if(k & 1)

            t = t * a;

        a = a * a;

        k >>= 1;

    }

    return t;

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        Matrix mt;

        ll a, b;

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

        ll c = 2 * a + b + 81;

        c %= MOD;

        if(n == 1) printf("%lld\n", a % MOD);

        else if(n == 2) printf("%lld\n", b % MOD);

        else if(n == 3) printf("%lld\n", c % MOD);

        else

        {

            mt.mat[0][0] = 1;

            mt.mat[0][1] = 2;

            mt.mat[0][3] = 1;

            mt.mat[1][0] = 1;

            mt.mat[2][1] = 1;

            mt.mat[3][3] = 1;

            mt.mat[3][4] = 4;

            mt.mat[3][5] = 6;

            mt.mat[3][6] = 4;

            mt.mat[3][7] = 1;

            mt.mat[4][4] = 1;

            mt.mat[4][5] = 3;

            mt.mat[4][6] = 3;

            mt.mat[4][7] = 1;

            mt.mat[5][5] = 1;

            mt.mat[5][6] = 2;

            mt.mat[5][7] = 1;

            mt.mat[6][6] = 1;

            mt.mat[6][7] = 1;

            mt.mat[7][7] = 1;

            mt = mt ^ (n - 3);

            ll ans = mt.mat[0][0] * c + mt.mat[0][1] * b + mt.mat[0][2] * a + mt.mat[0][3] * 256

                    + mt.mat[0][4] * 64 + mt.mat[0][5] * 16 + mt.mat[0][6] * 4 + mt.mat[0][7];

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

        }

    }

    return 0;

}

巴特西

hdu5950

hdu5950

题意

code

最新文章

热门文章