1008. FWT

题目描述

现在有 $n$ 个数字，其中 $\forall i\in[1, n]，x_1 \And x_i = x_i, x_i\And x_n = x_n$。

现在再给定 $m$ 个条件 $a, b$，表示 $x_a \And x_b = x_b$。

现在在给定两个整数 $l, r$，所有 $x$ 在 $[l, r]$ 范围内。现在想求合法 $x$ 数量。

现在很善变，他会多次询问，每次反转 $l$ 或者 $r$ 的某一位，他想在每次修改后再次得到答案。

现在是谁。

输入格式

第一行输入一个正整数 $T（1\le T\le 5）$，表示数据组数。

对于每组数据，数据第一行三个正整数 $n, m, t（3\le n\le 20, 0\le m\le （n-2）\times（n-3）, 1\le t\le 10^5）$。

接下来 $m$ 组 $（a, b）$。

接下来两行，每行一个正整数，分别表示 $l,r（1\le l\le r\le 2^{100000}）$ 的二进制形式，

接下来 $t$ 行，给出 $op, i$，$op=0$ 时表示反转 $l$ 的二进制从左到右第 $i$ 位（最高位为第一位）；$op=1$ 时反转 $r$.

输出格式

每组数据输出 $t+1$ 行，第一行输出没有修改时候的答案，接下来 $t$ 行分别输出每次修改后的答案。答案对 998244353 取模。

样例输入

1
3 1 2
1 2
10
110
0 1
1 2

样例输出

13
37
19

提示

对于样例，在没有修改的情况下，所有的合法对是（2,2,2）,（3,2,2）,（3,3,2）,（3,3,3）,（4,4,4）, （5,4,4）, （5,5,4）,（5,5,5）, （6,2,2）, （6,4,4）, （6,6,2）, （6,6,4）, （6,6,6）。

来源：2026杭电多校-测试专用（四川大学） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1231&pid=1008