LightOJ 1096 - nth Term 矩阵快速幂

http://www.lightoj.com/volume_showproblem.php?problem=1096

题意：\(f(n) = a * f(n-1) + b * f(n-3) + c, if(n > 2) f(n)= 0, if(n ≤ 2) \)

思路：给出了递推式，构造下4X4矩阵就好。

/** @Date    : 2016-12-19-18.55

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version :

  */

#include<bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

const LL mod = 1e4 + 7;

struct matrix

{

    LL mt[4][4];

    void init()

    {

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

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

                mt[i][j] = 0;

    }

    void cig()

    {

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

            mt[i][i] = 1;

    }

};

matrix mul(matrix a, matrix b)

{

    matrix c;

    c.init();

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

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

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

            {

                c.mt[i][j] += a.mt[i][k] * b.mt[k][j];

                c.mt[i][j] %= mod;

            }

    return c;

}

matrix fpow(matrix a, LL n)

{

    matrix r;

    r.init();

    r.cig();

    while(n > 0)

    {

        if(n & 1)

            r = mul(r, a);

        a = mul(a, a);

        n >>= 1;

    }

    return r;

}

LL fun(LL a, LL b, LL c, LL n)

{

    if(n < 3)

    {

        return 0;

    }

    matrix base;

    base.init();

    base.mt[0][0] = a;

    base.mt[0][2] = b;

    base.mt[0][3] = c;

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

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

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

    base = fpow(base, n - 3);

    LL ans = (base.mt[0][0] * c + base.mt[0][3]) % mod;

    return ans;

}

int main()

{

    int T;

    cin >> T;

    int cnt = 0;

    while(T--)

    {

        LL n, a, b, c;

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

        LL ans = fun(a, b, c, n);

        printf("Case %d: %lld\n", ++cnt, ans);

    }

    return 0;

}

巴特西

LightOJ 1096 - nth Term 矩阵快速幂

最新文章

热门文章