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

想法

由題目可知，必須由甲開始，甲結束。因此，取的次數是奇數。我們可以將第一個甲獨立判斷，後面乙甲都綁定在一起。於是，可以得到。
\(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";
    }
}