#1191559 (C++17) No.226 0-1パズル

• 問題: No.226 0-1パズル
• ユーザー: 小畑裕貴
• 提出日時: 2026-10-05 19:21:57
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 3 ms / 5,000 ms
• コード長: 4,001 bytes
• コンパイル時間: 663 ms
• コンパイル使用メモリ: 137,744 KB
• 実行使用メモリ: 11,264 KB
• 最終ジャッジ日時: 2026-10-05 19:22:09
• 合計ジャッジ時間: 2,160 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
other	AC * 22

ソースコード

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <ctime>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define repb(i, e) for (int i = (int)(e); i >= 0; i--)
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<long long>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvd = vector<vd>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vc = vector<char>;
using vvc = vector<vc>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, long long>;
using pli = pair<long long, int>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vpil = vector<pil>;
using vpli = vector<pli>;

const double PI = acos(-1);
const ll MOD = 1000000007;
const ll MODL = 2147483647;
const int INF = 1000000007;
const ll INFL = 1LL<<60;

template <typename T> inline bool chmin(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <typename T> inline bool chmax(T &a, T b) {if (a < b) {a = b; return true;} return false;}
// template <typename T> T gcd(T a, T b) {if (a < b) swap(a, b); if (b == 0) return a; else return gcd(b, a%b);}
template <typename T> inline T ceil(T a, T b) {return (a+(b-1))/b;}
template <typename T> inline T floor(T a, T b) {return a/b;}
template <typename T> inline void add(T &a, T b, T m) {a = ((a % m + b % m)) % m;}
template <typename T> inline void sub(T &a, T b, T m) {a = ((a % m - b % m) + m) % m;}
template <typename T> inline void mul(T &a, T b, T m) {a = (((a % m + m) % m) * ((b % m) + m) % m) % m;}
vector<long long> F(1000009, -1);


ll Power(ll a, ll b, ll m) {
    ll ans = 1, func = a;
    while (b > 0) {
        if (b % 2 == 1) {
            ans = (ans * func) % m;
        }
        func = (func * func) % m;
        b /= 2;
    }
    return ans;
}


ll Modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t*b;
        u -= t*v;
        swap(a, b);
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


ll Fact(ll a, ll m) {
    if (F[a] != -1) return F[a];
    if (a == 0) return F[a] = 1;
    return F[a] = (a * Fact(a-1, m)) % m;
}


ll Perm(ll a, ll b, ll m) {
    if (a < b || b < 0) return 0;
    ll ans = Fact(a, m);
    mul(ans, Modinv(Fact(a-b, m), m), m);
    return ans;
}


ll Comb(ll a, ll b, ll m) {
    if (a < b || b < 0) return 0;
    ll ans = Fact(a, m);
    ans = (ans*Modinv(Fact(b, m), m)) % m;
    ans = (ans*Modinv(Fact(a-b, m), m)) % m;
    return ans;
}


int main() {
    int h, w, now, v;
    ll num1 = 0, num2 = 0, ans = 0;
    bool okh = true, okw = true, ok0 = true, ok1 = true;
    cin >> h >> w;
    vs s(h);
    rep(i, h) cin >> s[i];
    rep(i, w) {
        now = -1;
        rep(j, h) {
            if (s[j][i] != '?') {
                v = (int)(s[j][i] - '0');
                if (now == -1) now = (v + j) % 2;
                else if (now != (v + j) % 2) okh = false;
            }
        }
        if (now == -1) num1++;
        else {
            if ((now + i) % 2 == 0) ok0 = false;
            else ok1 = false;
        }
    }
    rep(i, h) {
        now = -1;
        rep(j, w) {
            if (s[i][j] != '?') {
                v = (int)(s[i][j] - '0');
                if (now == -1) now = (v + j) % 2;
                else if (now != (v + j) % 2) okw = false;
            }
        }
        if (now == -1) num2++;
    }
    if (okh) add(ans, Power(2ll, num1, MOD), MOD);
    if (okw) add(ans, Power(2ll, num2, MOD), MOD);
    if (ok0) sub(ans, 1ll, MOD);
    if (ok1) sub(ans, 1ll, MOD);
    if (!okh && !okw) ans = 0;
    cout << ans << endl;
}