結果

問題 No.226 0-1パズル
コンテスト
ユーザー 303Yuyu
提出日時 2021-02-13 15:55:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,667 bytes
コンパイル時間 1,640 ms
コンパイル使用メモリ 171,984 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-26 14:26:46
合計ジャッジ時間 2,420 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
//#include <atcoder/all>

using namespace std;
//using namespace atcoder;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using ld = long double;
using vld = vector<ld>;
using vb = vector<bool>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

template <class T> bool chmin(T& a, T b) {
    if(a > b) { a = b; return true; }
    else return false;
}

template <class T> bool chmax(T& a, T b) {
    if(a < b) { a = b; return true; }
    else return false;
}

template <class T> ostream& operator<<(ostream& s, const vector<T>& a) {
    for(auto i : a) s << i << ' ';
    return s;
}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

struct mint {
    static const long long mod = 1000000007;
    long long x;
    mint(long long x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint& a) {if ((x += a.x) >= mod) x -= mod; return *this;}
    mint& operator-=(const mint& a) {if ((x += mod - a.x) >= mod) x -= mod; return *this;}
    mint& operator*=(const mint& a) {(x *= a.x) %= mod; return *this;}

    friend const mint operator+(const mint& a, const mint& b) { mint ret = a; return ret += b; }
    friend const mint operator-(const mint& a, const mint& b) { mint ret = a; return ret -= b; }
    friend const mint operator*(const mint& a, const mint& b) { mint ret = a; return ret *= b; }
    friend ostream& operator<<(ostream& s, const mint& a) { return s << a.x; }

    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2);}
    mint& operator/=(const mint a) { return (*this) *= a.inv();}
    friend const mint operator/(const mint& a, const mint& b) { mint ret = a; return ret /= b; }
};

void solve() {
    ll h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    // 0101..又は1010..のパターン
    mint ans = 1;
    rep(i, h) {
        vll p(2, -1);   // 0又は1のインデックスの2の剰余
        rep(j, w) {
            char c = s[i][j];
            if(c == '?') continue;
            else if(p[c-'0'] == -1) p[c-'0'] = j%2;
            else if(p[c-'0'] != j%2) {  // 0101..のパターンはない
                ans = 0;
                break;
            }
        }
        if(p[0] == -1 && p[1] == -1) ans *= 2;
        else if(p[0] == p[1]) ans = 0;
        if(ans.x == 0) break;
    }

    // 0101..以外のパターン
    mint ans2 = 1;
    vll a(w, -1);
    rep(i, h) {
        rep(j, w) {
            char c = s[i][j];
            if(c == '?') continue;
            if(a[j] == -1) a[j] = (c-'0'+i)%2;
            else if(a[j] != (c-'0'+i)%2) {  // 0101..以外のパターンはない
                ans2 = 0;
                break;
            }
        }
        if(ans2.x == 0) break;
    }
    rep(i, w) if(a[i] == -1) ans2 *= 2;
    if(ans2.x != 0) {
        bool f = true;
        rep(i, w) if(a[i] != -1 && a[i] != i%2) f = false;  // 0101..でない
        if(f) ans2 -= 1;
        f = true;
        rep(i, w) if(a[i] != -1 && a[i] == i%2) f = false;  // 1010..でない
        if(f) ans2 -= 1;
    }

    cout << ans + ans2 << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}
0