首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#7475

开关问题(2023.12) 有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这…

开关问题(2023.12)

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

时间限制:1000

内存限制:65536

输入

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

输出

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


样例输入

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

样例输出

4
Oh,it's impossible~!!

提示

第一组数据的说明:一共以下四种方法: 操作开关1 操作开关2 操作开关3 操作开关1、2、3 (不记顺序)

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; const int MAXN = 35; bool a[MAXN][MAXN]; inline int read() {   int x;   scanf("%d", &amp;x);   return x; } int gauss(int n) {   int rank = 0;   for (int d = 0; d &lt; n; ++d) { /* d for diagonal */     int i;     /* try to find first line whose d'th element = 1 */     for (i = d; i &lt; n; ++i)       if (a[i][d] == 1)         break;     /* not found */     if (i == n)       continue;     /* found */     /* Step 1: make the d'th element of rank'th line to be 1, by swapping i'th      * line and rank'th line, including the rightmost column */     for (int j = 0; j &lt;= n; ++j)       swap(a[rank][j], a[i][j]);     /* Step 2: eliminating the following line if the d'th element = 1, including      * the rightmost column */     for (i = rank + 1; i &lt; n; ++i)       if (a[i][d])         for (int j = 0; j &lt;= n; ++j)           a[i][j] ^= a[rank][j];     ++rank;   }   /* up to now, the rank+'th line should be all 0 */   /* if the rightmost column is 1, bad equation, return -1 */   for (int i = rank; i &lt; n; ++i)     if (a[i][n])       return -1;   /* otherwise, return the rank */   return rank; } int main() {   int K = read();   for (int k = 0; k &lt; K; ++k) {     memset(a, 0, sizeof(a));     int N = read();     for (int i = 0; i &lt; N; ++i)       a[i][N] ^= read();     for (int i = 0; i &lt; N; ++i)       a[i][N] ^= read();     for (int x = 0; x &lt; N; ++x)       a[x][x] = 1;     for (;;) {       int x = read() - 1, y = read() - 1;       if (x == -1)         break;       a[y][x] = 1;     }     int rank = gauss(N);     if (rank == -1)       printf("Oh,it's impossible~!!\n");     else       printf("%d\n", 1 &lt;&lt; (N - rank));   }   system("pause");   return 0; }</pre>
这道题暂未补解析。