#P9655. Giant Graph

    ID: 6278 传统题 2000ms 512MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>难度分类省选/NOI-图论最大权独立集博弈论SG 函数mex 计算异或合并动态规划线性 DP滚动数组模拟与实现技巧时间戳避免清空数组CF2600

Giant Graph

题目描述

kk 维生物居住在 kk 维空间里的一张点数为 nkn^k 的无向图 GG 上,GG 的顶点用 x=(x1,x2,⋯ ,xk)\textbf{x}=(x_1,x_2,\cdots,x_k) 表示,其中 xi∈[1,n]∩Zx_i\in [1, n] \cap \mathbb{Z}。

同时给定 kk 张无向图,图从 11 到 kk 编号,其中图 Gi=({1,2,⋯ ,n},Ei)G_i=(\{1,2,\cdots,n\},E_i),∣Ei∣=mi|E_i|=m_i。

对于图 GG 的两个不同的顶点 x\textbf{x} 和 y\textbf{y},两者有边当且仅当两者恰好只有第 ii 维的分量 xix_i 和 yiy_i 不同,且满足 (xi,yi)∈Ei(x_i,y_i)\in E_i。

kk 维生物喜欢做游戏,游戏是和独立集有关的。现在他们想和你做游戏:假设图 GG 中顶点 x\textbf{x} 的 点权为 V∑i=1kxiV^{\sum_{i=1}^kx_i},其中 VV 比你能想象到的最大的数还要大,求这张图最大权独立集的权值,答案对 998244353998244353 取模。

输入格式

第一行三个整数 n,k,vn,k,v,含义与题面一致,其中 vv 表示为 V mod 998244353V \bmod 998244353 的值。

接下来按顺序依次给定 kk 张无向图,每张图按如下方式给出:首先给出 mim_i,表示 GiG_i 的边集大小,之后的 mim_i 行中,第 jj 行有两个正整数 uj,vju_j,v_j,表示 GiG_i 的一条无向边 (uj,vj)(u_j,v_j)。

输出格式

输出一个整数,表示图 GG 最大权独立集的权值对 998244353998244353 取模后的值。

样例

2 3 1
1
1 2
1
1 2
1
1 2
4

最大权独立集为 {(2,1,1),(1,2,1),(1,1,2),(2,2,2)}\{(2, 1, 1),(1, 2, 1),(1, 1, 2),(2, 2, 2)\}。

5 1 2
4
4 2
3 5
1 3
3 4
50
10 5 402600065
0
0
0
0
0
416675831

下载样例 4 输入;下载样例 4 输出。

数据范围

对于所有数据,1≤n≤1051\le n \le 10^5,1≤k≤51 \le k \le 5,1≤v≤9982443521 \le v \le 998244352,保证:

  • 0≤mi≤min⁡((n2),105)0 \le m_i \le \min(\binom{n}{2},10^5);

  • 1≤uj,vj≤n1 \le u_j,v_j \le n;

  • 给定的图 GiG_i 无重边无自环,不保证联通。

本版保留现行 Hydro 评分:全部测试点共 100 分,统一按以上全局范围评测。