← 返回题目列表

Codeforces · 2061/C

C. 凯文和谜题

中文机器翻译题面 查看原题

凯文喜欢逻辑谜题。

他和 $$$n$$$ 排成一排的同学玩游戏。左边第 $$$i$$$ 人说他们左边有 $$$a_i$$$ 骗子(不包括他们自己)。

每个同学要么是诚实的,要么是说谎的,但限制是不能有两个说谎的人并排站立。诚实的同学总是说实话。说谎者可以说真话,也可以说谎话,这意味着他们的陈述被认为是不可靠的。

Kevin 想要确定以 $$$998\,244\,353$$$ 为模的不同可能游戏配置的数量。如果至少一名同学在一种配置中是诚实的,而在另一种配置中是骗子,则两种配置被认为是不同的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n \leq 2 \cdot 10^5$$$) — 同学的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i \leq n$$$) — 他们声称的第 $$$i$$$ 人左边的骗子数量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 不同游戏配置的数量以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

8
3
0 1 2
5
0 0 0 0 0
5
0 0 1 1 2
5
0 1 2 3 4
5
0 0 1 1 1
5
5 1 5 2 5
1
0
4
2 3 1 1

输出 #1

1
2
3
0
4
1
2
0

注意

我们将使用 $$$\color{red}{\text{red}}$$$ 来标记说谎者,使用 $$$\color{blue}{\text{blue}}$$$ 来标记诚实的人。

在第一个测试用例中,唯一可能的方法是 $$$(\color{red}{0},\color{blue}{1},\color{red}{2})$$$。

在第二个测试用例中,两种可能的方式是 $$$(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0})$$$ 和 $$$(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{red}{0})$$$。

在第三个测试用例中,三种可能的方式是 $$$(\color{blue}{0},\color{blue}{0},\color{red}{1},\color{blue}{1},\color{red}{2})$$$, $$$(\color{blue}{0},\color{red}{0},\color{blue}{1},\color{red}{1},\color{blue}{2})$$$, $$$(\颜色{蓝色}{0}、\颜色{红色}{0}、\颜色{蓝色}{1}、\颜色{蓝色}{1}、\颜色{红色}{2})$$$。