自动搬运

查看原文

来自洛谷，原作者为

	Weng_Weijie やー！今日もパンがうまい！

搬运于2025-08-24 22:01:26，当前版本为作者最后更新于2019-01-17 19:36:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这篇文章参考了其他人的题解，结合了我自己的理解，希望大家喜欢

---

题意

$\mathrm{Definition}$

极长连续区间: 若 $[l,r]$ 对应的值为 $\alpha_l,\dots,\alpha_r$, 且 $\max p -\min p + 1=r - l+1$，则 $[l,r]$ 称为连续区间，对一个 $i$， 找到最大的 $j$，使得 $[i-j+1,i]$ 是连续区间，称 $[i-j+1,i]$ 为极长连续区间

对于一个排列 $\alpha$，用 $L_i$ 表示以第 $i$ 个元素为右端点的极长连续区间长度

给定 $L_i$ 求满足条件的排列 $\alpha$ 的个数

---

题解

Part 1

$\mathrm{Theorem}\space 1.1$

$L_n=n$

$\mathrm{Proof}\space 1.1$

显然整个排列就是一个极长连续区间

$\mathrm{Theorem}\space 1.2$

极长连续区间要么相包含，要么没有交

$\mathrm{Proof}\space 1.2$

如果两个极长连续区间相交而不包含，显然这两个极长连续区间的并也是连续区间，从而右边的极长连续区间不满足极长连续子区间的定义

由 定理1.1 和 定理1.2 可以总结出无解的条件

接下来的叙述可以说明当且仅当不满足上两个条件之一时无解

$\mathrm{Theorem}\space 1.3$

将每个极长连续区间找到最短的包含它的极长连续区间，会形成一个树型结构

$\mathrm{Proof}\space 1.3$

除了 $L_n$ 以外其他极长连续区间，都能找到一个最短的极长连续区间

Part 2

接下来将考虑如何计数

$\mathrm{Definition}$

令 $f_n$ 表示满足 $L_i=1\space (i\in [1,n])$ 的 $n+1$ 阶排列数量

若将一个连续区间 $[l,r]$ 提取出来，$L$ 不变，只考虑这些元素的相对大小关系，可以看成是一个 $r-l+1$ 阶排列，得到的一段区间的答案记做 $A[l,r]$，这道题即求 $A[1,n]$

$\mathrm{Theorem}\space 2.1$

若极长连续区间 $[l,r]$ 在树型关系中有 $k$ 个儿子分别为 $[p_0,p_1-1],[p_1,p_2-1]\dots,[p_{k-1},p_k-1]$，则 $A[l,r]=f(k)\displaystyle\prod_{i=0}^{k-1} A[p_i,p_{i+1}-1]$

$\mathrm{Proof}\space 2.1$

可以发现 $p_0=l,p_k=r$，由于 $[p_i,p_{i+1}-1]$ 这若干个区间是连续的，所以这 $k$ 个区间包括 $[r,r]$ 总共 $k+1$ 个区间相对大小关系是确定的，即要么 $A$ 中每个元素都小于 $B$ 中每个元素，要么都大于

将这 $k+1$ 个区间按照大小关系给定一个 $k+1$ 阶排列，在这 $k+1$ 阶排列中的连续区间，在原区间中也是连续区间

因此除了 $[r,r]$ 有一个长度为 $k+1$ 的极长连续区间， 其余均不能有长度大于 $1$ 的连续区间，否则在原排列中就不是极长连续区间

因此方案数为每个内部区间的方案数乘积再乘上 $f(k)$

$\mathrm{Theorem}\space 2.2$

设 $s_i$ 为以 $i$ 结尾极长连续区间树型结构中儿子个数，则答案为 $\displaystyle\prod_{i=1}^nf(s_i)$

$\mathrm{Proof}\space 2.2$

根据 定理2.1 将其展开即可

由 定理2.1 或 定理2.2 说明了之前无解条件的问题

Part 3

接下来的问题变为了如何求 $f(n)$

$\mathrm{Theorem}\space 3.1$

$f(n)$ 等于所有连续区间要么包含 $n+1$，要么长度为 $1$ 的 $n+1$ 阶排列个数

$\mathrm{Prood}\space 3.1$

考虑排列 $\alpha$ 的逆 $\alpha^{-1}$

考虑连续区间 $[l,r]$ 的对应的值为 $[L,R]$ 那么在 $\alpha^{-1}$ 中 $[L,R]$ 对应的值为 $[l,r]$

若 $[l,r]$ 不是一个连续区间，那么 $\alpha_l,\dots,\alpha_r$ 不是一个区间

即原排列和逆排列的连续区间一一对应

原排列中的连续区间要么包含最后一个元素，要么长度为 $1$，因此逆排列中的连续区间要么包含 $n+1$，要么长度为 $1$

接下来考虑计算在后一个意义下计算 $f(n)$

记满足该性质的排列为合法排列

$\mathrm{Theorem}\space 3.3$

当 $n>2$ 时，$f(n)=(n-1)f(n-1)+\displaystyle\sum_{i=2}^{n-2}(n-i-1)f(i)f(n-i), f(0)=1, f(1)=2$

$\mathrm{Proof}\space 3.3$

考虑将 $n$ 阶排列中每个元素 $+1$ 然后插入 $1$ 来得到合法 $n+1$ 排列

分两种情况：

(1) 原排列合法，此时插入 $1$ 只要不插入在 $2$ 旁边即可得到一个新的合法排列

假设产生了一个新的不经过最大值的连续区间 $[l,r]$，那么它一定经过 $1$，即 值域为 $[1,x]$，而此时原排列的区间 $[l,r-1]$ 的值域为 $[1,x-1]$，因此与它是合法区间矛盾

(2) 原排列不合法，此时刚好有一个不经过最大值，长度 $>1$ 且不被其他极大连续区间包含的极大连续区间，否则插入一个 $1$ 并不会使两个极大连续区间同时消失，即不会变得合法

设这个原排列中极大连续区间长度为 $l$，值域为 $[x,x+l-1]$

首先 $x > 1$，不然插入后的这个区间也是连续的，然后因为原区间不经过最大值，因此 $x+l-1<n$，$2 \leq x \leq n-l$，所以 $x$ 的取值共有 $n-l-1$ 种

再考虑 $l$ 的范围，$l\geq 2$ 是显然的，而为了 $x$ 有取值 $n-l\geq 2$，即 $l\leq n-2$

再考虑方案数，先考虑这个特殊区间的方案数，这个区间中没有 $2$，因此经过 $1$ 的子区间都不会是连续的，于是把 $1$ 看做 $l+1$，其他的元素按大小关系编号为 $1\sim l$，方案数为 $f(l)$，接下来无视这个 $1$，将这个区间和其他 $n-l$ 个元素按照大小关系编号为 $1\sim n-l+1$，方案数为 $f(n-l)$，可以证明不会有新增的连续区间，证明方法与第一种情况类似

至此，这道题就做完了，可以用单调栈求出每个极长连续区间的儿子个数，用分治+FFT 求 $f(n)$。事实上OEIS上有这个序列，也可以参考一下 A090753

感谢 @CaptainSlow 在 Theorem 3.3 处指出的一处错误。

代码：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

namespace IO {
	char rbuf[(int) 1e8], *in = rbuf, ch;
	void init() {
		std::fread(rbuf, 1, 1e8, stdin);
	}
	char getchar() {
		return *in++;
	}
	void read(int &x) {
		while (std::isspace(ch = getchar())); x = ch & 15;
		while (std::isdigit(ch = getchar())) x = x * 10 + (ch & 15);
	}
}
const int N = 131072;
using LL = long long;
int n, f[N], lim, s, rev[N], wn[N], w[N];
const int mod = 998244353;
int pow(int x, int y) {
	int ans = 1;
	for (; y; y >>= 1, x = (LL) x * x % mod)
		if (y & 1) ans = (LL) ans * x % mod;
	return ans;
}
void fftinit(int len) {
	wn[0] = lim = 1, s = -1; while (lim < len) lim <<= 1, ++s;
	for (int i = 0; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
	const int g = pow(3, (mod - 1) / lim);
	for (int i = 1; i < lim; ++i) wn[i] = (LL) wn[i - 1] * g % mod;
}
void reduce(int &x) { x += x >> 31 & mod; }
void fft(int *A, int typ) {
	for (int i = 0; i < lim; ++i)
		if (i < rev[i]) std::swap(A[i], A[rev[i]]);
	for (int i = 1; i < lim; i <<= 1) {
		const int t = lim / i / 2;
		for (int k = 0; k < i; ++k) w[k] = wn[t * k];
		for (int j = 0; j < lim; j += i << 1)
			for (int k = 0; k < i; ++k) {
				const int x = A[k + j], y = (LL) A[k + j + i] * w[k] % mod;
				reduce(A[k + j] += y - mod), reduce(A[k + j + i] = x - y);
			}
	}
	if (!typ) {
		std::reverse(A + 1, A + lim);
		const int il = pow(lim, mod - 2);
		for (int i = 0; i < lim; ++i)
			A[i] = (LL) A[i] * il % mod;
	}
}
int A[N], B[N];
void mul(int *A, int *B, int n, int m, int *ret, int len) {
	static int tA[N], tB[N];
	fftinit(n + m - 1);
	std::memcpy(tA, A, n << 2), std::memset(tA + n, 0, lim - n << 2);
	std::memcpy(tB, B, m << 2), std::memset(tB + m, 0, lim - m << 2);
	fft(tA, 1), fft(tB, 1);
	for (int i = 0; i < lim; ++i)
		tA[i] = (LL) tA[i] * tB[i] % mod;
	fft(tA, 0);
	std::memcpy(ret, tA, len << 2);
}
void solve(int l, int r) {
	if (l + 1 == r) { reduce(f[l] += (LL) (l - 1) * f[l - 1] % mod - mod); return; }
	int mid = l + r + 1 >> 1;
	solve(l, mid);
	if (l > 1) {
		for (int i = l; i < mid; ++i)
			A[i - l] = (LL) (i - 1) * f[i] % mod;
		B[0] = B[1] = 0;
		for (int i = 2; i < r - l; ++i)
			B[i] = f[i];
		mul(A, B, mid - l, r - l, A, r - l);
		for (int i = mid; i < r; ++i)
			reduce(f[i] += A[i - l] - mod);
		A[0] = A[1] = 0;
		for (int i = 2; i < r - l; ++i)
			A[i] = (LL) (i - 1) * f[i] % mod;
		for (int i = l; i < mid; ++i)
			B[i - l] = f[i];
		mul(A, B, r - l, mid - l, A, r - l);
		for (int i = mid; i < r; ++i)
			reduce(f[i] += A[i - l] - mod);
	} else {
		A[0] = A[1] = B[0] = B[1] = 0;
		for (int i = 2; i < mid; ++i)
			A[i] = (LL) (i - 1) * f[i] % mod, B[i] = f[i];
		mul(A, B, mid, mid, A, r);
		for (int i = mid; i < r; ++i)
			reduce(f[i] += A[i] - mod);
	}
	solve(mid, r);
}
int tc, L[N], stack[N], top;
void solve() {
	for (int i = 1; i <= n; ++i)
		IO::read(L[i]);
	if (L[n] != n)
		return void(std::puts("0"));
	top = 0;
	int ans = 1;
	for (int i = 1; i <= n; ++i) {
		int _cnt = 0;
		while (top) {
			if (i - L[i] + 1 <= stack[top] && i - L[i] > stack[top] - L[stack[top]]) {
				return void(std::puts("0"));
			}
			if (i - L[i] + 1 <= stack[top])
				++_cnt, --top;
			else
				break;
		}
		stack[++top] = i;
		ans = (LL) ans * f[_cnt] % mod;
	}
	std::printf("%d\n", ans);
}
int main() {
	IO::init();
	f[0] = 1, f[1] = 2;
	IO::read(tc), IO::read(n);
	solve(1, n);
	while (tc--)
		solve();
	return 0;
}