作为异或高斯消元的例题,怎么把这道题和高斯消元联系起来花了我好久
题意简述
给出 个开关的初态、终态与关联关系,求有多少种操作方法可以到达终态。每个开关至多操作一次。
思路解析
首先要解决一个问题:它和高斯消元到底有什么关系??
如何利用高斯消元解决这个问题?
看到题中的关联关系,我们可以想到这是不是一道图论开关本身和与它关联的所有开关的操作应该满足一定的条件这不废话。不过这个思路很不清晰不要说这么多废话啊喂,所以接下来要解决的就是细节问题。
先看一下前半部分。
开关和与它关联的开关的操作怎么表示?
我们先假设有两个初始均为关闭状态的开关 ,且 对 有关联关系。
- 若 被操作, 未被操作。此时 最后的状态为开。
- 若 被操作, 亦被操作。此时 最后的状态为关。
- 若 未被操作, 被操作。此时 最后的状态为开。
- 若 未被操作, 亦未被操作。此时 最后的状态为关。
虽然看起来很乱也许其中有某些规律?仔细思考后不难发现如果将被操作与否、开启与关闭用 表示,那么开关的操作和终态之间有异或关系。也就是说,我们把所有的操作异或起来,得到的答案应满足题中给出的终态。
再看后半部分。
题中的条件具体指什么?
这个条件对应的应该是方程中的终态,如果我们仅仅将开关最后的状态作为终态的话,很明显在开关初始为开启的时候就不行了。所以应该对它进行改动,实际上,终态应为「开关的状态是否发生了变化」。再对应到 和 ,就满足了前面说的异或关系。
对于方程的系数,如果开关 对开关 有关联关系,那么在对开关 列出的方程中, 的系数就应为 ,否则为 。
这样,对于每一个开关都可以得出一个方程,将这些方程组成一系列方程组就可以使用高斯消元解决了。成功将看起来完全不相干的事物联系起来了
如何统计解的数量?
无解的情况和只有一种解的情况高斯消元可以帮我们判断,但是有多重解的时候就得自己上了。
已知有 个方程组,所以有 个固定变量,所以最后解的个数是 。
自己碰运气做对后乱七八糟想了一大堆结果是去看了题解才知道为什么
AC Code
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN = 110;
int n;
int a[MAXN][MAXN];
void swap(int & a, int & b)
{
int t = a;
a = b, b = t;
}
int gauss()
{
int r, c;
for (r = 0, c = 0; c < n; c++) {
int t = r;
for (int i = r; i < n; i++) {
if (a[i][c]) {
t = i;
break;
}
}
if (a[t][c] == 0) {
continue;
}
for (int i = c; i <= n; i++) {
swap(a[t][i], a[r][i]);
}
for (int i = r + 1; i < n; i++) {
if (a[i][c]) {
for (int j = c; j <= n; j++) {
a[i][j] ^= a[r][j];
}
}
}
r++;
}
if (r < n) {
for (int i = r; i < n; i++) {
if (a[i][n]) {
return -1;
}
}
}
return pow(2, n - r); // r 就对应上面的 K
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
#endif
int K;
scanf("%d", &K);
while (K--) {
memset(a, 0, sizeof a);
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i][n]);
}
for (int i = 0; i < n; i++) {
int t;
scanf("%d", &t);
a[i][n] ^= t; // 求出是否变化
a[i][i] = 1; // 这里必须要有
}
int x, y;
while (scanf("%d%d", &x, &y) != EOF && x && y) {
a[y - 1][x - 1] = 1;
}
int t = gauss();
if (t == -1) {
printf("Oh,it's impossible~!!\n");
}
else {
printf("%d\n", t);
}
}
return 0;
}