题目详情题解（0）讨论（0）提交记录（0）

AT_abc262_e.[ABC262E] Red and Blue Graph

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 NN 个顶点、MM 条边的简单无向图。顶点编号为 1,2,…,N1, 2, \dots, N，第 ii 条边连接顶点 UiU_i 和 ViV_i。

将每个顶点涂成红色或蓝色的方法共有 2N2^N 种。在这些方法中，满足以下所有条件的方法数，模 998244353998244353 后的余数是多少？

  • 恰好有 KK 个顶点被涂成红色。
  • 连接颜色不同顶点的边的数量为偶数。

输入格式

输入以如下格式从标准输入给出。

NN MM KK
U1U_1 V1V_1
⋮\vdots
UMU_M VMV_M

输出格式

输出答案。

输入输出样例

  • 输入#1

    4 4 2
1 2
1 3
2 3
3 4

    输出#1

    2

  • 输入#2

    10 10 3
1 2
2 4
1 5
3 6
3 9
4 10
7 8
9 10
5 9
3 4

    输出#2

    64

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 0≤K≤N0 \leq K \leq N
  • 1≤Ui<Vi≤N(1≤i≤M)1 \leq U_i < V_i \leq N \quad (1 \leq i \leq M)
  • (Ui,Vi)≠(Uj,Vj)(i≠j)(U_i, V_i) \neq (U_j, V_j) \quad (i \neq j)
  • 输入均为整数

样例解释 1

以下 22 种方案满足条件：

  • 将顶点 1,21, 2 涂成红色，顶点 3,43, 4 涂成蓝色。
  • 将顶点 3,43, 4 涂成红色，顶点 1,21, 2 涂成蓝色。

对于上述涂色方法，连接颜色不同顶点的边是第 22 条和第 33 条边。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页