[CTSC2018]青蕈领主 题解

· · 题解

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

题意

\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
\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;
}