形式化题目

有 $N$ 个开关，每个开关的初始状态与目标状态都由 $N$ 个 $0/1$ 给出。给定一组有向关系 I J： 操作第 $I$ 个开关时，第 $J$ 个开关的状态也会翻转（反过来不保证成立）。对于任意 I，操作 I 一定翻转 I 自己。每个开关最多被操作一次。

求能达成目标状态的操作集合个数（不计操作顺序）。

记 $x_i\in\{0,1\}$ 表示是否操作第 $i$ 个开关，$a_{i,j}=1$ 表示操作 $i$ 会翻转 $j$（含 $a_{i,i}=1$）， $b_j=\text{st}_j\oplus\text{ed}_j$ 表示第 $j$ 位需要被翻转的奇偶性。则一个操作集合 $x$ 能达成目标，当且仅当它满足下面 $N$ 条方程：

约束：$0<N<29$，即 $N\leqslant 28$；$K$ 组测试数据独立。

一个必须先说清的读题点：I J 是有向的。 题面「其他的与此开关相关联的开关也会相应地发生变化」描述的是操作 $I$ 的效果， 而数据里的 I J 是逐对列出的：给 1 2 不给 2 1 时，操作 2 不会影响 1。 真实数据 switch 1-6 的第 4 组（$N=15$，答案为 Oh,it's impossible~!!） 只有 1 10 / 1 2 / 1 3 / 1 4 / 2 5 / 2 1 六条边：把它当无向图会算出 $4$，与标准答案不符。 本文与代码一律按有向处理。

正解

思路

朴素做法：枚举 $2^N$ 个操作集合

每个开关只有「按 / 不按」两种选择，于是最直接的做法是枚举全部 $2^N$ 个操作集合， 对每个集合模拟一遍「按下 $i$ 就翻转 $i$ 及所有被 $i$ 影响的开关」，看是否等于目标状态。

这个做法绝对正确：同一个集合内的操作先后顺序不影响结果，枚举也既不重复也不遗漏。 但它的瓶颈极其明确——搜索空间是 $2^N$。$N=28$ 时是 $2.7\times10^8$ 个集合， 每个还要 $O(N^2)$ 模拟，并且 $K$ 组数据都要重来，Python 与 C++ 都跑不动。

换一个视角：不要枚举解，只要数解

题目只问「有多少种方法」，不问具体是哪些方法。所以只要能刻画解集的结构，就可以直接数出个数。

关键观察是：顺序无关 + 每个开关最多一次 + 翻转两次抵消，三者合起来说明第 $j$ 个开关的最终 状态只取决于「会翻转第 $j$ 位的那些被操作开关」的个数的奇偶性。把「是否操作 $i$」记成 一个 GF(2) 上的变量 $x_i$，那么「第 $j$ 位达到目标」就写成一条线性方程：

一共有 $N$ 个位置，于是得到 $N$ 条方程的 GF(2) 线性方程组。解集是一个仿射子空间： 设系数矩阵的秩为 $r$，若方程组有解则恰有 $2^{\,N-r}$ 个解（$N-r$ 个自由变量任意取值）， 若无解则一个解都没有。于是问题从「枚举 $2^N$ 个解」变成「求一个秩 $+$ 判一次矛盾」。

有向边怎么进方程：方程按「位置」编号

这一步是本题最容易写反的地方。因为 I J 是有向的，方程要按输出位置 $j$ 编号， 而不是按开关 $i$ 编号：

• 读到 i j：说明「操作 $i$ 会翻转 $j$」，于是变量 $x_i$ 出现在第 $j$ 行；
• 每个开关一定翻转自己，所以每行补上自环：变量 $x_j$ 也出现在第 $j$ 行；
• 第 $j$ 行的右端常数就是 $b_j$。

位压缩：一行一个整数

$N\leqslant 28$ 给了我们一个便宜的实现方式：把第 $j$ 行压成一个整数， 低 $N$ 位放系数（第 $i$ 位是 $a_{i,j}$），第 $N$ 位放常数 $b_j$。 这样一次整行异或就是 GF(2) 上的一次初等行变换，消元的内层循环被压缩成一次 ^=。

常数项必须放在第 $N$ 位、而不是最低位：若常数占第 $0$ 位，它会和变量 $x_1$ 的系数位撞在一起， 消元时无法区分这两者。放在第 $N$ 位后，变量占 $[0,N)$、常数独占第 $N$ 位， 「出现 $0=1$」就退化成一句比较 row == 1 << n。

用样例核对

样例 1：$N=3$，$000\to111$，六条边构成完全有向图（去掉自环）。第 $j$ 行的三个系数都是 $1$（自环 + 另外两个开关都能影响它），三行完全相同：

消元后只剩一行 1 1 1 | 1，即 $x_1\oplus x_2\oplus x_3=1$：秩 $r=1$，自由元 $N-r=2$， 答案 $2^2=4$。这四个解正是「按下奇数个开关」的全部集合，与样例输出一致。

样例 2：$N=3$，$000\to101$，边只有 1 2 与 2 1：

第 1、2 行系数相同而常数不同，异或后得到 0 0 0 | 1，即 $0=1$，方程组无解， 输出 Oh,it's impossible~!!。直观上也确实做不到：第 1 位和第 2 位只能被 $x_1,x_2$ 同时影响（翻转就一起翻转），无法一个翻一个不翻。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 16:27
# update_at: 2026-10-01 16:33

import sys
from collections.abc import Iterator

IMPOSSIBLE = "Oh,it's impossible~!!"  # 无解时的固定输出（题面原文，含两个感叹号）


def build_equations(n: int, start: list[int], goal: list[int], data: Iterator[int]) -> list[int]:
    """把本组数据变成 n 个方程：第 j 行的低 n 位记录「哪些开关会改变第 j 位」。

    第 j 位的最终状态只由「会带动 j 的那些开关」以及 j 自己决定，所以每个方程
    对应一个输出位置 j，而不是一个开关。
    """
    rows = [0] * n
    i, j = next(data), next(data)  # 一对 I J；读到 0 0 表示本组结束
    while j:
        rows[j - 1] ^= 1 << (i - 1)  # 变量 i 出现在第 j 行：按 i 会带动 j
        i, j = next(data), next(data)
    for j in range(n):
        rows[j] |= 1 << j  # 主对角元：按 j 自己必定改变第 j 位
    # 第 j 位要求翻转恰好 (start[j] ^ goal[j]) 次，把它作为常数项放到第 n 位。
    return [row ^ (start[j] ^ goal[j]) << n for j, row in enumerate(rows)]


def free_variables(rows: list[int], n: int) -> int:
    """把每一行看成「变量系数写在低 n 位、右端常数写在第 n 位」的整数，返回自由元个数。

    返回 -1 表示出现 0 = 1 的矛盾行（无解）。消元时用「取最低位的行」当主元行，
    这样第 j 列的主元恰好是第 j 位。
    """
    rows = [row for row in rows if row]  # 全零行不含任何信息，直接丢掉
    rank = 0
    for col in range(n):
        pivot = -1
        for k in range(rank, len(rows)):
            if rows[k] >> col & 1:
                pivot = k
                break
        if pivot < 0:
            continue  # 这一列没有主元，该变量自由
        rows[rank], rows[pivot] = rows[pivot], rows[rank]
        pivot_row = rows[rank]
        for k in range(len(rows)):
            if k != rank and rows[k] >> col & 1:
                rows[k] ^= pivot_row  # 整行异或，右端常数跟着一起变
        rank += 1
    if any(row == 1 << n for row in rows):  # 只剩常数位的 0 = 1
        return -1
    return n - rank


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    cases = next(data)  # 题面的 K

    for _ in range(cases):
        n = next(data)
        start = [next(data) for _ in range(n)]
        goal = [next(data) for _ in range(n)]
        free = free_variables(build_equations(n, start, goal, data), n)
        out.append(IMPOSSIBLE if free < 0 else str(1 << free))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 18:34
 * update_at: 2026-10-06 18:34
 */

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 30;          // N < 29
const char IMPOSSIBLE[] = "Oh,it's impossible~!!";

int n;                        // 开关数量
ll row[MAXN];                 // 第 j 行：低 n 位为系数，第 n 位为右端常数

// 读入一组数据并构建 n 个 GF(2) 方程
void build_equations() {
    static int st[MAXN], ed[MAXN];
    for (int i = 0; i < n; ++i) scanf("%d", &st[i]);
    for (int i = 0; i < n; ++i) scanf("%d", &ed[i]);

    for (int j = 0; j < n; ++j) row[j] = 0;

    int i, j;
    while (scanf("%d%d", &i, &j) == 2 && (i || j)) {
        // 操作第 i 个开关会翻转第 j 个开关：变量 x_i 进入第 j 行
        row[j - 1] ^= 1LL << (i - 1);
    }

    // 自环：操作第 j 个开关必定翻转第 j 个开关
    for (int j = 0; j < n; ++j) row[j] |= 1LL << j;

    // 右端常数：第 j 位是否需要翻转
    for (int j = 0; j < n; ++j) row[j] ^= (ll)(st[j] ^ ed[j]) << n;
}

// 高斯消元求自由元个数；返回 -1 表示出现 0 = 1 的矛盾行
int free_variables() {
    int rank = 0;
    for (int col = 0; col < n; ++col) {
        int pivot = -1;
        for (int k = rank; k < n; ++k) {
            if (row[k] >> col & 1LL) {
                pivot = k;
                break;
            }
        }
        if (pivot < 0) continue; // 无主元，该列自由

        swap(row[rank], row[pivot]);
        for (int k = 0; k < n; ++k) {
            if (k != rank && (row[k] >> col & 1LL)) row[k] ^= row[rank];
        }
        ++rank;
    }

    // 检查只剩常数位的矛盾行 0 = 1
    for (int k = 0; k < n; ++k) {
        if (row[k] == (1LL << n)) return -1;
    }
    return n - rank;
}

int main() {
    int K;
    scanf("%d", &K);
    while (K--) {
        scanf("%d", &n);
        build_equations();
        int free_cnt = free_variables();
        if (free_cnt < 0) {
            printf("%s\n", IMPOSSIBLE);
        } else {
            printf("%lld\n", 1LL << free_cnt);
        }
    }
    return 0;
}

复杂度

设单组 $N\leqslant 28$、边数 $M$。建方程 $O(N+M)$，高斯消元 $O(N^2)$（每列扫一遍主元， 最坏对每行做一次整数异或），总时间 $O\bigl(K(N+M+N^2)\bigr)$；空间 $O(N)$ 个整数。 相比朴素枚举的 $O\bigl(K\cdot 2^N N^2\bigr)$，指数部分被完全消除。

实测：真实数据 0.017 s / 峰值 14.7 MB；构造的最坏情形（$K=1000$、每组 $N=28$、边表拉满 $28\times27=756$ 条）用时 0.12 s，离 1000 ms 与 128 MB 都有充足余量。

总结

本题的全部难度在建模，不在写代码：

1. 「每个开关最多按一次」+「顺序无关」⇒ 一个方法就是一个 $0/1$ 向量 $x$；
2. 第 $j$ 位的最终状态只由一组 $x_i$ 的异或和决定 ⇒ $N$ 条 GF(2) 线性方程；
3. 解集的规模只由秩决定 ⇒ 答案 $=2^{\,N-r}$，出现 $0=1$ 即无解。

有了这三步，「枚举 $2^N$ 个操作集合」就被换成「求 $N\leqslant 28$ 行的矩阵的秩」， 而位压缩让每行的 $N$ 个系数变成一个整数，一次异或抵消一整行。 最需要留心的是 I J 是有向的：方程按位置编号，变量 $i$ 进入第 $j$ 行， 再加上自环 $a_{j,j}=1$ 与常数位。

图示解析

这张图串起本题从读题到得到答案的主线：

1
2
3
4
5
6
7
8
9输入：初始/目标状态 + 有向边 I J
|- 每个开关最多按一次, 顺序无关
|  `- 一个方法 = 0/1 向量 x
`- 第 j 位最终状态 = 影响 j 的 x_i 的异或和
   `- N 条 GF(2) 方程: 行 j 的系数 = {i : i 影响 j} + 自环 j
      `- 整行压成一个整数 (低 N 位系数, 第 N 位常数)
         `- 高斯消元求秩 r, 并检查是否出现 0 = 1
            |- 有 0 = 1      -> Oh,it's impossible~!!
            `- 无矛盾        -> 答案 = 2^(N - r)

从上往下看这条链：先由读题得到「一个方法是一个 $0/1$ 向量」，再把「每个位置达到目标」 翻译成一行方程，接着把整行压成一个整数以便一次异或消去一整行，最后只剩两种出口—— 出现 $0=1$ 说明无解，否则自由元个数 $N-r$ 决定解数。图中每一步都对应正文已经证明过的结论， 不替代 ### 思路 里的样例推演。