#84. Tutte 多项式

Tutte 多项式

当前没有测试数据。

题目描述

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

对于一个无向图 G=(V,E)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)k(E) 表示图 (V,E)(V, E) 的连通分量数。它还有一些看起来更简洁自然的定义和很多优秀的性质,但在这题只需要知道这个定义。

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

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

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

输入格式

11 行:nn

2+i2+i 行(0in10 \leq i \leq n−1):Gi,0 Gi,1 Gi,n1G_{i, 0}\ G_{i, 1}\ \ldots G_{i, n-1}Gi,jG_{i, j}00 表示 (i,j)E(i, j) \notin E ,为 11 表示 (i,j)E(i, j) \in E

2+n2+n 行:x yx\ y

输出格式

11 行:TG(x,y)mod998244353T_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] 是输入的 xxyy,样例输出中给出了一些可能的 (x,y)(x, y) 对应的输出。

样例输出

(x,y)(x, y) TG(x,y)mod998244353T_G(x, y) \bmod 998244353
(0,1)(0, 1) 66
(0,2)(0, 2) 2424
(1,0)(1, 0) 1010
(1,1)(1, 1) 2424
(1,2)(1, 2) 5252
(2,0)(2, 0) 6060
(2,1)(2, 1) 8686

数据范围与提示

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

子任务

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