思路

做法一

用二进制状态压缩枚举操作哪些开关能够满足条件即可。

时间复杂度：$O(2^N)$

#include <iostream>
#include <cstring>

using namespace std;

const int N = 30, M = 1000;

int n, idx;
int h[N], e[M], ne[M];
bool a[N], b[N], backup[N];

bool check(){
  for (int i = 0; i < n; i ++ )
    if (a[i] ^ b[i])  return 0;

  return 1;
}

void turn(int x){
  a[x] = !a[x];
  for (int i = h[x]; ~ i; i = ne[i]){
    int j = e[i];
    a[j] = !a[j];
  }
}

void insert(int a, int b){
  e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void init(){
  idx = 0;
  memset(e, 0, sizeof e);
  memset(ne, 0, sizeof ne);
  memset(h, -1, sizeof h);
}

void solve(){
  init();

  cin >> n;
  for (int i = 0; i < n; i ++ )
    cin >> a[i];

  for (int i = 0; i < n; i ++ )
    cin >> b[i];

  int x, y;
  while (cin >> x >> y, x or y)
    insert(x - 1, y - 1);

  int res = 0;

  for (int bits = 0; bits < 1 << n; bits ++ ){
    memcpy(backup, a, sizeof a);

    for (int j = 0; j < n; j ++ )
      if (bits >> j & 1) turn(n - j - 1);

    res += check();

    memcpy(a, backup, sizeof backup);
  }

  if (res)  cout << res << endl;
  else puts("Oh,it's impossible~!!");
}

int main(){
  int t;
  cin >> t;
  while (t -- )
    solve();

  return 0;
}

做法二

转化为异或方程组来做

对每个开关，找出所有可影响到这个开关的所有开关（包括它本身），然后使其异或和为决定这个开关最终是开还是不开。（此处需要观看官方题解视频来理解。）

最终可以得到$N$个异或方程的方程组。用高斯消元求解。

如果无解，则输出无解的字符串。

如果有解，那么这个方程组中自由变量的个数为$k$，则答案为$2^k$。因为每个自由变量都可以取值为2种值 $0，1$，其他非自由变量受自由变量的影响，也就是说自由变量的取值方法都只能唯一的对应出各非自由变量的取值方法，而各自由变量之间取值方法不受影响。（线性代数知识）

时间复杂度：$O(N^3)$

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 30;

int a[N], b[N];
int f[N][N];
int n;

void print(){
  for (int i = 1; i <= n; i ++ ){
    for (int j = 1; j <= n + 1; j ++ )
      cout << f[i][j] << " ";

    cout << endl;
  }
}
void gauss(){

  int r, c;
  for (r = 1, c = 1; c <= n; c ++ ){

    int t = -1;
    for (int i = r; i <= n; i ++ )
      if (f[i][c]){
        t = i;
        break;
      }

    if (t == -1)  continue;

    for (int i = c; i <= n + 1; i ++ )
      swap(f[t][i], f[r][i]);

    for (int i = r + 1; i <= n; i ++ )
      if (f[i][c])
        for (int j = n + 1; j >= c; j -- )
          f[i][j] ^= f[r][j];

    r ++ ;

  }

  if (r == n + 1)
    cout << 1 << endl;
  else if (r < n + 1)
    if (f[r][n + 1])
      puts("Oh,it's impossible~!!");
    else 
      cout << (1 << n - r + 1) << endl;
}

int main(){
  int t;
  cin >> t;
  while (t -- ){
    memset(f, 0, sizeof f);

    cin >> n;
    for (int i = 1; i <= n; i ++ )
      cin >> a[i];

    for (int j = 1; j <= n; j ++ )
      cin >> b[j];

    for (int i = 1; i <= n; i ++ )
      f[i][i] = 1;

    int x, y;
    while (cin >> x >> y, x or y)
      f[y][x] = 1;

    for (int i = 1; i <= n; i ++ )
      f[i][n + 1] = a[i] ^ b[i];

    gauss();
  }

  return 0;
}