# 某不科学的单调序列的首项加权和: 题解

## 方法与贡献

出题人解法已经给出组合数公式，并把两项共用的分子连乘合并。Codex（GPT-6）补齐计数证明，使用组合数对称性缩短小值域情况下的连乘。首选程序为 [std.cpp](std.cpp)；共用乘积方案保留在 [alternative.cpp](alternative.cpp) 和[补充题解](solution-alternative.zh.md)。两份程序均支持完整范围。

## 数量与首项之和

令 $A$ 为合法序列数量。把每个编号的出现次数写成 $m$ 个非负整数，其和为 $n$ .隔板法给出

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

令 $B$ 为所有合法序列首项之和。每个序列的首项 $x_1$ 可以视为可选整数 $y\in[1,x_1]$ 的数量。这样每个“序列与选择”恰好对应一个长度为 $n+1$ 的非递减序列 $(y,x_1,\ldots,x_n)$ ，故

$$B=\binom{n+m}{n+1},\qquad \mathrm{Answer}=kB+cA\pmod p$$

这一双射同时解释常数项与首项的贡献，长度一也无需特别修改。$m=0$ 时先输出零，不构造上述以编号出现次数为基础的组合模型。

## 首选：对称乘积

对每个组合数 $\binom{a}{b}$ ，先令 $t=\min(b,a-b)$ ，再计算

$$\binom{a}{b}=\frac{(a-t+1)(a-t+2)\cdots a}{t!}$$

分子、分母分别逐项取模，用快速幂 $(t!)^{p-2}$ 求逆。这里两次计算的 $t$ 均不超过 $n+1\le10000001<p$ ，因此分母一定可逆。上标 $a$ 可以大于等于 $p$ ：分子出现 $p$ 的倍数时结果为零，仍然正确。不能直接计算 $a!$ 再取逆，也不能约掉可能为零的相邻组合数。

模内乘法用有符号 64 位整数。单次两个模数内因子的积小于 $p^2$ ；两项最终加权之和也小于 $2\times10^9p<2^{63}$ .

## 正确性、复杂度与选择

隔板法和双射分别计算 $A,B$ ；合法的分母逆元精确计算这两个整数的模值；最后线性组合即所求总和。

令 $t=\min(n+1,m-1)$ （此处 $m\ge1$），首选时间为 $O(t+\log p)$ ，辅助空间 $O(1)$ .共用乘积方案时间为 $O(n+\log p)$ 、空间 $O(1)$ .小值域时首选减少循环次数；值域很大时，共用乘积减少重复乘法，具有常数开销优势，作为并列实用方案。不能仅依据渐进式判断某一输入上的实际快慢。

## 数据生成与验证

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

[性能记录](../../../docs/benchmark-R30.json)保留每份正式输入和源码的哈希、五轮时间及峰值工作集。所有交付方案均通过完整数据。312 个小输入与独立序列枚举或精确整数组合数一致；完整范围比较两份程序，并单独核对零值、单一编号和跨模数边界。