[AdditionalFile155.zip](file://AdditionalFile155.zip?type=additional_file)

#155. Tutte 多项式

标签: 传统 | 时间限制: 10000 ms | 内存限制: 1024 MiB | 显示标签 通过: 73 | 提交: 144

题目描述

这是一道（集合幂级数对数和指数、所有点子集生成树计数以及一些其他东西的）模板题。

对于一个无向图 $G = (V, E)$，Tutte 多项式可以定义为 $T_G(x, y) = \sum_{A \subseteq E} (x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|}$，其中 $k(E)$ 表示图 $(V, E)$ 的连通分量数。它还有一些看起来更简洁自然的定义和很多优秀的性质，但在这题只需要知道这个定义。

在一些 $(x, y)$ 上，Tutte 多项式和一些计数问题相关。一个图的 Tutte 多项式等于它的所有连通分量的 Tutte 多项式之积，为了方便，以下假设图 $G$ 连通。

• 容易观察到 $T_G(1, 1)$ 是 $G$ 的生成树（即无环连通生成子图）数量，$T_G(2, 1)$ 是 $G$ 的生成森林（即无环生成子图）数量，$T_G(1, 2)$ 为 $G$ 的连通生成子图数量，$T_G(2, 2)$ 是 $G$ 的生成子图数量，即 $2^{|E|}$。
• $y=0$ 时有 $P_G(k) = (-1)^{|V|-k(E)}k^{k(E)}T_G(1-k, 0)$，$P_G(k)$ 表示 $G$ 的色多项式，是 $G$ 的顶点 $k$ 染色的数量。
  • 特别地，$T_G(2, 0)$ 是 $G$ 的无环定向数量。
• $x=0$ 时有 $C_G(k) = (-1)^{|E|-|V|+k(E)}T_G(0, 1-k)$，$C_G(k)$ 表示 $G$ 的流多项式，是 $G$ 的无处为零 $k$-流的数量。
  • 特别地，$T_G(0, 2)$ 是 $G$ 的强连通定向数量。

对一个无重边无自环的图 $G = (\{0, 1, \dots, n-1\}, E)$，求 $T_G(x, y) \bmod 998244353$。

输入格式

第 1 行：$n$

第 $2 + i$ 行 ($0 \le i \le n - 1$)：$G_{i,0}\ G_{i,1}\ \dots\ G_{i,n-1}$，$G_{i,j}$ 为 0 表示 $(i,j) \notin E$，为 1 表示 $(i,j) \in E$

第 $2 + n$ 行：$x\ y$

输出格式

第 1 行：$T_G(x, y) \bmod 998244353$

样例

样例输入

5
0 1 1 0 1
1 0 0 1 1
1 0 0 1 1
0 1 1 0 0
1 1 1 0 0
[x] [y]

[x] 和 [y] 是输入的 $x$ 和 $y$，样例输出中给出了一些可能的 $(x, y)$ 对应的输出。

样例输出

数据范围与提示

• $1 \le n \le 21$
• $G_{i,j} \in \{0, 1\}, G_{i,j} = G_{j,i}, G_{i,i} = 0$
• $0 \le x, y < 998244353$

子任务

1. (16 分) $n \le 7$
2. (20 分) $n \le 11$
3. (14 分) $n \le 14$
4. (25 分) $n \le 18$
5. (25 分) 没有附加限制