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

方法与贡献¶

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

数量与首项之和¶

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

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