結果

問題 No.2837 Flip Triomino
ユーザー InTheBloom
提出日時 2024-08-09 23:14:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,676 bytes
コンパイル時間 1,711 ms
コンパイル使用メモリ 112,756 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-08-09 23:14:45
合計ジャッジ時間 3,004 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <atcoder/modint>
#include <queue>

using namespace std;
using ll = long long;


int main () {
    int N, M; cin >> N >> M;

    // 横棒と縦棒を駆使して左上3x3で作れるか？という問題に帰着できそう。
    // 最終的に左上3x3のスペースにおいて2^9通りの場面から白一色にたどり着けるかを見てみよう。

    vector<string> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];

    const ll MOD = 998244353;
    using mint = atcoder::static_modint<MOD>;

    vector<vector<mint>> black(N, vector<mint>(M));
    mint all = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char c = S[i][j];
            if (c == 'B') {
                black[i][j] = 1;
            }
            if (c == '?') {
                black[i][j] = mint(1) / 2;
                all *= 2;
            }
        }
    }

    // 右側から左端3列まで縮める
    for (int j = M - 1; 3 <= j; j--) {
        for (int i = 0; i < N; i++) {
            // p := 最右がひっくり返される確率
            mint p = black[i][j];

            for (int k = 0; k < 2; k++) {
                black[i][j - k] = p * (1 - black[i][j - k]) + (1 - p) * black[i][j - k];
            }
        }
    }

    // 下側から上3列まで縮める
    for (int i = N - 1; 3 <= i; i--) {
        for (int j = 0; j < 3; j++) {
            mint p = black[i][j];

            for (int k = 0; k < 2; k++) {
                black[i - k][j] = p * (1 - black[i - k][j]) + (1 - p) * black[i - k][j];
            }
        }
    }

    // 3x3の白から到達可能な盤面を前計算する。
    vector<bool> vis(1 << 9);
    queue<int> q;

    q.push(0);
    vis[0] = true;

    while (!q.empty()) {
        auto pos = q.front(); q.pop();

        // 縦棒
        for (int i = 0; i < 3; i++) {
            int bar = (1 << i) | (1 << (i + 3)) | (1 << (i + 6));
            if (!vis[pos ^ bar]) {
                vis[pos ^ bar] = true;
                q.push(pos ^ bar);
            }
        }

        // 横棒
        for (int i = 0; i < 3; i++) {
            int bar = (1 << (3 * i)) | (1 << (3 * i + 1)) | (1 << (3 * i + 2));
            if (!vis[pos ^ bar]) {
                vis[pos ^ bar] = true;
                q.push(pos ^ bar);
            }
        }

        // 斜め(右下)
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                int upl = 3 * i + j;
                int piece = (1 << upl) | (1 << (upl + 3)) | (1 << (upl + 3 + 1));
                if (!vis[pos ^ piece]) {
                    vis[pos ^ piece] = true;
                    q.push(pos ^ piece);
                }
            }
        }

        // 斜め(左上)
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                int upl = 3 * i + j;
                int piece = (1 << upl) | (1 << (upl + 1)) | (1 << (upl + 3 + 1));
                if (!vis[pos ^ piece]) {
                    vis[pos ^ piece] = true;
                    q.push(pos ^ piece);
                }
            }
        }
    }

    mint ans = 0;
    for (int field = 0; field < (1 << 9); field++) {
        if (!vis[field]) continue;

        mint p = 1;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int ord = 3 * i + j;
                mint q = black[i][j];
                if ((field & (1 << ord)) == 0) {
                    q = 1 - q;
                }
                p *= q;
            }
        }

        ans += p * all;
    }

    cout << ans.val() << "\n";
}
0