結果
| 問題 | No.226 0-1パズル |
| ユーザー |
 KowerKoint2010
|
| 提出日時 | 2019-11-06 23:34:48 |
| 言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 5,000 ms |
| コード長 | 5,214 bytes |
| コンパイル時間 | 1,513 ms |
| コンパイル使用メモリ | 167,948 KB |
| 実行使用メモリ | 4,380 KB |
| 最終ジャッジ日時 | 2023-10-04 12:08:01 |
| 合計ジャッジ時間 | 2,484 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 2 ms
4,380 KB |
| testcase_04 | AC | 1 ms
4,376 KB |
| testcase_05 | AC | 2 ms
4,376 KB |
| testcase_06 | AC | 1 ms
4,380 KB |
| testcase_07 | AC | 1 ms
4,376 KB |
| testcase_08 | AC | 1 ms
4,376 KB |
| testcase_09 | AC | 2 ms
4,380 KB |
| testcase_10 | AC | 1 ms
4,380 KB |
| testcase_11 | AC | 1 ms
4,376 KB |
| testcase_12 | AC | 1 ms
4,376 KB |
| testcase_13 | AC | 1 ms
4,376 KB |
| testcase_14 | AC | 1 ms
4,376 KB |
| testcase_15 | AC | 1 ms
4,380 KB |
| testcase_16 | AC | 2 ms
4,380 KB |
| testcase_17 | AC | 2 ms
4,376 KB |
| testcase_18 | AC | 2 ms
4,376 KB |
| testcase_19 | AC | 2 ms
4,376 KB |
| testcase_20 | AC | 2 ms
4,376 KB |
| testcase_21 | AC | 2 ms
4,376 KB |
ソースコード
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const int ddx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};
ll gcd(ll a, ll b) {
if(b == 0) return a;
return gcd(b, a % b);
}
int extgcd(int a, int b, int& x, int&y) {
int d = a;
if(b != 0) {
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}else {
x = 1;
y = 0;
}
return d;
}
int inv(int a) {
int x, y;
extgcd(a, MOD, x, y);
return (x + MOD) % MOD;
}
struct modint {
int val;
modint() {
val = 0;
}
modint(int n) {
val = n % MOD;
}
modint &operator=(const modint &x) {
val = x.val;
return *this;
}
bool operator==(const modint &rhs) const {return val == rhs.val;}
modint operator+(const modint &rhs) const {return modint((val + rhs.val) % MOD);}
modint operator-(const modint &rhs) const {return modint((val + MOD - rhs.val) % MOD);}
modint operator*(const modint &rhs) const {return modint((int)((ll)val * rhs.val % MOD));}
modint operator/(const modint &rhs) const {return modint((int)((ll)val * inv(rhs.val) % MOD));}
modint &operator+=(const modint &rhs) {
val = (val + rhs.val) % MOD;
return *this;
}
modint &operator-=(const modint &rhs) {
val = (val + MOD- rhs.val) % MOD;
return *this;
}
modint &operator*=(const modint &rhs) {
val = (int)((ll)val * rhs.val % MOD);
return *this;
}
modint &operator/=(const modint &rhs) {
val = (int)((ll)val * inv(rhs.val) % MOD);
return *this;
}
};
struct unitree {
int *par, *rank, *sz;
unitree(int n) {
par = new int[n];
rank = new int[n];
sz = new int[n];
for(int i = 0; i < n; i++) {
par[i] = i;
rank[i] = 0;
sz[i] = 1;
}
}
int root(int x) {
if(par[x] == x) return x;
else return par[x] = root(par[x]);
}
void merge(int x, int y) {
x = root(x);
y = root(y);
if(x == y) return;
if(rank[x] < rank[y]) {
par[x] = y;
sz[y] += sz[x];
}else {
par[y] = x;
if(rank[x] == rank[y]) rank[x]++;
sz[x] += sz[y];
}
}
bool same(int x, int y) {
return root(x) == root(y);
}
int siz(int x) {
return sz[root(x)];
}
};
bool check(ll mid) {
return true;
}
ll bin(ll left, ll right) {
while(right - left > 1) {
ll mid = (left + right) / 2;
if(check(mid)) left = mid;
else right = mid;
}
return left;
}
struct vect {
ll x, y;
vect() {
x = 0;
y = 0;
}
vect(ll x, ll y) {
this->x = x;
this->y = y;
}
int posi() const {
if(x == 0 && y == 0) exit(1);
if(x > 0 && y == 0) return 0;
if(x > 0 && y > 0) return 1;
if(x == 0 && y > 0) return 2;
if(x < 0 && y > 0) return 3;
if(x < 0 && y == 0) return 4;
if(x < 0 && y < 0) return 5;
if(x == 0 && y < 0) return 6;
if(x > 0 && y < 0) return 7;
}
int posi(const vect& v) const {
ll s = x * v.y - y * v.x;
ll c = x * v.x + y * v.y;
if(s == 0 && c == 0) exit(1);
if(s == 0 && c > 0) return 0;
if(s > 0 && c > 0) return 1;
if(s > 0 && c == 0) return 2;
if(s > 0 && c < 0) return 3;
if(s == 0 && c < 0) return 4;
if(s < 0 && c < 0) return 5;
if(s < 0 && c == 0) return 6;
if(s < 0 && c > 0) return 7;
}
bool operator<(const vect& rhs) {
int p1 = posi();
int p2 = rhs.posi();
if(p1 != p2) return p1 < p2;
return rhs.x * y < x * rhs.y;
}
};
signed main() {
int h, w;
cin >> h >> w;
char** s = new char*[h];
rep(i, h) {
s[i] = new char[w];
string str;
cin >> str;
rep(j, w) {
s[i][j] = str[j];
}
}
modint ans(1);
rep(i, h) {
modint tmp(0);
rep(x, 2) {
bool flag = true;
rep(j, w) {
if(s[i][j] != '?' && s[i][j] != '0' + (x + j) % 2) flag = false;
}
if(flag) tmp += modint(1);
}
ans *= tmp;
}
rep(x, 2) {
bool flag = true;
rep(i, h) {
rep(j, w) {
if(s[i][j] != '?' && s[i][j] != '0' + (x + i + j) % 2) flag = false;
}
}
if(flag) ans -= modint(1);
}
modint ans2(1);
rep(j, w) {
modint tmp(0);
rep(x, 2) {
bool flag = true;
rep(i, h) {
if(s[i][j] != '?' && s[i][j] != '0' + (x + i) % 2) flag = false;
}
if(flag) tmp += modint(1);
}
ans2 *= tmp;
}
cout << (ans + ans2).val << endl;
}