2023年ICPC济南站G题

2024-03-13 22:12

文章标签 2023 icpc 济南

本文主要是介绍2023年ICPC济南站G题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Gifts from Knowledge

题意

给定r行c列的01矩阵，可以对每一行进行翻转，也可以不进行操作，翻转的意思是将一开始的序列{ $a_{1}, a_{2}, \dots, a_{n}$ }翻转为{ $a_{n},\dots,a_{2},a_{1}$ },使得最终得到的01矩阵的每一列的1的个数不多于1个，问有多少种翻转方案，对结果模1e9+7

分析

容易知道的是，设第i列和第c-i+1列总的1的个数为x，当x$\geq $3 后，无解，当 x$ \leq$1时，无论怎么操作，这两列永远合法，所以最终只需要考虑当x=2时。

当x=2时有两种情况，假设两个1分别位于第x和y行

初始时，两个1位于同一列，那么能进行的操作就是{(翻转x，y不动)，(不动x，翻转y)}
初始时，两个1位于不同列，那么能进行的操作就是{(翻转x，翻转y)，(不动x，不动y)}

由此两种情况我们可以发现，当同一对x和y同时拥有以上两种情况的时候是无解的，比如：

2 6
101010
100100

这个样例就是无解的，因此需要做的就是使用扩展域并查集，i表示翻转第i行，i+n表示不翻转第i行，因此，当两个1位于同一列的时候，合并(x, y+n)和(x+n, y)，当两个1位于不同列的时候，合并(x, y)和(x+n, y+n)，注意要判断i和i+n是否在一个连通块内，答案就是 $2^{连通块的个数}$

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;
void Solve() {int n, m;cin >> n >> m;vector<string> a(n + 1);vector<vector<int> > G(m + 1);for (int i = 1; i <= n; i++) {cin >> a[i];a[i] = ' ' + a[i];bool ok = false;for (int j = 1; j <= m; j++) {if (a[i][j] == '1') {G[j].emplace_back(i);ok = true;}}}vector<int> fa(2 * n + 1);iota(fa.begin(), fa.end(), 0);auto getfa = [&](int x, auto getfa) -> int {return x == fa[x] ? x : fa[x] = getfa(fa[x], getfa);};for (int i = 1; i <= m; i++) {if (i == m - i + 1) {if (G[i].size() > 1) {cout << "0\n";return;}} else {if (G[i].size() + G[m - i + 1].size() >= 3) {cout << "0\n";return;}if (G[i].size() + G[m - i + 1].size() == 2) {vector<int> z;for (auto it : G[i]) {z.emplace_back(it);}for (auto it : G[m - i + 1]) {z.emplace_back(it);}if (G[i].size() == 1) {int f1 = getfa(z[0], getfa), f2 = getfa(z[1], getfa);if (f1 != f2) {fa[f1] = f2;}f1 = getfa(z[0] + n, getfa), f2 = getfa(z[1] + n, getfa);if (f1 != f2) {fa[f1] = f2;}} else {int f1 = getfa(z[0], getfa), f2 = getfa(z[1] + n, getfa);if (f1 != f2) {fa[f1] = f2;}f1 = getfa(z[0] + n, getfa), f2 = getfa(z[1], getfa);if (f1 != f2) {fa[f1] = f2;}}}}}for (int i = 1; i <= n; i++) {if (getfa(i, getfa) == getfa(i + n, getfa)) {cout << "0\n";return;}}LL ans = 1;for (int i = 1; i <= n; i++) {if (getfa(i, getfa) == i) {ans = ans * 2 % mod;}}cout << ans << '\n';
}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int T;cin >> T;while (T--) {Solve();}return 0;
}