开关游戏：计算达到目标状态的方法数

给定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~!!' 不包括引号

样例输入

样例输出

4
Oh,it's impossible~!!

提示

第一组数据的说明：

一共以下四种方法：

操作开关1
操作开关2
操作开关3
操作开关1、2、3 （不记顺序）

C++代码

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<int> start_state;
vector<int> end_state;
vector<vector<int>> switches;

int count = 0;

void dfs(int index, vector<int>& state) {
    // 如果已经遍历完所有开关
    if (index == N) {
        // 判断当前状态是否与目标状态相同
        if (state == end_state) {
            count++;
        }
        return;
    }

    // 不操作当前开关
    dfs(index + 1, state);

    // 操作当前开关
    for (int i = 0; i < switches[index].size(); i++) {
        int switch_index = switches[index][i];
        state[switch_index] = 1 - state[switch_index]; // 状态取反
    }
    dfs(index + 1, state);
    for (int i = 0; i < switches[index].size(); i++) {
        int switch_index = switches[index][i];
        state[switch_index] = 1 - state[switch_index]; // 恢复状态
    }
}

int main() {
    int K;
    cin >> K;
    while (K--) {
        cin >> N;
        start_state.resize(N);
        end_state.resize(N);
        switches.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> start_state[i];
        }
        for (int i = 0; i < N; i++) {
            cin >> end_state[i];
        }
        int I, J;
        cin >> I >> J;
        while (I != 0 || J != 0) {
            switches[I - 1].push_back(J - 1);
            cin >> I >> J;
        }

        vector<int> state(N, 0); // 初始状态全部为0
        count = 0;
        dfs(0, state);

        if (count == 0) {
            cout << "Oh,it's impossible~!!" << endl;
        } else {
            cout << count << endl;
        }

        start_state.clear();
        end_state.clear();
        switches.clear();
    }
    return 0;
}