結果
| 問題 |
No.226 0-1パズル
|
| コンテスト | |
| ユーザー |
 naribow
|
| 提出日時 | 2020-08-23 21:31:18 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 5,000 ms |
| コード長 | 6,409 bytes |
| コンパイル時間 | 1,684 ms |
| コンパイル使用メモリ | 175,608 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-07-26 14:26:13 |
| 合計ジャッジ時間 | 2,451 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
typedef unsigned long long ull;
typedef long double ldouble;
const ll INF=1e18;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <int mod>
struct ModInt {
int val;
ModInt() : val(0) {}
ModInt(long long x) : val(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
int getmod() { return mod; }
ModInt &operator+=(const ModInt &p) {
if ((val += p.val) >= mod) {
val -= mod;
}
return *this;
}
ModInt &operator-=(const ModInt &p) {
if ((val += mod - p.val) >= mod) {
val -= mod;
}
return *this;
}
ModInt &operator*=(const ModInt &p) {
val = (int)(1LL * val * p.val % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-val); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return val == p.val; }
bool operator!=(const ModInt &p) const { return val != p.val; }
ModInt inverse() const {
int a = val, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(long long n) const {
ModInt ret(1), mul(val);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.val; }
friend istream &operator>>(istream &is, ModInt &a) {
long long t;
is >> t;
a = ModInt<mod>(t);
return (is);
}
static int get_mod() { return mod; }
};
const int MOD = 1000000007; // if inv is needed, this shold be prime.
using modint = ModInt<MOD>;
int main(){
int h, w;
cin >> h >> w;
vector<vector<char> > s(w, vector<char>(h));
vector<char> first(w, '?');
bool check = true;
modint mutual = 1;
rep(y, h){
int mutual_y = 2;
int f_mutual_y = 0;
rep(x, w){
cin >> s.at(x).at(y);
// 交互でない場合のための準備
if(y % 2 == 0 && s.at(x).at(y) != '?'){
if(first.at(x) != s.at(x).at(y) && first.at(x) != '?') {check = false;}
else first.at(x) = s.at(x).at(y);
}
else if(y % 2 == 1 && s.at(x).at(y) != '?'){
if(first.at(x) - '0' != !(s.at(x).at(y) - '0') && first.at(x) != '?') {check = false;}
else first.at(x) = !(s.at(x).at(y) - '0') + '0';
}
// 交互の場合のための準備
if(s.at(x).at(y) != '?' && mutual_y == 2 && x % 2 == 0){
mutual_y = 1;
f_mutual_y = (s.at(x).at(y) - '0');
}
else if(s.at(x).at(y) != '?' && mutual_y == 2 && x % 2 == 1){
mutual_y = 1;
f_mutual_y = !(s.at(x).at(y) - '0');
}
else if(s.at(x).at(y) == '1' && x % 2 == 0 && f_mutual_y == 1){
// 0K
}
else if(s.at(x).at(y) == '1' && x % 2 == 0 && f_mutual_y == 0){
// NG
mutual_y = 0;
}
else if(s.at(x).at(y) == '1' && x % 2 == 1 && f_mutual_y == 1){
// NG
mutual_y = 0;
}
else if(s.at(x).at(y) == '1' && x % 2 == 1 && f_mutual_y == 0){
// 0K
}
else if(s.at(x).at(y) == '0' && x % 2 == 0 && f_mutual_y == 1){
// NG
mutual_y = 0;
}
else if(s.at(x).at(y) == '0' && x % 2 == 0 && f_mutual_y == 0){
// OK
}
else if(s.at(x).at(y) == '0' && x % 2 == 1 && f_mutual_y == 1){
// OK
}
else if(s.at(x).at(y) == '0' && x % 2 == 1 && f_mutual_y == 0){
// NG
mutual_y = 0;
}
}
mutual *= mutual_y;
}
// 交互ではなくても解が存在する場合
if(check){
modint not_mutual = 1;
int mutual_y = 2;
int f_mutual_y = 0;
rep(x, w){
if(first.at(x) == '?') {
not_mutual *= 2;
}
if(first.at(x) != '?' && mutual_y == 2 && x % 2 == 0){
mutual_y = 1;
f_mutual_y = first.at(x) - '0';
}
else if(first.at(x) != '?' && mutual_y == 2 && x % 2 == 1){
mutual_y = 1;
f_mutual_y = !(first.at(x) - '0');
}
else if(first.at(x) == '1' && x % 2 == 0 && f_mutual_y == 1){
// 0K
}
else if(first.at(x) == '1' && x % 2 == 0 && f_mutual_y == 0){
// NG
mutual_y = 0;
}
else if(first.at(x) == '1' && x % 2 == 1 && f_mutual_y == 1){
// NG
mutual_y = 0;
}
else if(first.at(x) == '1' && x % 2 == 1 && f_mutual_y == 0){
// 0K
}
else if(first.at(x) == '0' && x % 2 == 0 && f_mutual_y == 1){
// NG
mutual_y = 0;
}
else if(first.at(x) == '0' && x % 2 == 0 && f_mutual_y == 0){
// OK
}
else if(first.at(x) == '0' && x % 2 == 1 && f_mutual_y == 1){
// OK
}
else if(first.at(x) == '0' && x % 2 == 1 && f_mutual_y == 0){
// NG
mutual_y = 0;
}
}
not_mutual -= mutual_y;
mutual += not_mutual;
}
cout << mutual << endl;
}