『开关问题异或高消』

小灰灰 2021-12-21 21:04 266阅读 0赞

--------------------

## 开关问题(POJ 1830) ##

### Description ###

有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。

你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）

### Input Format ###

输入第一行有一个数K，表示以下有K组测试数据。 每组测试数据的格式如下： 第一行 一个数N（0 < N < 29） 第二行 N个0或者1的数，表示开始时N个开关状态。 第三行 N个0或者1的数，表示操作结束后N个开关的状态。 接下来 每行两个数I J，表示如果操作第 I 个开关，第J个开关的状态也会变化。每组数据以 0 0 结束。

### Output Format ###

如果有可行方法，输出总数，否则输出“Oh,it's impossible~!!” 不包括引号

### Sample Input ###

2  
    3  
    0 0 0  
    1 1 1  
    1 2  
    1 3  
    2 1  
    2 3  
    3 1  
    3 2  
    0 0  
    3  
    0 0 0  
    1 0 1  
    1 2  
    2 1  
    0 0

### Sample Output ###

4  
    Oh,it's impossible~!!

### 解析 ###

设\\(x\_i\\)代表是否操作了第\\(i\\)个开关，按了为\\(1\\)，不按为\\(0\\)。\\(f\_\{ij\}\\)代表开关\\(i\\)和开关\\(j\\)的联系情况，按下\\(j\\)会影响\\(i\\)则\\(f\_\{ij\}=1\\)，反之\\(f\_\{ij\}=0\\)，对于任意的\\(i\\)，令\\(f\_\{ii\}=1\\)。

如果将第\\(i\\)个开关最后是否变化记为\\(p\_i\\)的话，就可以得到异或方程组：  
\\\[ \\begin\{cases\} f\_\{11\}x\_\{1\}\\ xor \\ f\_\{12\}x\_\{2\}\\ xor\\ ... \\ xor\\ f\_\{1n\}x\_n=p\_1 \\\\ f\_\{21\}x\_\{1\}\\ xor \\ f\_\{22\}x\_\{2\}\\ xor\\ ... \\ xor\\ f\_\{2n\}x\_n=p\_2 \\\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ ... \\\\ f\_\{n1\}x\_\{1\}\\ xor \\ f\_\{n2\}x\_\{2\}\\ xor\\ ... \\ xor\\ f\_\{nn\}x\_n=p\_n \\end\{cases\} \\\]

同样地，这个方程组也是可以高斯消元的，只需将加减操作改为异或即可。

对于本题，求的是方案数，那么我们分高斯消元的三种情况处理即可。当方程组恰好有解时，方案数为\\(1\\)，当方程组无解时，方案数为\\(0\\)，当方程组无穷解时，记录下自由元的个数\\(p\\)，由于每个\\(x\\)可以取\\(1\\)或\\(0\\)，所以方案数为\\(2^\{p\}\\)。

由于本题增广矩阵中所有元素非\\(1\\)即\\(0\\)，所以可以状态压缩一下，方便运算。

\\(Code:\\)

#include <bits/stdc++.h> using namespace std; const int N=30; int n,f[N],ans,t; inline void input(void) { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&f[i]); int x,y; for (int i=1;i<=n;i++) { scanf("%d",&x); f[i] ^= x; } while ( scanf("%d%d",&x,&y) && x && y ) f[y] |= 1 << x; } inline void init(void) { for (int i=1;i<=n;i++) f[i] |= 1 << i; } inline void Gauss(void) { ans = 1; for (int i=1;i<=n;i++) { for (int j=i+1;j<=n;j++) if ( f[j] > f[i] ) swap(f[j],f[i]); if (!f[i]){ans = 1 << (n-i+1);break;} if (f[i]==1){ans = 0;break;} for (int j=n;j>=1;j--) { if (f[i] >> j & 1) { for (int k=1;k<=n;k++) if ( i ^ k && ( f[k] >> j & 1 ) ) f[k] ^= f[i]; break; } } } } int main(void) { freopen("switch.in","r",stdin); freopen("switch.out","w",stdout); scanf("%d",&t); while (t--) { input(); init(); Gauss(); if ( !ans )printf("Oh,it's impossible~!!\n"); else printf("%d\n",ans); } return 0; }

--------------------

转载于:https://www.cnblogs.com/Parsnip/p/10716893.html