[題解]動態規劃-圍棋遊戲

作者:

內容目錄

想法

由題目可知，必須由甲開始，甲結束。因此，取的次數是奇數。我們可以將第一個甲獨立判斷，後面乙甲都綁定在一起。於是，可以得到。
dp_n = dp_{n-2} + 2 \times dp_{n-3} + dp_{n-4}

其中， dp_{n-2} 是最後乙甲都取 1 個棋子； dp_{n-3} 是最後乙甲其中一個取 1 個棋子， dp_{n-4} 是最後乙甲都取 2 個棋子的方法數。

由於這是一個線性遞迴的轉移式，因此我們可以用矩陣乘法進一步優化。
\begin{pmatrix}dp_{n} \\ dp_{n-1} \\ dp_{n-2} \\ dp_{n-3} \end{pmatrix} = \begin{pmatrix} 0 & 1 & 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} \times \begin{pmatrix}dp_{n-1} \\ dp_{n-2} \\ dp_{n-3} \\ dp_{n-4} \end{pmatrix}

最後， dp_0=0, \; dp_1 = dp_2 = dp_3 =1 ，因此，可以整理如下。
\begin{pmatrix}dp_{n} \\ dp_{n-1} \\ dp_{n-2} \\ dp_{n-3} \end{pmatrix} = \begin{pmatrix} 0 & 1 & 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} ^ {n-3} \times \begin{pmatrix}\;1\; \\ 1 \\ 1 \\ 0 \end{pmatrix}

用快速冪的技巧將複雜度優化至 O(4^3 \times \log_{2}{n})

實作

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using vll=vector<ll>;
using Mer=vector<vll>;

const ll MOD=1e9+7;

Mer operator*(Mer a,Mer b){
    Mer ret(a.size(),vll(b[0].size()));
    for(int i=0;i<a.size();++i){
        for(int j=0;j<b[0].size();++j){
            for(int k=0;k<a.size();++k){
                ret[i][j]=(ret[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    return ret;
}

Mer POW(Mer a,ll x){
    Mer ret(a.size(),vll(a[0].size(),0));
    for(int i=0;i<a.size();++i) ret[i][i]=1;
    while(x>0){
        if(x&1) ret=ret*a;
        a=a*a;
        x>>=1;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    ll n;
    cin>>n;

    if(n<=3){
        cout<<1<<"\n";
    }else{
        Mer t=Mer({
            {0,1,2,1},
            {1,0,0,0},
            {0,1,0,0},
            {0,0,1,0}
        });

        t=POW(t,n-3);

        Mer ans=Mer({{1},{1},{1},{0}});

        ans=t*ans;

        cout<<ans[0][0]<<"\n";
    }
}

發佈留言