题目描述
这是一道（集合幂级数对数和指数、所有点子集生成树计数以及一些其他东西的）模板题。
对于一个无向图 $G = (V, E)$，Tutte 多项式可以定义为 $TG(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=(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$
样例
input
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 1output
6
样例输入
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$
子任务
- （16 分）$n \leq 7$
- （20 分）$n \leq 11$
- （14 分）$n \leq 14$
- （25 分）$n \leq 18$
- （25 分）没有附加限制