3 x N グリッドのパスの数 [yukicoder No.569]

https://yukicoder.me/problems/no/569

解説放送

未定

前提知識

• 行列累乗によるDP高速化

解説

https://yukicoder.me/problems/no/569

この問題と全く同じようにして解く
細かい部分は上の記事に任せるとして、状態と遷移だけここでは書いておく。
状態と遷移を上の記事のようにして行列化して答える。

状態（太字が左上と繋がっている所で、繋がっているのは連結していることを示す）

遷移

0 -> 0,1,2,3,4,5,6,7
1 -> 0,1,2,3,6,7
2 -> 0,1,2,3,8,9
3 -> 0,1,2,3,4,8,9,10,11
4 -> 2,3,4,5
5 -> 2,3,4,5,6
6 -> 3,5,6,7
7 -> 3,6,7
8 -> 0,8,9
9 -> 0,8,9,10
10 -> 0,1,9,10,11
11 -> 0,1,10,11

これで、初期状態はv[0]=1, v[other]=0として、
最終的な答えはv[0]～v[7]の総和

string M[12] = {
    "111100001111",
    "111100000011",
    "111111000000",
    "111111110000",
    "100011000000",
    "100011100000",
    "110001110000",
    "110000110000",
    "001100001100",
    "001100001110",
    "000100000111",
    "000100000011"
};

string Vinit = "100000000000";

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    while (cin >> N) {
        Mat m(12, Vec(12, 0));
        rep(y, 0, 12) rep(x, 0, 12) m[y][x] = M[y][x] - '0';
        Vec v(12, 0);
        rep(x, 0, 12) v[x] = Vinit[x] - '0';

        m = fastpow(m, N);
        v = mulMatVec(m, v);
        int ans = 0;
        rep(i, 0, 8) ans = (ans + v[i]) % mod;
        
        cout << ans << endl;
    }
}