4273. [THUPC 2025 pre] 乒乓球赛

【题目描述】

Menji 喜欢看乒乓球比赛，但由于观赛的人太多，他只能听到一部分的信息。

乒乓球赛一共包含 $T$ 局，一局乒乓球的过程如下：

两位选手分别有得分，用 $s_A$ 和 $s_B$ 表示，初始 $s_A=s_B=0$。

接下来会进行若干个回合，在第 $i$ 个回合，会有一个获胜者 $win_i(win_i\in\{\text{A},\text{B}\})$，若 $win_i=\text{A}$ 则 $A$ 的得分 $+1$，即 $s_A=s_A+1$，否则 $B$ 的得分 $+1$，即 $s_B=s_B+1$。当任意一名选手达到 $11$ 分，且领先另一名选手至少 $2$ 分时（即 $\max(s_A,s_B)\geq 11$, $\max(s_A,s_B)-\min(s_A,s_B)\geq 2$），该局立刻结束。

对于每一局比赛，Menji 听到了最终该局进行的回合数 $n$，以及一部分时刻结束时的比分，例如 Menji 可能在第 $5$ 回合结束时听到比分是 $3:2$，但 Menji 并不知道哪一名选手获得了 $3$ 分，只知道其中一名选手获得了 $3$ 分，另外一名选手获得了 $2$ 分。

具体的，Menji 的信息可以被表示为一个非负整数 $n$，表示该局恰好进行了 $n$ 个回合，以及 $2$ 个长为 $n$ 的序列 $a_1\cdots a_n,b_1\cdots b_n$。对于每一个 $i(1\leq i\leq n)$，若 $a_i=b_i=-1$，则 Menji 没有听到任何第 $i$ 个回合结束时的信息，否则保证 $0\leq a_i,b_i\leq n$，表示在第 $i$ 个回合结束时，一定满足 $s_A=a_i,s_B=b_i$ 或 $s_A=b_i,s_B=a_i$。

显然，很多时候 Menji 的信息并不能还原比赛每一局每一回合的获胜者，甚至有时候 Menji 的信息会是错误的。Menji 想要知道，有多少个获胜者序列 $win_1\cdots win_n$ 满足他已知的所有信息？

由于答案可能很大，请输出答案对 $998244353$ 取模的结果。

【输入格式】

第一行一个整数 $T(1\leq T\leq 10^5)$，表示乒乓球比赛的局数。

对于每一局：

第一行一个整数 $n$，表示比赛恰好进行了 $n(1\leq n\leq 10^5)$ 回合。

之后 $n$ 行，每行两个整数 $a_i,b_i$，满足 $a_i=b_i=-1$ 或 $0\leq a_i,b_i\leq n$，表示 Menji 已知的一部分信息。

保证总回合数不超过 $5\times 10^5$，即 $\sum n\leq 5\times 10^5$。

【输出格式】

对于每一局，输出一行一个数，表示可能的获胜者序列个数，对 $998244353$ 取模。

【样例输入】

7
11
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11
-1 -1
1 1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 11
22
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11 9
-1 -1
-1 -1
22
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
23
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
22
-1 -1
1 1
-1 -1
3 1
-1 -1
4 2
-1 -1
2 6
-1 -1
-1 -1
5 6
-1 -1
-1 -1
7 7
-1 -1
-1 -1
9 8
-1 -1
9 10
-1 -1
11 10
-1 -1

【样例输出】

2
0
0
0
369512
0
864

【样例解释】

比赛总共进行了 $6$ 局。

• 对于第一局，恰好进行了 $11$ 个回合结束，一定是某一选手连胜了 $11$ 回合，所以获胜者序列一定是全 $\text{A}$ 或是全 $\text{B}$，故答案为 $2$。
• 对于第二局，恰好进行了 $11$ 个回合结束，但第二回合结束的比分是 $1:1$，最终至多只能达到 $10:1$ 的比分，因此不存在合法的获胜者序列使得恰好 $11$ 回合结束，故答案为 $0$。
• 对于第三局，显然不可能在 $11$ 个回合内达到 $1:11$ 的比分，故答案为 $0$。
• 对于第四局，若第 $20$ 个回合的比分达到 $11:9$，则该局会立刻结束，不会进行到第 $22$ 个回合，故答案为 $0$。
• 对于第五局，双方的得分一定是先达到 $10:10$，之后其中一名选手连胜 $2$ 局，故答案为 ${20 \choose 10}\times 2 = 369512$。
• 对于第六局，容易发现不可能恰好进行 $23$ 个回合时结束，故答案为 $0$。
• 对于第七局，我有一个完美的解释，可惜写不下了。

【来源】

清华大学学生算法协会 GitLink 仓库