同一骨架 2025 年福建预赛 · P006318
两题都要追踪首次到达边界的时刻，终点信息本身不能保证此前路径合法。固定终止时刻时，应先限制前面所有状态仍在允许区域，再让最后一步进入边界；计数与概率的区别在于后者须保留题中各步的实际权重。
前题统计受下边界限制的正负步路径；后题有两个吸收边界及停留步，路径需要按给定胜负和局概率加权。
培玉 · 一试
2021 年重庆预赛
F3填空题经典的计数模型
已知 ，，并且
则有序数组 的组数为。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
把 看成格路的上、下步；总和条件会先确定最后一步，再化为标准卡特兰计数。
想想一道相关的题
先回想这道题的想法，再试试当前题。
解答
第 个部分和非负，而加上 后为 ，故
前 项恰有 个 和 个 ，且每个部分和非负。 由反射原理，组数为
复核
每个合法的前 项后只能接一个 ，故与原题数组一一对应。
方法总结
序列的非负部分和是标准卡特兰模型；先用总和确定末项，可把奇数长度化为偶数长度路径。
为什么评为 F3（会透露解法方向）
先由末步迫使前2020项总和为0，再把非负部分和数组归入平衡路径并用反射原理排除越界路径。
联系 · 2 条
易混 2026 年上海预赛 · P006134
两题的正负步数都可由总步数与净位移确定，但固定终点与全过程不越界给出的合法集合不同。仅有位移条件时选择正步位置即可；增加所有前缀限制后，必须再用反射等双射剔除越界路径，不能沿用同一个二项式计数。
前题只约束最终位移；后题把最后一步与此前的非负部分和分开，前缀约束是额外的实质限制。
已记下，谢谢！