CF2170E Binary Strings and Blocks

定义二进制串（仅由字符 $0$ 和/或 $1$ 组成的字符串）中的“块”为：一段由相同字符组成、且无法继续向左或向右扩展的连续子串。例如，在字符串 $110001111$ 中，有三个块： - 11（第 $1$ 位到第 $2$ 位）； - 000（第 $3$ 位到第 $5$ 位）； - 1111（第 $6$ 位到第 $9$ 位）。 例如，第 $7$ 位到第 $9$ 位的 111 不是一个块，因为可以向左扩展；第 $1$ 位到第 $5$ 位的 11000 不是块，因为其中包含了不同的字符。 我们称一个字符串为“美丽的”，如果存在一种方法，删除恰好一个块后，剩余部分的块数为奇数。例如： - 字符串 $110001111$ 是美丽的，因为可以去掉第 $3$ 到第 $5$ 位的块，剩下 $111111$，只有一个块； - 字符串 $1010$ 是美丽的，因为可以去掉第 $1$ 位的块，得到 $010$，共有三个块； - 字符串 $0000$ 不是美丽的，因为唯一能删除的块后字符串为空，块数为 $0$。 现在给定一个整数 $n$ 和 $m$ 个约束条件，第 $i$ 个约束用整数对 $l_i, r_i$ 描述。记字符串 $s$ 的第 $l$ 位到第 $r$ 位为 $s[l:r]$，即 $s[l:r]=s_l s_{l+1} \dots s_r$。你的任务是，统计长度为 $n$ 的二进制串 $s$，满足： - 对于每个 $i$（$1 \le i \le m$），$s[l_i:r_i]$ 是美丽的。

第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试用例个数。 每组测试的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 3 \cdot 10^5$；$1 \le m \le 3 \cdot 10^5$），分别表示字符串长度和约束的数量。 接下来 $m$ 行，每行两个整数 $l_i, r_i$（$1 \le l_i < r_i \le n$），表示第 $i$ 个约束的区间。 额外条件： - 所有测试用例中 $n$ 之和不超过 $3 \cdot 10^5$； - 所有测试用例中 $m$ 之和不超过 $3 \cdot 10^5$。

对每组测试，输出一行一个整数，表示满足要求的字符串数。由于答案可能很大，输出结果对 $998244353$ 取模。

在题目的第一个例子中，满足条件的字符串有：1010 和 0101。对于这两个字符串，$s[1:2]$、$s[2:3]$、$s[3:4]$ 都是美丽的。 由 ChatGPT 5 翻译