201
edits
Difference between revisions of "BreakFast:2021HDU暑期多校训练营1"
Jump to navigation
Jump to search
→Problem C. Puzzle loop: add C bitset
(update C) |
(→Problem C. Puzzle loop: add C bitset) |
||
| Line 240: | Line 240: | ||
}</syntaxhighlight> | }</syntaxhighlight> | ||
=== bitset 优化 === | |||
<syntaxhighlight lang="cpp">#include <bits/stdc++.h> | |||
using namespace std; | |||
typedef long long ll; | |||
typedef unsigned long long ull; | |||
const int M = (int)1e6; | |||
const int N = (int)17; | |||
const double eps = 1e-6; | |||
const int inf = 0x3f3f3f3f; | |||
const ll mod = (ll)998244353; | |||
int n, m; | |||
char s[N + 5][N + 5]; | |||
int dx[] = {0, 0, 1, -1}; | |||
int dy[] = {1, -1, 0, 0}; | |||
int row, col; | |||
bitset<614> a[2 * (N + 1) * (N + 1) + 5]; | |||
inline int id(int x1, int y1, int x2, int y2) | |||
{ | |||
if(x1 > x2) swap(x1, x2); | |||
if(y1 > y2) swap(y1, y2); | |||
if(x1 == x2) return (x1 - 1) * m + y1; | |||
else return (n + 1) * m + (x1 - 1) * (m + 1) + y1; | |||
} | |||
void build() | |||
{ | |||
row = 0, col = (n + 1) * m + n * (m + 1); | |||
for(int i = 1; i <= n + 1; ++i) | |||
{ | |||
for(int j = 1; j <= m + 1; ++j) | |||
{ | |||
++row; | |||
a[row].reset(); | |||
for(int k = 0, x, y; k < 4; ++k) | |||
{ | |||
x = i + dx[k], y = j + dy[k]; | |||
if(x < 1 || x > n + 1 || y < 1 || y > m + 1) continue; | |||
a[row].set(id(x, y, i, j)); | |||
} | |||
} | |||
} | |||
for(int i = 1; i <= n; ++i) | |||
{ | |||
for(int j = 1; j <= m; ++j) | |||
{ | |||
if(s[i][j] == '.') continue; | |||
++row; | |||
a[row].reset(); | |||
a[row].set(id(i, j, i, j + 1)); | |||
a[row].set(id(i, j, i + 1, j)); | |||
a[row].set(id(i, j + 1, i + 1, j + 1)); | |||
a[row].set(id(i + 1, j, i + 1, j + 1)); | |||
a[row].set(col + 1, s[i][j] - '0'); | |||
} | |||
} | |||
// for(int i = 1; i <= row; ++i) | |||
// { | |||
// bool f = 0; | |||
// for(int j = 1; j <= col; ++j) | |||
// { | |||
// if(!a[i][j]) continue; | |||
// if(f) printf(" ^ "); | |||
// printf("x(%d)", j); | |||
// f = 1; | |||
// } | |||
// printf(" = 0\n"); | |||
// } | |||
} | |||
int gauss(int n, int m) | |||
{ | |||
int c, r; | |||
for(c = 1, r = 1; c <= m; ++c) | |||
{ | |||
int t = r; | |||
for(int i = r; i <= n; ++i) | |||
{ | |||
if(a[i][c]) t = i; | |||
} | |||
if(!a[t][c]) continue; | |||
swap(a[t], a[r]); | |||
for(int i = 1; i <= n; ++i) | |||
{ | |||
if(i == r) continue; | |||
if(a[i][c]) a[i] ^= a[r]; | |||
} | |||
++r; | |||
} | |||
for(int i = r; i <= n; ++i) | |||
{ | |||
if(a[i][m + 1]) return -1;//无解 | |||
} | |||
return m - r + 1;//自由元个数 | |||
} | |||
ll quick(ll a, ll b, ll p = mod) | |||
{ | |||
ll s = 1; | |||
while(b) | |||
{ | |||
if(b & 1) s = s * a % p; | |||
a = a * a % p; | |||
b >>= 1; | |||
} | |||
return s; | |||
} | |||
void work() | |||
{ | |||
scanf("%d %d", &n, &m); | |||
--n, --m; | |||
for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1); | |||
build(); | |||
int r = gauss(row, col); | |||
if(r == -1) printf("0\n"); | |||
else printf("%lld\n", quick(2, r)); | |||
} | |||
int main() | |||
{ | |||
// freopen("input.txt", "r", stdin); | |||
// freopen("output.txt", "w", stdout); | |||
// ios::sync_with_stdio(0); | |||
// cin.tie(0); cout.tie(0); | |||
int T; scanf("%d", &T); | |||
for(int ca = 1; ca <= T; ++ca) | |||
{ | |||
// printf("Case #%d:\n", ca); | |||
work(); | |||
} | |||
// work(); | |||
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n"; | |||
return 0; | |||
}</syntaxhighlight> | |||
[https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop] | [https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop] | ||