题解

问题分析

题目要求计算对初始排列 ([1, 2, \ldots, n]) 进行至多 (k) 次操作（每次操作将一个数移到开头或末尾）后可能得到的排列个数，对每个 (k=0,1,\ldots,n-1) 输出结果模 (m) 的值。

关键观察：

1. 操作的本质是通过移动元素形成新排列，移动次数越少，限制越严格。
2. 初始排列（(k=0)）只有1种。
3. 随着 (k) 增大，合法排列数逐渐增加，最终 (k=n-1) 时可得到所有 (n!) 种排列（样例1中 (n=3) 时 (k=2) 输出6，即 (3!)）。

核心思路

1. 组合数学预处理：

   • 预处理阶乘 (jc[i]) 和逆元 (ny[i])（模 (m)），用于后续组合数计算。逆元通过费马小定理（(a^{m-2} \mod m)）求解，因 (m) 是素数。

2. 生成函数与动态规划：

   • 对每个可能的移动次数相关参数 (i)，构造生成函数 (f)，其系数通过逆元定义，用于表示合法的操作约束。
   • 用动态规划 (g[j]) 计算生成函数卷积，(g[j]) 表示满足约束的 (j) 个元素的排列方案数，通过递推公式累加合法组合。

3. 容斥与累加：

   • 通过容斥原理（(an[i] = an[i] - an[i-1])）调整计数，得到恰好 (i) 次操作的方案数。
   • 累加得到“至多 (k) 次操作”的结果，按 (k=0) 到 (k=n-1) 输出。

代码解析

1. 预处理：

   • 计算阶乘 (jc[i] = i! \mod m) 和逆元 (ny[i] = (i!)^{-1} \mod m)，逆元从 (n) 倒推至 (1)。

2. 生成函数构造：

   • 对每个 (i)，构造数组 (f)，其中 (f[j]) 根据 (j) 是否为 (i+1) 的倍数取逆元或其负数（模 (m)），用于表示操作约束。

3. 动态规划计算：

   • (g[0] = 1)（初始状态），对 (j \geq 1)，(g[j]) 通过卷积累加 (f[o] \cdot g[j-o]) 并取负（模 (m)），得到满足约束的方案数。

4. 结果调整与输出：

   • (an[i]) 表示与 (i) 相关的方案数，乘以 (n!) 后通过容斥调整。
   • 累加 (an[i]) 得到“至多 (k) 次操作”的结果，逆序输出（对应 (k=0) 到 (k=n-1)）。

总结

该解法通过生成函数与动态规划结合数论工具，高效计算了不同操作次数下的合法排列数，核心是利用组合数学和容斥原理处理操作约束，时间复杂度为 (O(n^2))，适用于 (n \leq 1000) 的数据范围。