妙啊！
首先有两个显然的结论：
\(L_n = n\)。
\([i - L_i + 1,i]\) 之间只会互相包含或不交，不会部分相交。
不满足上述两者直接输出 \(0\)。
于是不难发现 \([i - L_i + 1,i]\) 之间的包含关系形成了一个树形结构，根为 \([1,n]\)。
设 \(F(i)\) 表示对于连续区间 \([i-L_i+1,i]\) 内的 \(L\)，安排这一区间内的大小关系的合法方案数（可以视为一个 \(L_i\) 阶排列）。
则答案即 \(F(n)\)。
设 \(f(k)\) 表示满足 \(L_i = 1\ (1 \le i \le k)\) 的 \(k+1\) 阶排列个数。
设 \([i-L_i+1,i]\) 在树上有 \(k\) 个儿子 \(c_1,c_2,\dots,c_k\)，则有 \[
F(n) = f(k) \prod\limits_{i=1}^k F(c_i)
\]
因为这些儿子分别也是极长连续区间，所以若其中的安排顺序使得这些儿子之间按照大小关系形成了连续区间，则这样的连续区间会导致儿子不满足极长，所以儿子之间的顺序应当是 \(f(k)\) 种方案。
设 \(s_i\) 表示 \([i-L_i+1,i]\) 的儿子个数，则由上式不难得出答案即 \[ \prod\limits_{i=1}^n f(s_i) \]
\(s_i\) 可以通过单调栈求出。
那么只需要考虑预处理求出 \(f\) 即可。
给出一个结论：\(f(k)\) 等价于每个长度大于 \(1\) 的连续区间都包含最大值的 \(k+1\) 阶排列个数。
证明可以考虑将 \(f\) 的原定义中的排列取逆，则连续区间的位置与值域将交换。
考虑推导 \(f\) 的递推式。
不同地，从 \(k-1\) 到 \(k\)，考虑将所有数加一并插入一个新的 \(1\)。
分类讨论：
若插入前原排列合法，则 \(1\) 只有插入在 \(2\) 旁边时才可能形成一个新的长度大于 \(1\) 的不包含最大值的连续区间。
此部分方案数为 \((k-1)f(k-1)\)。若插入前原排列不合法，则最多只会有一个不包含最大值的极长连续区间。因为插入 \(1\) 无法同时破坏两个极长连续区间。 枚举这个区间的长度为 \(i\)，设其在原排列中值域为 \([x,x+i-1]\)，则易知 \(x \ge 2,x+i-1 < k\)，从而 \(2 \le x \le k-i\)。
则这个区间内的元素顺序和 \(1\) 插入的位置可以看做一个 \(i+1\) 阶排列，即把 \(1\) 看做这个排列中的 \(i+1\)，而删去这个 \(i+1\) 可以删去所有连续区间，故方案数为 \(f(i)\)。
另外，考虑这个连续区间的位置，不难得到安排这个连续区间与其他元素的相对位置的方案数为 \(f(k-i)\)。
综上， \[ \begin{aligned} f(k) &= (k-1)f(k-1) + \sum\limits_{i=2}^{k-2} (k-i-1)f(i)f(k-i) \\ &= (k-1)f(k-1) + \sum\limits_{i=2}^{k-2} (i-1)f(i)f(k-i) \qquad (k \ge 2) \end{aligned} \]
分治 NTT 即可。
学习某大佬写左闭右开或许会好写亿点？
（明明就是自己不会写就抄了别人的代码吧）
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
using namespace std;
const int N = 5e4;
const int mod = 998244353;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int T,n,a[N + 5];
namespace Poly
{
const int N = 1 << 17;
const int G = 3;
int lg2[N + 5];
int rev[N + 5],fac[N + 5],ifac[N + 5],inv[N + 5];
int rt[N + 5],irt[N + 5];
inline void init()
{
for(register int i = 2;i <= N;++i)
lg2[i] = lg2[i >> 1] + 1;
int w = fpow(G,(mod - 1) / N);
rt[N >> 1] = 1;
for(register int i = (N >> 1) + 1;i <= N;++i)
rt[i] = (long long)rt[i - 1] * w % mod;
for(register int i = (N >> 1) - 1;i;--i)
rt[i] = rt[i << 1];
fac[0] = 1;
for(register int i = 1;i <= N;++i)
fac[i] = (long long)fac[i - 1] * i % mod;
ifac[N] = fpow(fac[N],mod - 2);
for(register int i = N;i;--i)
ifac[i - 1] = (long long)ifac[i] * i % mod;
for(register int i = 1;i <= N;++i)
inv[i] = (long long)ifac[i] * fac[i - 1] % mod;
}
struct poly
{
vector<int> a;
inline poly(int x = 0)
{
x && (a.push_back(x),1);
}
inline poly(const vector<int> &o)
{
a = o;
shrink();
}
inline void shrink()
{
for(;!a.empty() && !a.back();a.pop_back());
}
inline int size() const
{
return a.size();
}
inline void resize(int x)
{
a.resize(x);
}
inline int operator[](int x) const
{
if(x < 0 || x >= size())
return 0;
return a[x];
}
inline int &operator[](int x)
{
return a[x];
}
inline void clear()
{
vector<int>().swap(a);
}
inline void ntt(int type = 1)
{
int n = size();
type == -1 && (reverse(a.begin() + 1,a.end()),1);
int lg = lg2[n] - 1;
for(register int i = 0;i < n;++i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lg),
i < rev[i] && (swap(a[i],a[rev[i]]),1);
for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
for(register int i = 0;i < n;i += w)
for(register int j = 0;j < m;++j)
{
int t = (long long)rt[m | j] * a[i | j | m] % mod;
a[i | j | m] = dec(a[i | j],t),a[i | j] = add(a[i | j],t);
}
if(type == -1)
for(register int i = 0;i < n;++i)
a[i] = (long long)a[i] * inv[n] % mod;
}
friend inline poly operator+(const poly &a,const poly &b)
{
vector<int> ret(max(a.size(),b.size()));
for(register int i = 0;i < ret.size();++i)
ret[i] = add(a[i],b[i]);
return poly(ret);
}
friend inline poly operator-(const poly &a,const poly &b)
{
vector<int> ret(max(a.size(),b.size()));
for(register int i = 0;i < ret.size();++i)
ret[i] = dec(a[i],b[i]);
return poly(ret);
}
friend inline poly operator*(poly a,poly b)
{
if(a.a.empty() || b.a.empty())
return poly();
int lim = 1,tot = a.size() + b.size() - 1;
for(;lim < tot;lim <<= 1);
a.resize(lim),b.resize(lim);
a.ntt(),b.ntt();
for(register int i = 0;i < lim;++i)
a[i] = (long long)a[i] * b[i] % mod;
a.ntt(-1),a.shrink();
return a;
}
poly &operator+=(const poly &o)
{
resize(max(size(),o.size()));
for(register int i = 0;i < o.size();++i)
a[i] = add(a[i],o[i]);
return *this;
}
poly &operator-=(const poly &o)
{
resize(max(size(),o.size()));
for(register int i = 0;i < o.size();++i)
a[i] = dec(a[i],o[i]);
return *this;
}
poly &operator*=(poly o)
{
return (*this) = (*this) * o;
}
poly deriv() const
{
if(a.empty())
return poly();
vector<int> ret(size() - 1);
for(register int i = 0;i < size() - 1;++i)
ret[i] = (long long)(i + 1) * a[i + 1] % mod;
return poly(ret);
}
poly integ() const
{
if(a.empty())
return poly();
vector<int> ret(size() + 1);
for(register int i = 0;i < size();++i)
ret[i + 1] = (long long)a[i] * inv[i + 1] % mod;
return poly(ret);
}
inline poly modxn(int n) const
{
n = min(n,size());
return poly(vector<int>(a.begin(),a.begin() + n));
}
inline poly inver(int m) const
{
poly ret(fpow(a[0],mod - 2));
for(register int k = 1;k < m;)
k <<= 1,ret = (ret * (2 - modxn(k) * ret)).modxn(k);
return ret.modxn(m);
}
inline poly log(int m) const
{
return (deriv() * inver(m)).integ(),modxn(m);
}
inline poly exp(int m) const
{
poly ret(1);
for(register int k = 1;k < m;)
k <<= 1,ret = (ret * (1 - ret.log(k) + modxn(k))).modxn(k);
return ret.modxn(m);
}
};
}
using Poly::init;
using Poly::poly;
poly g,h;
int f[N + 5];
void solve(int l,int r)
{
if(l >= r)
return ;
if(l + 1 == r)
{
l > 1 && (f[l] = (f[l] + (long long)(l - 1) * f[l - 1]) % mod);
return ;
}
int mid = l + r + 1 >> 1;
solve(l,mid);
if(l > 1)
{
g.resize(mid - l),h.resize(r - l),h[0] = h[1] = 0;
for(register int i = 0;i < mid - l;++i)
g[i] = (long long)(i + l - 1) * f[i + l] % mod;
for(register int i = 2;i < r - l;++i)
h[i] = f[i];
g *= h;
for(register int i = mid;i < r;++i)
f[i] = add(f[i],g[i - l]);
g.resize(mid - l),h.resize(r - l),h[0] = h[1] = 0;
for(register int i = 0;i < mid - l;++i)
g[i] = f[i + l];
for(register int i = 2;i < r - l;++i)
h[i] = (long long)(i - 1) * f[i] % mod;
g *= h;
for(register int i = mid;i < r;++i)
f[i] = add(f[i],g[i - l]);
}
else
{
g.resize(mid),h.resize(mid),g[0] = g[1] = h[0] = h[1] = 0;
for(register int i = 2;i < mid;++i)
g[i] = (long long)(i - 1) * f[i] % mod,
h[i] = f[i];
g *= h;
for(register int i = mid;i < r;++i)
f[i] = add(f[i],g[i]);
}
solve(mid,r);
}
int st[N + 5],top,s,ans;
int flag;
int main()
{
Poly::init();
scanf("%d%d",&T,&n),f[0] = 1,f[1] = 2;
solve(1,n);
for(;T;--T)
{
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
if(a[n] ^ n)
{
puts("0");
continue;
}
ans = 1,top = 0,flag = 0;
for(register int i = 1;i <= n;++i)
{
s = 0;
for(;top && i - a[i] + 1 <= st[top];--top)
{
++s;
if(i - a[i] > st[top] - a[st[top]])
{
puts("0");
flag = 1;
break;
}
}
if(flag)
break;
st[++top] = i,ans = (long long)ans * f[s] % mod;
}
if(flag)
continue;
printf("%d\n",ans);
}
}