はまやんはまやんはまやん

hamayanhamayan's blog

3 x N グリッド上のサイクルの個数 [yukicoder No.541]

競技プログラミング

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

解説放送

https://youtu.be/WZgCsIMo1nI?t=963

前提知識

解法

https://yukicoder.me/submissions/185696
　
公式解説の補足として説明していきます
　
0番目を初期状態、9番目を受理状態とする。
dp[i][j] := i列目までで連結状態がjである組合せ
を更新することを考える。
例えば、2番目の状態(2,3)を考えると、これは状態0,状態1,状態2,状態3,状態5から遷移可能であるため、漸化式として書くと、
dp[i + 1][2] = dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3] + dp[i][5]
となる。
これを全ての状態について考えて、行列におこすと以下のソースコードのようになる。
あとは、これを使って、N回dpを更新するが、愚直にやると間に合わないので、行列累乗によるDP高速化を行って、高速に目的の番目までdpを回すと答え。

（行列を文字で表して、取り込むのはkmjpさんのコードを見て参考にしました。
さすがです。）

string M[10] = {
    "1000000000", // 0. 初期状態(どこもつながってない)
    "1111110000", // 1. (1,2)
    "1111010000", // 2. (1,3)
    "1111011000", // 3. (1,4)
    "1100110010", // 4. (2,3)
    "1111111100", // 5. (2,4)
    "1001011010", // 6. (3,4)
    "1000101100", // 7. (1,2)(3,4)
    "0000010010", // 8. (1,4)(2,3)
    "0111111011"  // 9. 受理状態(単純閉路ができてる)
};

string Vinit = "1000000000";

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

        m = fastpow(m, N + 1);
        v = mulMatVec(m, v);
        cout << v[9] << endl;
    }
}