某不科学的单调序列计数: 补充解法¶

Pascal 递推：出题人解法¶

alternative.cpp 计算主解证明的组合数。令 \(a=n+m-1\) 、\(t=\min(n,m-1)\) ，初始 \(C_0=1\) ，其余为零。对行号 \(i=1,\ldots,a\) ，按 \(j=\min(i,t),\ldots,1\) 倒序更新

\[ C_j\leftarrow C_j+C_{j-1}\pmod p \]

更新前两个值都来自上一行，正是 Pascal 恒等式。倒序保证 \(C_{j-1}\) 尚未被覆盖；每行完成后 \(C_j=\binom{i}{j}\) ，因此最后 \(C_t\) 为答案。\(t=0\) 时始终为一。

时间 \(O((n+m)t)\) ，辅助空间 \(O(t)\) .此法只做加法，不依赖质数或逆元，支持完整数据；本题首选乘积法减少运算和存储。Codex（GPT-6）把出题人的二维表改为滚动数组，保留同一递推。