3931: Tutte 多项式

这是一道（集合幂级数对数和指数、所有点子集生成树计数以及一些其他东西的）模板题。 对于一个无向图 $G = (V, E)$，[Tutte 多项式](https://en.wikipedia.org/wiki/Tutte_polynomial)可以定义为 $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$ 的[色多项式](https://en.wikipedia.org/wiki/Chromatic_polynomial)，是 $G$ 的顶点 $k$ 染色的数量。 - 特别地，$T_G(2, 0)$ 是 $G$ 的[无环定向](https://en.wikipedia.org/wiki/Acyclic_orientation)数量。 - $x=0$ 时有 $C_G(k)=(-1)^{|E|-|V|+k(E)}T_G(0, 1-k)$，$C_G(k)$ 表示 $G$ 的[流多项式](https://en.wikipedia.org/wiki/Nowhere-zero_flow#Flow_polynomial)，是 $G$ 的无处为零 $k$-流的数量。 - 特别地，$T_G(0, 2)$ 是 $G$ 的[强连通定向](https://en.wikipedia.org/wiki/Strong_orientation)数量。 对一个无重边无自环的图 $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
0 1

6