阿祁的部落格

ZeroJudge g556 - 白色世界 解題心得( 題目 )

解題概念:矩陣快速冪

注意:這題有個簡單版本(g555)遞迴+DP memorization即可求解，但是這題數字更大沒辦法這麼做，O(N)在時間和空間複雜度都無法承受。

解題方法:我們可以先觀察規律，發現f(n)=f(n-1)+f(n-2)+1，長得很像費氏數列，我們知道費氏數列可透過矩陣快速冪求解，而這題也可以。

首先是初始狀態，假設這個矩陣叫做A:

f(1) 

f(0) 

1

要注意的是下方程式碼把初始狀態簡化了，因為f(0)=0，所以其實最後轉移矩陣乘上他只需要管兩項。

再來是狀態的轉移矩陣，假設這個矩陣叫做B，其實B^1[0][0]、B^2[0][0]、B^3[0][0] ... 就是費氏數列。(感謝thanksone提供提示)

1 1 1

1 0 0

0 0 1

要注意的是下方程式碼把初始狀態簡化了，因為f(0)=0，所以其實最後轉移矩陣乘上他只需要管兩項。

最後求的方法就是B^(n-1)*A。

使用矩陣快速冪，可在O(logn)內得到答案。

//Author:En Chi Tsung(欉恩祁)

//Date:2022/02/08

import java.io.*;

import java.util.*;

public class zjg556 {

    public static int r;

    public static long ret;

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));    

    public static final int p=998244353;

    public static final long[][] a=new long[][] {

        {1,1,1},

        {1,0,0},

        {0,0,1}

    };

    public static void main(String[] args) throws Exception{

        final int t=(int)readLong();

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

            bw.write(DP(readLong())+"\n");

        }

        bw.flush();

    }

    

    public static int DP(long x) {

        if(x==1) {

            return 1;

        }

        else {

            long[][] mem=exp(x-1);

            return (int)((mem[0][0]+mem[0][2])%p);

        }

    }

    

    public static long[][] exp(long x) {

        if(x==1) {

            return a;

        }

        long[][] mem;

        mem=exp(x/2);

        if(x%2==0) {

            return multiply(mem,mem);

        }

        else {

            return multiply(mem,multiply(mem,a));

        }

    }

    

    public static long[][] multiply(long[][] a,long[][] b){

        long[][] cal=new long[3][3];

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

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

                cal[i][j]=(a[i][0]*b[0][j]%p+a[i][1]*b[1][j]%p+a[i][2]*b[2][j]%p)%p;

            }

        }

        return cal;

     }

    

    public static long readLong() throws Exception {

        ret=0;

        r=br.read();

        while(r>47&&r<58) {

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }

        return ret;

    }

}