[PA 2024] Żarówki

Luogu

IDLGP10367

Time3000ms

Memory1024MB

DifficultyP6

数学图论2024图论建模二分图组合数学PA（波兰）

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Żarówki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zar/)，感谢 Macaronlin 提供翻译** 有 $n$ 个灯泡，每个灯泡有两种状态：开和关，初始状态是给定的。有 $m$ 个开关，每个开关控制两个灯泡，按下开关可以使这两个灯泡变为与目前状态相反的状态，只有在两个灯泡有相同状态时才起作用，否则不起作用。你可以随意安排开关的使用顺序和使用次数，问利用这些开关可以实现多少种配置方案。灯泡在一种配置中打开而在另一种配置中关闭，则两种配置被视为不同。 ## Input 第一行两个整数 $n$ 和 $m\ (1\le n\le 200\,000,0\le m\le 400\,000)$，表示灯泡和开关的个数。第二行 $n$ 个整数 $c_i\ (c_i\in \{0,1\})$，如果 $c_i=1$，则初始时第 $i$ 个灯泡是打开的，如果 $c_i=0$，则初始时第 $i$ 个灯泡是关闭的。接下来 $m$ 行，每行两个整数 $a_i,b_i\ (1\le a_i,b_i\le n,a_i\neq b_i)$，描述一个开关。保证开关会影响不同的无序灯泡对。形式化地，$\forall i,j \in \{1,2,\ldots,m\},i\neq j$，都有 $(a_i,b_i)\neq (a_j,b_j)$ 且 $(a_i,b_i)\neq (b_j,a_j)$。 ## Output 输出一行一个整数，表示利用这些开关可以实现多少种配置方案。输出对 $10^9+7$ 取模。 [samples] ## Background PA 2024 5C2 ## Note 所有可以实现的配置方案为：`10110`，`00010`，`00111` 和 `10011`。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[PA 2024] Żarówki",
    "description": {
      "content": "**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Żarówki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zar/)，感谢 Macaronlin 提供翻译** 有 $n$ 个灯泡，每个灯泡有两种状态：开和关，初始状态是给定的。有 $m$ 个开关，每个开关",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10367"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Żarówki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zar/)，感谢 Macaronlin 提供翻译**\n\n有 $n$ 个灯泡，每个灯泡有两种状态：开和关，初始状态是给定的。有 $m$ 个开关，每个开关...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments