易混 2021 年重庆预赛 · P006945
两题的正负步数都可由总步数与净位移确定,但固定终点与全过程不越界给出的合法集合不同。仅有位移条件时选择正步位置即可;增加所有前缀限制后,必须再用反射等双射剔除越界路径,不能沿用同一个二项式计数。
前题只约束最终位移;后题把最后一步与此前的非负部分和分开,前缀约束是额外的实质限制。
固定步长数列的端点计数
在数列 中,,且对任意 ,有
则满足要求的数列有个。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
十四次相邻变化每次只能是 或 。
端点差确定两种步数,之后只需选择正步所在位置。
设十四次变化中有 次为 ,有 次为 。则
解得
任意选定九个位置放置正步,其余位置放置负步,就唯一确定一个满足条件的数列。因此 数列总数为
九次正步和五次负步的总变化为 ;反过来每个数列都对应唯一的正步位置集合, 所以没有重复或遗漏。
固定步长的数列计数可视为一维格路。先由总步数和净位移解出正、负步数,再用组合数 选择其中一种步的位置。
末项差确定14步中九步向上、五步向下,任选五个负步位置就唯一确定数列。
易混 2021 年重庆预赛 · P006945
两题的正负步数都可由总步数与净位移确定,但固定终点与全过程不越界给出的合法集合不同。仅有位移条件时选择正步位置即可;增加所有前缀限制后,必须再用反射等双射剔除越界路径,不能沿用同一个二项式计数。
前题只约束最终位移;后题把最后一步与此前的非负部分和分开,前缀约束是额外的实质限制。
已记下,谢谢!