luogu#P9493. 「SFCOI-3」进行一个列的排

    ID: 13464 远端评测题 1500ms 128MiB 尝试: 4 已通过: 2 难度: 5 上传者: 标签>动态规划,dp2023洛谷原创O2优化区间 dp

「SFCOI-3」进行一个列的排

题目背景

(其实这题原来叫 I must say No,不过出于某些显然的原因就改题目名了 /kk)

You must say Yes.

(题目背景图片来自 Phigros 曲绘,如有侵权,请告知出题人。)

题目描述

小 R 有一个长度为 nn 的排列 p1pnp_1\dots p_n。换句话说,p1pnp_1\dots p_n 包含 0(n1)0 \sim (n - 1) 之间的数,并且满足对于 0(n1)0 \sim (n - 1)nn 个数,每个数在 pp 中出现且仅出现一次。

小 R 有 nn 个限制,其中第 i(0in1)i(0 \leq i \leq n - 1) 个用一个正整数 LiL_i 描述,表示至少有一个长度为 LiL_i 的区间 [l,r][l, r](即 rl+1=Lir - l + 1 = L_i)满足 mexk=lrpk=i\operatorname{mex}_{k=l}^r p_k = i

小 R 丢失了排列 p1pnp_1\dots p_n,不过幸运的是她仍然记得这 nn 条限制。请你帮她求出总共有多少个初始的合法排列,答案对 998244353998244353 取模。

输入格式

本题每个测试点有多组数据。

第一行一个整数 TT 表示数据组数。对于每组数据:

  • 第一行一个整数 nn
  • 第二行 nn 个整数依次表示 L0Ln1L_0\dots L_{n-1}

输出格式

TT 行,每行一个整数表示答案。

4
4
1 1 3 3
5
2 1 3 3 4
6
1 1 2 5 4 5
10
3 2 3 4 7 6 8 8 8 9
4
12
8
96

提示

定义

  • 一个序列的 mex\operatorname{mex} 是其中没有出现过的最小非负整数,如 mex{1,3,4}=0\operatorname{mex}\{1, 3, 4\} = 0mex{0,1,1,2,5}=3\operatorname{mex}\{0, 1, 1, 2, 5\} = 3mex{3,1,0,2}=4\operatorname{mex}\{3, 1, 0, 2\} = 4

数据规模与约定

  • Subtask 0(10 pts):n10n \leq 10
  • Subtask 1(30 pts):n18n \leq 18
  • Subtask 2(15 pts):n300n \leq 300
  • Subtask 3(45 pts):无特殊限制。

对于所有数据,1T101 \leq T \leq 101n5×1031 \leq n \leq 5 \times 10^31Lin1 \leq L_i \leq n