結果
問題 | No.226 0-1パズル |
ユーザー | qLethon |
提出日時 | 2022-09-04 15:23:11 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,908 bytes |
コンパイル時間 | 2,437 ms |
コンパイル使用メモリ | 206,112 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-29 15:50:37 |
合計ジャッジ時間 | 3,172 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | WA | - |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template <std::uint_fast64_t Modulus> class modint { using u64 = std::uint_fast64_t; u64 a; public: template <class INT> constexpr modint(const INT x = 0) noexcept : a(x >= 0 ? x % Modulus : x % int_fast64_t(Modulus) + Modulus) {} constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {} constexpr u64 &value() noexcept { return a; } constexpr const u64 &value() const noexcept { return a; } constexpr modint operator+(const modint rhs) const noexcept { return modint(*this) += rhs; } constexpr modint operator-(const modint rhs) const noexcept { return modint(*this) -= rhs; } constexpr modint operator*(const modint rhs) const noexcept { return modint(*this) *= rhs; } constexpr modint operator/(const modint rhs) const noexcept { return modint(*this) /= rhs; } constexpr modint &operator+=(const modint rhs) noexcept { a += rhs.a; if (a >= Modulus) { a -= Modulus; } return *this; } constexpr modint &operator-=(const modint rhs) noexcept { if (a < rhs.a) { a += Modulus; } a -= rhs.a; return *this; } constexpr modint &operator*=(const modint rhs) noexcept { a = a * rhs.a % Modulus; return *this; } constexpr modint &operator/=(modint rhs) noexcept { u64 exp = Modulus - 2; while (exp) { if (exp % 2) { *this *= rhs; } rhs *= rhs; exp /= 2; } return *this; } constexpr bool operator<(const modint& rhs) const noexcept {return this->a < rhs.a;} constexpr bool operator>(const modint& rhs) const noexcept {return rhs < *this;} constexpr bool operator<=(const modint& rhs) const noexcept {return !(*this > rhs);} constexpr bool operator>=(const modint& rhs) const noexcept {return !(*this < rhs);} constexpr bool operator==(const modint& rhs) const noexcept {return this->a == rhs.a;} constexpr bool operator!=(const modint& rhs) const noexcept {return !(*this == rhs);} constexpr modint& operator++() noexcept { *this += modint(1); return *this; } constexpr modint operator++(int) noexcept { modint tmp(*this); ++(*this); return tmp; } constexpr modint& operator--() noexcept { *this -= modint(1); return *this; } constexpr modint operator--(int) noexcept { modint tmp(*this); --(*this); return tmp; } constexpr modint operator-() const noexcept { return modint(0) - *this; } template <std::uint_fast64_t M> friend constexpr std::ostream& operator<<(std::ostream& os, const modint<M>& rhs) noexcept { os << rhs.a; return os; } template <std::uint_fast64_t M> friend constexpr std::istream& operator>>(std::istream& is, modint<M>& rhs) noexcept { int64_t tmp; is >> tmp; rhs = modint(tmp); return is; } constexpr modint pow(const u64 k) const noexcept { if (k == 0) return 1; if (k % 2 == 0){ modint res = pow(k / 2); return res * res; } return pow(k - 1) * modint(*this); } template <typename T> operator const T (){return a;} }; constexpr int64_t p = 1e9 + 7; using mint = modint<p>; int main(){ int h, w; cin >> h >> w; vector<string> S(h); for (auto &s: S) cin >> s; vector<mint> A(h); for (int i = 0; i < h; i++){ bool ok0 = true, ok1 = true; for (int j = 0; j < w; j++){ ok0 &= S[i][j] == '?' or S[i][j] - '0' == j % 2; ok1 &= S[i][j] == '?' or S[i][j] - '0' == (j + 1) % 2; } if (ok0) A[i]++; if (ok1) A[i]++; } mint ans = 0; { mint s = 1; for (int i = 0; i < h; i++) s *= A[i]; ans = s; } for (int i = 1; i < h; i++){ for (int j = 0; j < w; j++){ if (S[i][j] == '?') continue; char c = i % 2 == 1 ? '0' + (1 - (S[i][j] - '0')) : S[i][j]; if (S[0][j] == '?') S[0][j] = c; else if (S[0][j] != c) S[0][j] == 'x'; } } int hatena = 0; for (int j = 0; j < w; j++){ if (S[0][j] == 'x'){ cout << ans << endl; return 0; } if (S[0][j] == '?') hatena++; } ans += mint(2).pow(hatena); bool ok0 = true, ok1 = true; for (int j = 0; j < w; j++){ ok0 &= S[0][j] == '?' or S[0][j] - '0' == j % 2; ok1 &= S[0][j] == '?' or S[0][j] - '0' == (j + 1) % 2; } if (ok0) ans--; if (ok1) ans--; cout << ans << endl; }