题解

问题分析

题目要求计算“正确的排列”（即不存在非平凡连续子序列且值连续的排列）的个数，这类排列在组合数学中被称为简单置换（Simple Permutations）。简单置换的定义为：不包含长度为 (2 \le k \le n-1) 的连续子序列构成公差为1的等差数列（即值连续）。

核心思路

1. 生成函数与反演：

   • 利用生成函数表示置换的计数问题，通过组合反演（Combinatorial Inversion）推导简单置换的生成函数。
   • 关键生成函数包括：全体置换的生成函数 (P(x))、连通置换的生成函数 (C(x))、简单置换的生成函数 (S(x))。

2. 递归关系与FFT优化：

   • 简单置换的计数可通过递归关系推导，涉及生成函数的卷积运算，利用FFT（此处为NTT，模998244353下的快速变换）优化卷积计算，降低时间复杂度。
   • 通过OEIS序列（A003319、A111111）验证递归关系，确认简单置换的计数公式。

3. 预处理与高效计算：

   • 预处理阶乘、逆元等组合数工具，用于生成函数的系数计算。
   • 实现组合反演算法，求解生成函数的逆，进而得到简单置换的计数序列。

代码解析

1. 模运算与NTT实现：

   • 定义 ModInt 结构体处理模998244353的运算，包括加减乘除、幂运算和逆元计算。
   • 实现NTT（快速数论变换）及其逆变换，用于高效计算多项式卷积，是生成函数运算的核心工具。

2. 生成函数反演：

   • cominvFac 函数通过分块FFT计算生成函数的组合逆，得到与置换计数相关的序列 (Q)（对应OEIS A059372）。

3. 简单置换计数：

   • simplePermutations 函数利用 (Q) 序列推导简单置换的计数序列 (S)（对应OEIS A111111），其中：
     • (S[1] = 1)，(S[2] = 2)，(S[3] = 0)（长度为3的置换必含非平凡连续子序列）。
     • 对于 (n \ge 4)，通过 (Q) 序列的系数转换得到 (S[n])。

4. 输出处理：

   • 根据输入的 type 和 n，输出对应长度的简单置换个数（type=0 输出单个值，type=1 输出1到n的所有值）。

总结

该解法通过生成函数和组合反演理论，结合NTT优化卷积运算，高效计算了简单置换的个数。时间复杂度主要来自FFT运算，为 (O(n \log n))，适用于 (n \le 10^5) 的数据范围。核心是将置换计数问题转化为生成函数的运算，利用反演关系和快速变换工具突破枚举法的效率瓶颈。