201
edits
Difference between revisions of "BreakFast:2021HDU暑期多校训练营1"
Jump to navigation
Jump to search
update C
(update AEFGHIJK) |
(update C) |
||
| Line 70: | Line 70: | ||
[https://acm.hdu.edu.cn/showproblem.php?pid=6951 Problem B. Rocket land] | [https://acm.hdu.edu.cn/showproblem.php?pid=6951 Problem B. Rocket land] | ||
[https://acm.hdu.edu.cn/showproblem.php?pid=6952 Problem C. Puzzle loop] | == [https://acm.hdu.edu.cn/showproblem.php?pid=6952 Problem C. Puzzle loop] == | ||
=== 题目大意 === | |||
<math display="inline">T</math> 组输入，每组输入一个大小为 <math display="inline">(n - 1) \times (m - 1)</math> 的地图，地图字符集为 <math display="inline">\{'0', '1', '.'\}</math>. | |||
<math display="inline">'0'</math> 表示该格子周围四条边有偶数条红边. | |||
<math display="inline">'1'</math> 表示该格子周围四条边有奇数条红边. | |||
<math display="inline">'.'</math> 表示该格子周围四条边无限制. | |||
要求红边形成若干个边不相交的环，求方案数. | |||
<math display="inline">1 \leq T \leq 100, 1 \leq n, m \leq 17</math>. | |||
=== 分析 === | |||
红边实质上就是若个干不相交的欧拉路嘛，因此要求每个交点的度为偶数，这样便满足了形成若干个边不相交的环这一条件. | |||
此外对每个格子的四条边建异或方程. | |||
于是得到异或方程组，高斯消元即可. | |||
=== 代码实现 === | |||
<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; | |||
bool a[2 * (N + 1) * (N + 1) + 5][2 * N * (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; | |||
for(int k = 1; k <= col + 1; ++k) a[row][k] = 0; | |||
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][id(x, y, i, j)] = 1; | |||
} | |||
} | |||
} | |||
for(int i = 1; i <= n; ++i) | |||
{ | |||
for(int j = 1; j <= m; ++j) | |||
{ | |||
if(s[i][j] == '.') continue; | |||
++row; | |||
for(int k = 1; k <= col + 1; ++k) a[row][k] = 0; | |||
a[row][id(i, j, i, j + 1)] = 1; | |||
a[row][id(i, j, i + 1, j)] = 1; | |||
a[row][id(i, j + 1, i + 1, j + 1)] = 1; | |||
a[row][id(i + 1, j, i + 1, j + 1)] = 1; | |||
a[row][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; | |||
for(int i = c; i <= m + 1; ++i) swap(a[t][i], a[r][i]); | |||
for(int i = 1; i <= n; ++i) | |||
{ | |||
if(i == r) continue; | |||
if(a[i][c]) | |||
{ | |||
for(int j = m + 1; j >= c; --j) | |||
{ | |||
a[i][j] ^= a[r][j]; | |||
} | |||
} | |||
} | |||
++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] | ||