提出 #73347455

---

ソースコード 拡げる

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
// #include<sys/time.h>
// #include<atcoder/segtree>
// #include<atcoder/modint>

using namespace std;

// using mint = atcoder::modint998244353;

using P = pair<int, int>;
const int M = 998244353;
const long long LM = 1LL << 60;


const int W = 10;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    for (int _ = 0; _ < T; ++_) {
        int n, m;
        string x, y, z;
        cin >> n >> m >> x >> y >> z;
        reverse(x.begin(), x.end());
        reverse(y.begin(), y.end());
        reverse(z.begin(), z.end());
        vector<bitset<W * 2 + 1>> dp(n + 1);
        dp[0][W] = true;
        bool found_zero = false;
        for (int k = 0; k < n; ++k) {
            vector<bitset<W * 2 + 1>> nex(n + 1);
            for (int i = 0; i < n + 1; ++i) {
                for (int j = -W; j <= W; ++j) {
                    if (!dp[i][W + j]) {
                        continue;
                    }
                    for (int p = 0; p < 2; ++p) {
                        if (x[k] == '0' + (p ^ 1)) {
                            continue;
                        }
                        for (int q = 0; q < 2; ++q) {
                            if (y[k] == '0' + (q ^ 1)) {
                                continue;
                            }
                            if (p == 1 && q == 0) {
                                found_zero = true;
                                continue;
                            }
                            for (int r = 0; r < 2; ++r) {
                                if (z[k] == '0' + (r ^ 1)) {
                                    continue;
                                }
                                int ni = i + (p < q ? 1 : 0);
                                int nj = j + r - p * 2 - q;
                                if (nj % 2 != 0 && p == q) {
                                    found_zero = true;
                                    continue;
                                }
                                if (nj >= 0) {
                                    nj /= 2;
                                }
                                else {
                                    nj = (nj - 1) / 2;
                                }
                                if (-W <= nj && nj <= W) {
                                    nex[ni][W + nj] = true;
                                }
                                else {
                                    found_zero = true;
                                }
                            }
                        }
                    }

                }
            }
            swap(dp, nex);
            // cerr << k << '\n';
            // for (int i = 0; i < n; ++i) {
            //     for (int j = 0; j < W * 2 + 1; ++j) {
            //         cerr << dp[i][j];
            //     }
            //     cerr << '\n';
            // }
            // cerr << '\n';
        }
        for (int i = 0; i < n + 1; ++i) {
            for (int j = 0; j < W * 2 + 1; ++j) {
                if (j != W && dp[i][j]) {
                    found_zero = true;
                }
            }
        }
        string ans(m, '0');
        if (found_zero) {
            ans[0] = '1';
        }
        for (int i = 0, p = 1 % m; i < n + 1; ++i, p = p * 3 % m) {
            if (dp[i][W]) {
                ans[p] = '1';
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

提出情報

ジャッジ結果