【题目链接】

• 点击打开链接

【思路要点】

• 值域连续的区间的交和并均为值域连续的区间，因此一个合法输入应当能够构成一个树形结构。
• 考虑一个节点的子树，其对应的区间值域连续，且在后续的考虑中，我们会避免使其出现在更大的连续区间中，因此我们可以等效地将其看做一个数。
• 因此，记 f i f_i fi​ 表示长度为 i + 1 i+1 i+1 的，去掉最后一个元素后不存在非平凡连续区间的排列个数， s i s_i si​ 表示 i i i 的子节点个数，应当有
  A n s = ∏ i = 1 N f s i Ans=\prod_{i=1}^{N} f_{s_i} Ans=i=1∏N​fsi​​
• 关于 f i f_i fi​ 的计算有如下递推式 f 0 = 1 , f 1 = 2 , f i = ( i − 1 ) f i − 1 + ∑ j = 2 i − 2 ( j − 1 ) f j f i − j ( i ≥ 2 ) f_0=1,f_1=2,f_i=(i-1)f_{i-1}+\sum_{j=2}^{i-2}(j-1)f_jf_{i-j}\ (i\geq 2) f0​=1,f1​=2,fi​=(i−1)fi−1​+j=2∑i−2​(j−1)fj​fi−j​ (i≥2)
• 该递推式的证明：
  对于一个满足去掉最后一个元素后不存在非平凡连续区间的排列 a i a_i ai​ ，定义 b a i = i b_{a_i}=i bai​​=i ，那么 b i b_i bi​ 是一个不存在不包含最大值的非平凡连续区间的排列，且 a i a_i ai​ 和 b i b_i bi​ 一一对应，因此 f i f_i fi​ 同样也是长度为 i + 1 i+1 i+1 的，不存在不包含最大值的非平凡连续区间的排列，也即不存在不包含最小值的非平凡连续区间的排列，考虑删去序列的最小值。
  1 1 1 、序列仍然满足不存在不包含最小值的非平凡连续区间。
  那么可以看做是在这样的序列中插入了最小值，且不与次小值相邻，共有 i + 1 − 2 = i − 1 i+1-2=i-1 i+1−2=i−1 个插入位置，对 f i f_i fi​ 的贡献为 ( i − 1 ) f i − 1 (i-1)f_{i-1} (i−1)fi−1​ 。
  2 2 2 、序列不满足不存在不包含最小值的非平凡连续区间。
  枚举其中不包含最小值的非平凡连续区间的最大长度 j ( j ∈ [ 2 , i − 2 ] ) j\ (j\in[2,i-2]) j (j∈[2,i−2]) ，其值域 [ x , x + j − 1 ] [x,x+j-1] [x,x+j−1] 应当不包含最小值 2 2 2 ，即 x ∈ [ 3 , i + 1 − j ] x\in[3,i+1-j] x∈[3,i+1−j] ，共 i − 1 − j i-1-j i−1−j 种取值。插入最小值 1 1 1 后，该区间不再存在不包含最小值的非平凡连续区间，且全局亦是如此，因此可行的排列数为 f j f i − j f_jf_{i-j} fj​fi−j​ ，对 f i f_i fi​ 的贡献为 ∑ j = 2 i − 2 ( i − j − 1 ) f j f i − j = ∑ j = 2 i − 2 ( j − 1 ) f j f i − j \sum_{j=2}^{i-2}(i-j-1)f_jf_{i-j}=\sum_{j=2}^{i-2}(j-1)f_jf_{i-j} ∑j=2i−2​(i−j−1)fj​fi−j​=∑j=2i−2​(j−1)fj​fi−j​ 。
• 分治 F F T FFT FFT 计算 f i f_i fi​ 即可。
• 时间复杂度 O ( N L o g 2 N + T × N ) O(NLog^2N+T\times N) O(NLog2N+T×N) 。

【代码】

#include<bits/stdc++.h>using namespace std;const int MAXN = 262144;const int P = 998244353;typedef long long ll;typedef long double ld;typedef unsigned long long ull;template <typename T> void chkmax(T &x, T y) {x = max(x, y); }template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) {x = 0; int f = 1;char c = getchar();for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';x *= f;}template <typename T> void write(T x) {if (x < 0) x = -x, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}template <typename T> void writeln(T x) {write(x);puts("");}namespace NTT {const int MAXN = 262144;const int P = 998244353;const int G = 3;int power(int x, int y) {if (y == 0) return 1;int tmp = power(x, y / 2);if (y % 2 == 0) return 1ll * tmp * tmp % P;else return 1ll * tmp * tmp % P * x % P;}int N, Log, home[MAXN];int forward[25], bckward[25], inv[25];void NTTinit() {for (int i = 0; i < N; i++) {int ans = 0, tmp = i;for (int j = 1; j <= Log; j++) {ans <<= 1;ans += tmp & 1;tmp >>= 1;}home[i] = ans;}}void preinit() {forward[0] = bckward[0] = inv[0] = 1;for (int len = 2, lg = 1; len <= MAXN; len <<= 1, lg++) {forward[lg] = power(G, (P - 1) / len);bckward[lg] = power(G, P - 1 - (P - 1) / len);inv[lg] = power(len, P - 2);}}void NTT(int *a, int mode) {for (int i = 0; i < N; i++)if (home[i] < i) swap(a[i], a[home[i]]);for (int len = 2, lg = 1; len <= N; len <<= 1, lg++) {int delta;if (mode == 1) delta = forward[lg];else delta = bckward[lg];for (int i = 0; i < N; i += len) {int now = 1;for (int j = i, k = i + len / 2; k < i + len; j++, k++) {int tmp = a[j];int tnp = 1ll * a[k] * now % P;a[j] = (tmp + tnp) % P;a[k] = (tmp - tnp + P) % P;now = 1ll * now * delta % P;}}}if (mode == -1) {for (int i = 0; i < N; i++)a[i] = 1ll * a[i] * inv[Log] % P;}}void times(int *a, int *b, int *c, int sa, int sb) {N = 1, Log = 0;while (N <= sa + sb) {N <<= 1;Log++;}for (int i = sa + 1; i < N; i++)a[i] = 0;for (int i = sb + 1; i < N; i++)b[i] = 0;NTTinit();NTT(a, 1);NTT(b, 1);for (int i = 0; i < N; i++)c[i] = 1ll * a[i] * b[i] % P;NTT(c, -1);}}int n, ans, a[MAXN], f[MAXN], g[MAXN], h[MAXN];void update(int &x, int y) {x += y;if (x >= P) x -= P;}void work(int l, int r) {if (l == r) {update(f[l], 1ll * f[l - 1] * (l - 1) % P);if (l >= 2) {g[l] = 1ll * f[l] * (l - 1) % P;h[l] = f[l];}return;}int mid = (l + r) / 2;int len = r - l, lft = mid - l;static int tmp[MAXN], tnp[MAXN], res[MAXN];work(l, mid);if (l == 1) {for (int i = l; i <= mid; i++) {tmp[i - l] = g[i];tnp[i - l] = h[i];}NTT :: times(tmp, tnp, res, lft, lft);for (int i = mid + 1; i <= r; i++)update(f[i], res[i - 2 * l]);} else {for (int i = l; i <= mid; i++)tmp[i - l] = g[i];tnp[0] = 0;for (int i = 1; i <= len; i++)tnp[i] = h[i];NTT :: times(tmp, tnp, res, lft, len);for (int i = mid + 1; i <= r; i++)update(f[i], res[i - l]);for (int i = l; i <= mid; i++)tmp[i - l] = h[i];tnp[0] = 0;for (int i = 1; i <= len; i++)tnp[i] = g[i];NTT :: times(tmp, tnp, res, lft, len);for (int i = mid + 1; i <= r; i++)update(f[i], res[i - l]);}work(mid + 1, r);}void getans(int l, int r) {if (a[r] != r - l + 1) {ans = 0;return;}int cnt = 0, pos = r - 1;while (pos >= l) {if (pos - a[pos] + 1 < l) {ans = 0;return;}getans(pos - a[pos] + 1, pos);cnt++, pos -= a[pos];}ans = 1ll * ans * f[cnt] % P;}int main() {int T; read(T), read(n);NTT :: preinit();f[0] = 1, f[1] = 2;work(1, n);while (T--) {for (int i = 1; i <= n; i++)read(a[i]);ans = 1;getans(1, n);writeln(ans);}return 0;}