「CTSC2018」青蕈领主

题意简述

一个排列，给出右端点为 $i$ 的最长连续段长度 $L_i$，求可能的排列总数对 $998244353$ 取模。
不超过 $100$ 组数据，$n\le 5\times 10^4$。

主要思路

下称「非平凡连续段」为长度大于一的连续段。
由于连续段的交与并也是连续段，因此一个合法的输入连边相交线段应当构成一个树形结构。
考虑一个节点的子树，其对应的区间值域连续，且其不能出现在更大的连续区间中，因此可以等效地看成一个数。
因此，记 $f_n$ 为长度为 $n$ 的，去掉最后一个元素后不存在非平凡连续段的排列个数，$son_n$ 表示点 $n$ 的子节点个数。
则答案为 $\prod\limits_{i=1}^{n}f_{son_i}$。

现在我们考虑如何求出 $f$。
去掉最后一个元素后不存在非平凡连续段的排列的逆排列即不存在不包含最大值的非平凡连续段的排列，显然其个数与不存在不包含最小值的非平凡连续段的排列相同。那么考虑加上排列的最小值，此时排列长度为 $n+1$。

排列原先已满足不存在不包含最小值的非平凡连续段。
那么只需不与次小值相邻即可，故有 $n - 1$ 个插入位置。
排列原先存在不包含最小值的非平凡连续段。
枚举其中不包含最小值的非平凡连续段的最大长度 $j$($j\in[2, n - 2]$)，其值域应不包含最小值 $2$，共 $n - j - 1$ 种取值。插入最小值 $1$ 后，该区间及全局都不再存在不包含最小值的非平凡连续段，故可行的排列数为 $f_jf_{n-j}$。

于是递推式即为 $f_n = (n-1)f_{n-1} +\sum\limits_{j=2}^{n-2}(n-j-1)f_jf_{n-j}$。分治 FFT 即可。

参考代码

这个分治 FFT 由于是自己更新自己的，如果按照正常方法，左端点为整个分治的左端点时会有部分未处理完全，就会出问题。
所以要改一改，具体都写在代码里了。

#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
typedef long long i64;
typedef unsigned long long u64;
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
#define mod 998244353
inline int ksm(int x, int y) {
    int res = 1;
    for (; y; y >>= 1, x = (i64)x * x % mod)
        if (y & 1) res = (i64)res * x % mod;
    return res;
}
inline void qmo(int &x){ x += (x >> 31) & mod; }
} // namespace my_std
using namespace my_std;

#define MMR (1 << 23)
struct INPUT{
    char buf[MMR], *s, *t;
    INPUT(){ t = (s = buf) + fread(buf, 1, MMR, stdin); }
    #define gc() (s == t ? \
    (t = (s = buf) + fread(buf, 1, MMR, stdin), \
    s == t ? -1 : *s++) : *s++)
    inline INPUT& operator >>(int &x){
        x = 0;
        reg char c(gc());
        while(c < 48) c = gc();
        while(c > 47) x = x * 10 + c - 48, c = gc();
        return *this;
    }
}fin;
struct OUTPUT{
    char buf[MMR], *s;
    OUTPUT(){ s = buf; }
    inline OUTPUT& operator <<(int x){
        static int tmp[16];
        Rint *top = tmp;
        do{
            *++top = (x % 10) ^ 48, x /= 10;
        }while(x);
        while(top != tmp) *s++ = *top--;
        *s++ = 10;
        return *this;
    }
    inline void operator ++(){ *s++ = 48, *s++ = 10; }
    ~OUTPUT(){ fwrite(buf, 1, s - buf, stdout); }
}fout;

#define N 131131

int LMT(1);
int rev[N], omg[N], l2g[N];
inline void init(const int &n){
    FOR(i, 2, n << 1) l2g[i] = l2g[i >> 1] + 1;
}
inline void poly_init(const int &n){
    Rint l(0);
    while(LMT <= n) LMT <<= 1, ++l;
    FOR(i, 1, LMT - 1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
    reg const i64 t(ksm(3, (mod - 1) >> l));
    omg[LMT >> 1] = 1;
    FOR(i, (LMT >> 1) + 1, LMT - 1) omg[i] = t * omg[i - 1] % mod;
    ROF(i, (LMT >> 1) - 1, 1) omg[i] = omg[i << 1];
    LMT = l;
}
inline int get_len(const int &n){
    return 1 << (l2g[n] + 1);
}

inline void DFT(int *a, const int &n){
    static u64 tmp[N];
    reg const int fix(LMT - l2g[n]);
    Rint t;
    FOR(i, 0, n - 1) tmp[i] = a[rev[i] >> fix];
    for(Rint i(1); i < n; i <<= 1){
        for(Rint j(0); j < n; j += i << 1){
            FOR(k, j, j + i - 1){
                t = tmp[i + k] * omg[i + k - j] % mod;
                tmp[i + k] = tmp[k] + mod - t;
                tmp[k] += t;
            }
        }
    }
    FOR(i, 0, n - 1) a[i] = tmp[i] % mod;
}
inline void IDFT(int *a, const int &n){
    reverse(a + 1, a + n);
    DFT(a, n);
    reg const i64 bk(mod - (mod - 1) / n);
    FOR(i, 0, n - 1) a[i] = bk * a[i] % mod;
}

int n;
int f[N];
int tmp[N];

#define mst(A, B, C) memset((A), (B), (C) * sizeof(int))
#define mcp(A, B, C) memcpy((A), (B), (C) * sizeof(int))

void dac(const int &l, const int &r){
    if(l == r){
        qmo(f[l] += (3ll + mod - l) * f[l - 1] % mod - mod);
        return;
    }
    static int A[N], B[N];
    Rint mid((l + r) >> 1), lim(get_len(r - l + 1));
    dac(l, mid);

    mst(A, 0, lim), mst(B, 0, lim);
    if(l == 1){
        FOR(i, 1, mid) A[i - 1] = (i - 1ll) * f[i] % mod, B[i] = f[i];
        if(lim <= 24){
            mst(tmp, 0, lim);
            FOR(i, 0, (lim) - 1) FOR(j, 0, (lim) - 1)
                qmo(tmp[i + j] += (i64)A[i] * B[j] % mod - mod);
            FOR(i, mid + 1, r) qmo(f[i] += tmp[i - 1] - mod);
        }else{
            DFT(A, lim), DFT(B, lim);
            FOR(i, 0, lim - 1) A[i] = (i64)A[i] * B[i] % mod;
            IDFT(A, lim);
            FOR(i, mid + 1, r) qmo(f[i] += A[i - 1] - mod);
        }
    }else{
        mcp(A, f + l, mid + 1 - l);
        mcp(B + 1, f + 1, r - l);
        if(lim <= 24){
            mst(tmp, 0, lim);
            FOR(i, 0, (lim) - 1) FOR(j, 0, (lim) - 1)
                qmo(tmp[i + j] += (i64)A[i] * B[j] % mod - mod);
            FOR(i, mid + 1, r) qmo(f[i] += tmp[i - l] * (i - 2ll) % mod - mod);
        }else{
            DFT(A, lim), DFT(B, lim);
            FOR(i, 0, lim - 1) A[i] = (i64)A[i] * B[i] % mod;
            IDFT(A, lim);
            FOR(i, mid + 1, r) qmo(f[i] += A[i - l] * (i - 2ll) % mod - mod);
        }
    }

    dac(mid + 1, r);
}

int a[N];
int c[N];
int d[N];

inline void work(){
    FOR(i, 1, n) fin >> a[i];
    if(a[n] != n) return ++fout;
    Rint *t(d);
    mst(c, 0, n);
    Rint g, r, mx(0);
    FOR(i, 1, n){
        g = 0, r = i;
        while(d != t && *t >= i - a[i] + 1) ++g, r = *t--;
        if(r - a[r] < i - a[i]) return ++fout;
        chkmax(mx, g);
        ++c[g], *++t = i;
    }
    Rint A(1);
    FOR(i, 1, mx) A = (i64)A * ksm(f[i], c[i]) % mod;
    fout << A;
}

int main() {
    Rint esac;
    fin >> esac >> n;
    init(n), poly_init(n << 1);
    f[1] = 2, dac(1, n), f[0] = 1;
    while(esac --) work();
    return 0;
}