[原创]玲珑OJ 1109 Niro plays with snow [递推+预处理矩阵乘法]【数学】

2017-03-20 13:37:14 Tabris_ 阅读数：296

博客爬取于2020-06-14 22:41:10
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/64124556

题目链接:http://www.ifrog.cc/acm/problem/1109
————————————————————————————————————————————
1109 - Niro plays with snow
Time Limit：2s Memory Limit：128MByte

Submissions：50Solved：8

DESCRIPTION
Ah, it snows.

Niro picks up a snowflake. It grows every second. At every second, each of the smallest triangles splits and one of the two rotates by 180 degrees. The process is shown below. In the picture, blue represents the areas that are one layer thick, red two layers thick, yellow three layers thick, and green four layers thick.

Now let $F(n)$ be the number of smallest triangles that are one layers thick at order $n$ , and $G(n)$ be the number of smallest triangles thar are three layers thick at order $n$ . For example, $F(1) = 1, G(1) = 0, F(2) = 6, G(2) = 0, F(3) = 30, G(3) = 6, F(4) = 138, G(4) = 78.$

Given $n$ , can you tell Niro $F(n)$ and $G(n)$ modulo 1234321237?

INPUT
T+1 lines.
The first line contains one integer T, the number of test cases.
Each of the following T lines contains one integer n.

OUTPUT
T lines.
Each line contains two integers, $F(n) \mod 1234321237$ and $G(n) \mod 1234321237$ for each query.

SAMPLE INPUT
5
3
4
5
52
100

SAMPLE OUTPUT
30 6
138 78
606 654
540534048 39147304
978578590 88026038

HINT
$1≤T≤10^5$
$1≤n≤10^18$
————————————————————————————————————————————
题目大意：
就是问你第n个图形中一层和三层的三角形有多少个

解题思路：

看了看数据范围，想到是个矩阵乘法，也推出了 $8*8$ 的矩阵乘法
$ \left[\begin{array}{cc}\ 0&&6&&0&&0&&0&&0&&0&&0 \0&&3&&2&&0&&1&&0&&0&&0 \0&&1&&2&&1&&2&&0&&0&&0 \0&&0&&0&&3&&3&&0&&0&&0 \0&&0&&0&&0&&0&&6&&0&&0 \0&&0&&0&&0&&0&&3&&2&&0 \0&&0&&0&&0&&0&&1&&2&&1 \0&&0&&0&&0&&0&&0&&0&&3 \\end{array}\right]\times \left[\begin{array}{cc} F_0(i)\F_1(i)\F_2(i)\F_3(i)\G_0(i)\G_1(i)\G_2(i)\G_3(i)\ \end{array}\right] = \left[\begin{array}{cc} F_0(i+1)\F_1(i+1)\F_2(i+1)\F_3(i+1)\G_0(i+1)\G_1(i+1)\G_2(i+1)\G_3(i+1) \end{array}\right]$

-其中 $F_i()$ 表示三角形三边中有 $i$ 条变邻近红色(两层)
-其中 $G_i()$ 表示三角形三边中有 $i$ 条变邻近红色(两层)

然而交上去就TLE了,
复杂度 $O(T\times \log_2^{3}(n))$ …

然后听了Q 的说法预处理出所有的A矩阵的 $2^i$ 次幂然后在计算的时候只要用向量乘上矩阵就好了复杂度就变成了 $O(T\times \log_2^{2}(n))$ 然后就过了

然而当时听说还有用4*4的矩阵过得…
最后看了题解 ,真是玄妙无比啊…有兴趣的戳一下题解的传送阵

附本题代码
————————————————————————————————————————————

# include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

# define abs(x) ((x)>0?(x):-(x))

const int MOD =  1234321237;
const int N   =  1e5+7 ;
const int M   =  8 ;
/********************************************/

struct Matrix{
    LL m[M][M];
    void clearO(){
        for(int i=0; i<M; i++) //初始化矩阵
            for(int j=0; j<M; j++)
                m[i][j]= 0;
    }
    void clearE(){
        for(int i=0; i<M; i++) //初始化矩阵
            for(int j=0; j<M; j++)
                m[i][j]= (i==j);
    }
    void display(){
        for(int i=0; i<M; i++){
            for(int j=0; j<M; j++)
                printf("%d ",m[i][j]);
            puts("");
        }
        puts("-----");
    }
};

Matrix operator * (Matrix &a,Matrix &b){
    Matrix c;
    c.clearO();

    for(int k=0; k<M; k++)
        for(int i=0; i<M; i++){ //实现矩阵乘法
            if(a.m[i][k] <= 0)  continue;
            for(int j=0; j<M; j++){
                if(b.m[k][j] <= 0)    continue;
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
            }
        }
    return c;
}

Matrix operator ^ (Matrix &a,LL b){
    Matrix c;
    c.clearE();
    while(b){
        if(b&1) c= c * a ;
        b >>= 1;
        a = a * a ;
    }
    return c;
}

Matrix a[100];
void init(){

    a[0].m[0][1]=6;
    a[0].m[1][1]=3,a[0].m[1][2]=2,a[0].m[1][4]=1;
    a[0].m[2][1]=1,a[0].m[2][2]=2,a[0].m[2][3]=1,a[0].m[2][4]=2;
    a[0].m[3][1]=0,a[0].m[3][2]=0,a[0].m[3][3]=3,a[0].m[3][4]=3;
    a[0].m[4][5]=6;
    a[0].m[5][5]=3,a[0].m[5][6]=2;
    a[0].m[6][5]=1,a[0].m[6][6]=2,a[0].m[6][7]=1;
    a[0].m[7][5]=0,a[0].m[7][6]=0,a[0].m[7][7]=3;

    for(int i=1;(1ll<<i)<=1e18;i++)    a[i]=a[i-1]*a[i-1];
}

int main(){
    init();

    int _;
    Matrix b,c,d;
    LL n ;

    scanf("%d",&_);
    for(int i=1;i<=_;i++){
        scanf("%lld",&n);n--;

        b.clearO();
        b.m[0][0]=1;

//        b.display();

        for(int i=0;(1ll<<i)<=n;i++){
            if(n&(1ll<<i)){
                for(int j=0;j<M;j++){
                    for(int k=0;k<M;k++){
                        b.m[1][j]=(b.m[1][j]+b.m[0][k]*a[i].m[k][j]+MOD)%MOD;
                    }
                }
                for(int j=0;j<M;j++){
                    b.m[0][j]=b.m[1][j];
                    b.m[1][j]=0;
                }
            }
        }

        printf("%lld " ,((b.m[0][0]+b.m[0][1])%MOD+(b.m[0][2]+b.m[0][3])%MOD)%MOD);
        printf("%lld\n",((b.m[0][4]+b.m[0][5])%MOD+(b.m[0][6]+b.m[0][7])%MOD)%MOD);
    }


    return 0;
}