D.Starry的神奇魔法(矩阵快速幂)

/*D: Starry的神奇魔法

Time Limit: 1 s Memory Limit: 128 MB

Submit My Status

Problem Description

啦啦啦，Starry正愉快的做着编程题，代码是多么优美呀！突然，有人问他一道数学题，对于数学渣渣的Starry来说，这是多么的烦恼呀。不过不要紧，他还可以问其他人的，所以他想到了聪明的你们。这个问题是由一个神奇的魔法师提出的，他创造了一种魔法，每次使用魔法可以让今天的魔力值为前一天魔力值的2018倍+前两天魔力值的8倍+前三天魔力值的12倍。当然，一天只能使用一次魔法，除了使用魔法外，每天魔法师还能产生8888的魔力值。第一、二、三天的初始魔力值为888。他想问的是第n天他可以拥有多少魔力值。

Input

第一行输入一个T表示有TT个问题(1≤T≤104)(1≤T≤104)。

接下来T行，每行有一个数n（1≤n≤1018）n（1≤n≤1018），表示第nn天。

Output

输出TT行，每行输出第nn天的魔力值，由于数很大，结果对2018081220180812取模。

Sample Input

3

2

5

8

Sample Output

888

17299052

16854116*/

#include<iostream>

#include<string.h>

#define ll long long

#define inf 20180812

using namespace std;

struct mat

{

    ll p[4][4];

    mat()

    {

        memset(p,0,sizeof(p));

    }

};

mat mul(mat a,mat b)

{

    mat c;

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

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

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

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

    return c;

}

mat pow(mat a,ll n)

{

    mat b;

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

        b.p[i][i]=1;

    b.p[0][0]=b.p[1][0]=b.p[2][0]=888;

    b.p[3][0]=8888;

    while(n)

    {

        if(n&1)

            b=mul(a,b);

        a=mul(a,a);

        n/=2;

    }

    return b;

}

int main()

{

    int t;

    ll aa[11111];

    int c=0;

    mat a;

    a.p[0][0]=2018;

    a.p[0][1]=8;

    a.p[0][2]=12;

    a.p[0][3]=1;

    a.p[1][0]=a.p[2][1]=a.p[3][3]=1;

    scanf("%d",&t);

    while(t--)

    {

        ll n;

        scanf("%lld",&n);

        if(n<4)

        {

            aa[c]=888;

            c++;

            continue;

        }

        mat b=pow(a,n-3);

        aa[c]=b.p[0][0]%inf;

        c++;

    }

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

        printf("%lld\n",aa[i]);

    return 0;

}

巴特西

D.Starry的神奇魔法(矩阵快速幂)

最新文章

热门文章