#155. Tutte 多项式

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: negiizhao

题目描述

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

对于一个无向图 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 染色的数量。
  • x=0 时有 C_G(k)=(-1)^{|E|-|V|+k(E)}T_G(0, 1-k) C_G(k) 表示 G 流多项式,是 G 的无处为零 k -流的数量。

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

输入格式

1 行: n

2+i 行( 0 \leq i \leq n−1 ): G_{i, 0}\ G_{i, 1}\ \ldots 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) 对应的输出。

样例输出

(x, y) T_G(x, y) \bmod 998244353
(0, 1) 6
(0, 2) 24
(1, 0) 10
(1, 1) 24
(1, 2) 52
(2, 0) 60
(2, 1) 86

数据范围与提示

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

子任务

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