# 某不科学的单调序列计数: 题解

## 方法与贡献

出题人解法通过隔板法得到组合数，并使用 Pascal 递推。Codex（GPT-6）采用乘积与一次逆元求值，降低时间和空间；[std.cpp](std.cpp) 为首选。出题人的递推法使用滚动数组保留在 [alternative.cpp](alternative.cpp) 和[补充题解](solution-alternative.zh.md)，无需除法，能通过完整数据。

## 隔板法

设编号 $j$ 出现 $a_j$ 次。非递减要求使这些次数唯一决定序列，因此问题等价于

$$a_1+\cdots+a_m=n,\qquad a_j\ge0$$

把 $n$ 个相同标记与 $m-1$ 个隔板排在一起，两道相邻隔板之间、最前和最后的标记数分别给出各编号出现次数。允许相邻隔板及两端隔板，所以零次出现同样覆盖。共有

$$\binom{n+m-1}{n}=\binom{n+m-1}{m-1}$$

种排法，且双向转换唯一，公式成立。

## 计算组合数

令 $a=n+m-1$ 、$t=\min(n,m-1)$ .分子连乘 $a-t+1$ 至 $a$ ，分母连乘一至 $t$ ，分别对质数 $p$ 取模，再乘分母的 $p-2$ 次幂。所有因子都小于 $p$ ，分母可逆。$m=1$ 时 $t=0$ ，两个空乘积均为一。

每次乘法使用 64 位整数，乘积小于 $p^2$ .程序不需要保存全部组合数。

## 正确性与复杂度

隔板双射证明目标等于所用组合数；乘积公式和费马小定理给出其模值。时间 $O(t+\log p)$ ，辅助空间 $O(1)$ .滚动 Pascal 法时间 $O((n+m)t)$ 、空间 $O(t)$ ，对合数模数仍成立；本题模数为质数时首选乘积法。

## 数据生成与验证

使用 Python 3 标准库运行 `tests/generate.py --out-dir <目录>` 可按 [plan.json](tests/plan.json) 生成输入；可重复使用 `--case` 选择编号，使用 `--std <可执行程序路径>` 同时生成输出。先自行以 C++17 编译所需源码。固定计划与种子可重现输入；生成大数据放在题目目录之外。

[性能记录](../../../docs/benchmark-R30.json)保留每份正式输入和源码的哈希、五轮时间及峰值工作集。所有交付方案均通过完整数据。214 个小输入与逐层前缀计数或精确整数组合数一致；全部正式输入另用精确组合数核验。