1652_Tutte多项式

这是一道模板题。

对于一个无向图 G =(V, E) ，Tutte多项式可以定义为 ，其中 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)表示 G 的色多项式，是 G 的顶点 k染色的数量。特别地，TG(2,0) 是 G 的无环定向数量。

• x = 0 时有 ，C_G(k)表示 G 的流多项式，是 G 的无处为零 k-流的数量。特别地，T_G(0,2) 是 G 的强连通定向数量。

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

第 1 行：n

第 2+i 行（ 0 ≤ i ≤ n-1 ）： G_i,0  G_i,1 ... G_i,n-1 ，G_i,j 为 0 表示 (i,j)E ，为 1 表示 (i,j)∈E

第 2+n 行：x  y

第  1 行：T_G(x,y) mod 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)          TG(x,y) mod 998244353
(0,1)        6
(0,2)        24
(1,0)        10
(1,1)        24
(1,2)        52
(2,0)        60
(2,1)        86

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