結果
問題 | No.226 0-1パズル |
ユーザー |
|
提出日時 | 2023-10-15 10:32:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,774 bytes |
コンパイル時間 | 786 ms |
コンパイル使用メモリ | 73,040 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-16 21:57:54 |
合計ジャッジ時間 | 1,476 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
// No.226 0-1パズル#include <iostream>#include <vector>#include <string>using namespace std;const int MOD = 1'000'000'007;typedef long long ll;int power_mod(ll a, ll b, int mod = MOD) {ll ret = 1;while (b) {if (b & 1) {ret *= a;ret %= mod;}a *= a;a %= mod;b = b >> 1;}return ret;}int count_mod(const vector<string> &S, int mod = MOD) {int m = 0;for (int j = 0; j < (int)S[0].size(); ++j) {char cand = '?';for (int i = 0; i < (int)S.size(); ++i) {if (S[i][j] == '?') continue;char should = (S[i][j] - '0') ^ (i % 2) + '0';if (cand != '?' && cand != should) {return 0;}cand = should;}if (cand == '?') ++m;}return power_mod(2, m);}int count2(const vector<string> &S) {int ret[2] = { 1, 1 };for (int i = 0; i < (int)S.size(); ++i) {for (int j = 0; j < (int)S[0].size(); ++j) {for (int val = 0; val < 2; ++val) {if (S[i][j] == '0' && (i + j + val) % 2 == 1) {ret[val] = 0;}if (S[i][j] == '1' && (i + j + val) % 2 == 0) {ret[val] = 0;}}}}return ret[0] + ret[1];}int main() {int H, W;cin >> H >> W;vector<string>S(H);for (int i = 0; i < H; ++i) cin >> S[i];ll res = count_mod(S);vector<string> S_t(W, string(H, '?'));for (int i = 0; i < W; ++i) {for (int j = 0; j < H; ++j) {S_t[i][j] = S[j][i];}}res += count_mod(S_t);res -= count2(S);cout << res % MOD << endl;}