CCPC 2021 Online H - Subpermutation 复盘：排列边界与逆阶乘求和

题目中的两类连续段

2021 CCPC 网络选拔赛（重赛）H - Subpermutation 定义了 $n$ 的 full-permutation：把 $1$ 到 $n$ 的全部排列按字典序依次拼接，得到序列 $p_n$。

题目给定 $n,m$，要求统计 $p_n$ 中有多少个长度为 $m$ 的连续子序列，本身恰好是 $1$ 到 $m$ 的一个排列。多组数据的答案对 $10^9+7$ 取模，其中

$$1\le m\le n\le 10^6,\qquad T\le 10^5.$$

每个原排列的长度为 $n$，而待统计连续段的长度 $m$ 不超过 $n$。因此，一个连续段至多经过两个原排列，所有情况可以完整地拆成两类：

• 连续段完全位于一个排列内部；
• 连续段取前一个排列的非空后缀，再取后一个排列的非空前缀。

两类之间互不重叠，分别计数后相加即可。

一个排列内部的贡献

长度为 $m$ 的连续段是 $1$ 到 $m$ 的排列，当且仅当这 $m$ 个数在当前排列中占据连续的 $m$ 个位置。

先确定这个连续块的起点，共有 $n-m+1$ 种选择；块内的 $1$ 到 $m$ 可以任意排列，其余 $n-m$ 个数也可以任意排列。因此，完全位于单个排列内部的合法连续段总数为

$$I=(n-m+1)m!(n-m)!.$$

这里是在全部 $n!$ 个排列中整体计数：每个满足条件的排列恰好贡献一个合法位置，不会重复。

跨过排列边界

固定跨边界连续段从前一个排列末尾取出的长度为 $k$，其中

$$1\le k\le m-1.$$

记 $d=m-k$，并把前一个排列 $P$ 按位置拆成

$$P=A+B+C,$$

其中 $|A|=d$、$|B|=n-m$、$|C|=k$。跨边界的连续段由 $C$ 和后继排列 $Q$ 的长度为 $d$ 的前缀拼成。

先只要求 $A$ 与 $C$ 合起来恰好包含 $1$ 到 $m$。这时：

• $1$ 到 $m$ 可以任意放入 $A,C$ 对应的共 $m$ 个位置，有 $m!$ 种；
• $m+1$ 到 $n$ 可以任意放入中间的 $B$，有 $(n-m)!$ 种。

候选排列共有

$$m!(n-m)!$$

个。还需要判断从 $P$ 走到字典序后继 $Q$ 时，前缀 $A$ 是否保持不变。

最长下降后缀带来的扣除项

求一个排列的字典序后继时，需要找到它的最长下降后缀：交换后缀前的枢轴，再把后缀改成最小的升序状态。

如果 $B+C$ 不是下降序列，枢轴一定落在 $B+C$ 内，长度为 $d$ 的前缀 $A$ 不会改变。此时跨边界连续段就是 $C+A$，其中每个 $1$ 到 $m$ 恰好出现一次，因此合法。

反过来，如果 $B+C$ 整体下降，字典序后继操作就会越过 $A$ 与 $B+C$ 的分界。后继排列的前 $d$ 项不再恰好是原来的 $A$：会有原分界右侧的元素进入前缀；若 $P$ 已是最后一个排列，则它本来也没有后继。无论哪种情况，$C$ 与新前缀都不能再恰好组成 $1$ 到 $m$ 的排列。

于是只需从候选数中扣除 $B+C$ 整体下降的情况。

由于 $B$ 中的数都大于 $m$，$C$ 中的数都不超过 $m$，二者交界处天然满足下降关系。要让 $B+C$ 整体下降，只需让 $B$、$C$ 各自都按降序排列：

• 从 $1$ 到 $m$ 中选择 $k$ 个数放进 $C$，有 $\binom{m}{k}$ 种；选定后，$C$ 的降序唯一；
• 剩下的 $d$ 个数在 $A$ 中任意排列，有 $d!$ 种；
• $B$ 的降序唯一。

扣除项因此为

$$\binom{m}{k}d! =\binom{m}{k}(m-k)! =\frac{m!}{k!}.$$

固定 $k$ 时，合法的跨边界连续段数量为

$$B_k=m!(n-m)!-\frac{m!}{k!} =m!\left((n-m)!-\frac{1}{k!}\right).$$

对所有 $k$ 求和：

$$\begin{aligned} B &=\sum_{k=1}^{m-1}B_k \\ &=m!\left((m-1)(n-m)!-\sum_{k=1}^{m-1}\frac{1}{k!}\right). \end{aligned}$$

合并为闭式

把排列内部与排列边界的贡献相加：

$$\begin{aligned} Ans &=I+B \\ &=(n-m+1)m!(n-m)! \\ &\quad +m!\left((m-1)(n-m)!-\sum_{k=1}^{m-1}\frac{1}{k!}\right) \\ &=m!\left(n(n-m)!-\sum_{k=1}^{m-1}\frac{1}{k!}\right). \end{aligned}$$

最终只需要阶乘、逆阶乘以及逆阶乘的前缀和。

设

$$S_i=\sum_{k=1}^{i}\frac{1}{k!},$$

实现中的 fac[i]、ifac[i]、sum[i] 分别维护 $i!$、$(i!)^{-1}$ 和 $S_i$。单次询问直接计算

return (1ll * n * fac[n - m] % mod - sum[m - 1] + mod) % mod * fac[m] % mod;

其中的除法都在模 $10^9+7$ 意义下用逆元完成。预处理范围小于模数，所以每个阶乘都有逆元。

当 $m=1$ 时，求和为空，sum[0]=0，公式给出 $n(n-1)!=n!$，正好等于完整串中数字 1 的出现次数。当 $n=m$ 时，fac[n-m]=fac[0]=1，同一套公式也无需额外分支。

复杂度与实现边界

阶乘、逆阶乘和前缀和预处理到 $10^6$，时间复杂度为 $O(10^6+\log(10^9+7))$，空间复杂度为 $O(10^6)$。完成预处理后，每组询问只进行常数次模运算，单次复杂度为 $O(1)$，全部询问为 $O(T)$。

实现中还有三个边界需要保持一致：

• fac[0]=1，保证 $n=m$ 时可以直接取 $0!$；
• 逆阶乘前缀和从 ifac[1] 开始，保证 $m=1$ 时扣除项为空；
• 模减法先加 mod 再取模，避免中间结果为负数。

最终 AC 代码

点击展开/折叠 最终 AC 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 1e9 + 7, maxn = 1e6 + 5;

ll t, fac[maxn], ifac[maxn], sum[maxn];

ll qpow(ll a, ll b) {
    ll res = 1;
    a %= mod;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        fac[i] = fac[i - 1] * i % mod;
    }
    ifac[maxn - 1] = qpow(fac[maxn - 1], mod - 2) % mod;
    for (int i = maxn - 2; i >= 0; --i) {
        ifac[i] = ifac[i + 1] * (i + 1) % mod;
    }
    for (int i = 1; i < maxn; ++i) {
        sum[i] = (sum[i - 1] + ifac[i]) % mod;
    }
}

ll ans(int n, int m) {
    return (1ll * n * fac[n - m] % mod - sum[m - 1] % mod + mod) % mod * fac[m] % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        cout << ans(n, m) << '\n';
    }
    return 0;
}