题目理解

我们有一个 $N$ 句话的佛经，需要给每句话分配一个 $1$ 到 $N$ 的编号（排列）。每天只能在第 $i$ 个时段读编号为 $i$ 的句子。目标是计算恰好用 $K$ 天读完佛经的排列方案数。

问题分析

1. 问题转化

这实际上等价于计算有多少个 $1$ 到 $N$ 的排列，使得该排列恰好有 $K-1$ 个"上升"（即排列的下降数为 $K-1$）。

• 一天对应排列中的一个"连续下降段"
• 恰好 $K$ 天对应排列中恰好有 $K-1$ 个位置满足 $p_i > p_{i+1}$

2. 组合数学背景

这是一个经典的欧拉数问题。第 $n$ 个排列中恰好有 $k$ 个下降的排列数就是欧拉数 $\left\langle\begin{matrix}n \\ k\end{matrix}\right\rangle$。

算法思路

1. 容斥原理公式

代码使用了欧拉数的容斥原理公式：

$$\left\langle\begin{matrix}n \\ m\end{matrix}\right\rangle = \sum_{k=0}^{m} (-1)^k \binom{n+1}{k} (m+1-k)^n $$

其中：

• $n = N$（排列长度）
• $m = K-1$（下降个数）

2. 模运算处理

由于结果很大，需要对 $10^9+7$ 取模：

• 使用费马小定理计算组合数的模逆元
• 所有运算在模意义下进行

代码解析

1. 预处理阶乘

fr[0] = 1;
for (int i = 1; i <= n + 1; ++i)
    fr[i] = fr[i - 1] * i % Mod;

2. 快速幂函数

int qpow(int a, int b) {
    if (b == 0) return 1 % Mod;
    if (b & 1) return qpow(a, b - 1) * a % Mod;
    return qpow(a * a % Mod, b >> 1);
}

3. 组合数计算

int C(int n, int m) {
    return fr[n] * qpow(fr[m], Mod - 2) % Mod * qpow(fr[n - m], Mod - 2) % Mod;
}

4. 主计算逻辑

int co = 1;
for (int i = 0; i <= m; ++i, co *= -1)
    ans = (ans + C(n + 1, i) * qpow(m + 1 - i, n) % Mod * co) % Mod;
ans = (ans + Mod) % Mod;  // 处理负数

这里：

• m = K-1（下降个数）
• co 是 $(-1)^k$ 项
• C(n+1, i) 是 $\binom{n+1}{k}$
• qpow(m+1-i, n) 是 $(m+1-k)^n$

关键算法细节

1. 欧拉数公式推导

欧拉数 $\left\langle\begin{matrix}n \\ m\end{matrix}\right\rangle$ 表示长度为 $n$ 的排列中恰好有 $m$ 个下降的排列数。

容斥公式：

$$\left\langle\begin{matrix}n \\ m\end{matrix}\right\rangle = \sum_{k=0}^{m} (-1)^k \binom{n+1}{k} (m+1-k)^n $$

2. 模逆元计算

使用费马小定理：$a^{p-2} \equiv a^{-1} \pmod{p}$

qpow(fr[m], Mod - 2)  // 计算 fr[m] 的模逆元

3. 负数处理

由于容斥原理中可能出现负数，需要调整到模范围内：

ans = (ans + Mod) % Mod;

复杂度分析

• 预处理阶乘：$O(N)$
• 主循环：$O(K)$ 次迭代，每次包含 $O(\log N)$ 的快速幂
• 总复杂度：$O(N + K \log N)$
• 空间复杂度：$O(N)$

对于 $N \leq 10^5$，这是可接受的。

算法标签

• 组合数学：欧拉数、排列计数
• 容斥原理：核心计算方法
• 数论：模运算、模逆元
• 生成函数：欧拉数的生成函数背景

数学背景

欧拉数的性质

• $\left\langle\begin{matrix}n \\ 0\end{matrix}\right\rangle = 1$（完全上升排列）
• $\left\langle\begin{matrix}n \\ n-1\end{matrix}\right\rangle = 1$（完全下降排列）
• $\sum_{m=0}^{n-1} \left\langle\begin{matrix}n \\ m\end{matrix}\right\rangle = n!$

与本题的关联

• 用 $K$ 天读完 ⇔ 排列有 $K-1$ 个下降
• 答案 = $\left\langle\begin{matrix}N \\ K-1\end{matrix}\right\rangle$

总结

这道题通过将实际问题转化为排列的下降数计数问题，运用了经典的欧拉数容斥公式。算法的核心在于：

1. 问题转化：将天数问题转化为排列的下降数问题
2. 数学公式：使用欧拉数的容斥计算公式
3. 高效计算：预处理阶乘，使用快速幂和模逆元
4. 边界处理：正确处理模运算和负数情况

该解法充分利用了组合数学的经典结果，展示了数学理论在算法竞赛中的重要作用。