原题连接
更好的阅读体验

题目描述

有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。

你的目标是经过若干次开关操作后使得最后$N$个开关达到一个特定的状态。

对于任意一个开关，最多只能进行一次开关操作。

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

输入格式
输入第一行有一个数$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~!!

高斯消元+异或空间

设$x_i$表示第$i$个开关的操作情况,那么$x_i=1$为按了这个开关,否则$x_i=0$表示这个开关并没有按下去,那么我们接着统计$a_{i,j}$表示第i个开关和第j个开关的联系情况,$a_{i,j}=1$表示按下j会影响i的状态,否则就是不会影响,即$a_{i,j}=0$,特殊地一个点就是,$a_{i,i}=1$,因为我们本身肯定会影响本身.

我们用int整数,来存储一个n+1位的二进制数

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int a[110],n,t,ans,x,y;
signed main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            a[i]^=x;
            a[i]|=1<<i;
        }
        while(cin>>x>>y && (x && y))
            a[y]|=1<<x;
        ans=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
                if (a[j]>a[i])
                    swap(a[i],a[j]);
            if (a[i]==0)
            {
                ans=1<<(n-i+1);
                break;
            }
            if (a[i]==1)
            {
                ans=0;
                break;
            }
            for(int k=n;k;k--)
                if (a[i]>>k & 1)
                {
                    for(int j=1;j<=n;j++)
                        if (i!=j && (a[j]>>k & 1))
                            a[j]^=a[i];
                    break;
                }
        }
        if (ans==0)
            cout<<"Oh,it's impossible~!!"<<endl;
        else
            cout<<ans<<endl;
    }
}