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

方法与贡献¶

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

隔板法¶

设编号 \(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 生成输入；可重复使用 --case 选择编号，使用 --std <可执行程序路径> 同时生成输出。先自行以 C++17 编译所需源码。固定计划与种子可重现输入；生成大数据放在题目目录之外。

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