开关问题

Luogu

IDLGP10499

Time1000ms

Memory512MB

DifficultyP5

高斯消元

有 $N$ 个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后 $N$ 个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序） ## Input 输入第一行有一个数 $K$，表示以下有 $K$ 组测试数据。每组测试数据的格式如下：第一行：一个数 $N$。第二行：$N$ 个 $0$ 或者 $1$ 的数，表示开始时 $N$ 个开关状态。第三行：$N$ 个 $0$ 或者 $1$ 的数，表示操作结束后 $N$ 个开关的状态。接下来每行两个数 $I,J$，表示如果操作第 $I$ 个开关，第 $J$ 个开关的状态也会变化。每组数据以 `0 0` 结束。 ## Output 每组数据输出占一行。如果有可行方法，输出总数，否则输出 `Oh,it's impossible~!!` 。 [samples] ## Note 对于所有测试数据，满足 $1 \le K \le 10$，$0 < N < 29$。

Samples

Input #1

Output #1

4
Oh,it's impossible~!!

API Response (JSON)

{
  "problem": {
    "name": "开关问题",
    "description": {
      "content": "有 $N$ 个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。 你的目标是经过若干次开关操作后使得最后 $N$ 个开关达到一个特定的状态。 对于任意一个开关，最多只能进行一次开关操作。 你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10499"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $N$ 个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。\n\n你的目标是经过若干次开关操作后使得最后 $N$ 个开关达到一个特定的状态。\n\n对于任意一个开关，最多只能进行一次开关操作。\n\n你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments