[CTSC2018]青蕈领主 题解
Weng_Weijie
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](http://oeis.org/A090753)
感谢 @CaptainSlow 在 Theorem 3.3 处指出的一处错误。
代码：
```cpp
#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;
}
```