机场问题

实际上就是27日在萧山机场等航班的时候gwj问我的问题,不知道取什么标题好,就取了这个标题……
问题如下:
考虑一个长度为n的环,环上分布着n个点,相邻两点距离为1。顺时针依次标号为0,1,...,n-1,n号点就是0号点
现在有一只青蛙在0号点。它每次可以顺时针跳1长度单位或跳2单位长度。(不能逆时针跳)
现在它想绕这个环恰好两圈,也即从0号点开始顺时针总共跳恰好2n单位长度。
而因为这只青蛙脑洞比较大,它定了以下规则:
如果它第一次跳到i号点后,下一步选择的是跳1单位长度,那么如果它第二次跳到了i号点,下一步就只能选择跳2单位长度。
如果它第一次跳到i号点后,下一步选择的是跳2单位长度,那么如果它第二次跳到了i号点,下一步就只能选择跳1单位长度。
现在问它恰好绕两圈的跳法方案数。
例如当n=3的时候。
0->1->3(0)->2->3(0)
就是一条合法路径
而0->1->3(0)->1->2->3(0)
不是一条合法路径。
因为第一次在0号点选择的是走到1号点(1单位长度),而第二次在0号点也是选择走到1号点。

SOL

gwj跟我说过这个有一个非常简单的递归式……定义为长度为n时的答案。
那么大概有(毕竟是三天前飞机上讲的,记不太清楚了)

大概是这样?

总之我没想出来这个递归式的比较好的组合解释(而且我也不确定它的正确性)

所以现在来暴力推导吧!

路径总共有两种可能:
从0开始走一圈恰好回到0,然后再走一圈回到0
或者从0开始走一直走到n-1,然后从n-1跳到1,然后再从1走回0
好困……还是明天再继续推吧……

(5.4已坑……更新时间不定……

update on 5.9

xyz怂恿我来填坑。
我就来写写我当时飞机上yy的做法吧。

排版渣注意。
各种分类讨论注意。
语文渣注意。


我有特别的弃坑技巧。。。

首先设这题的答案为。。。我们的最终目标是得到它的递推式子。

显然的只有或者这两种路线。

考虑分别计数。

子任务1

先讨论这条路线。

实际上我们相当于要找到这样的一对路线

其中是一条的路线,是一条的路线,并且满足在点的时候,如果路线都经过点,则在该点时下一步的决策不同。

定义这样的路线对数在环长度为的时候为

简洁起见,我们定义表示这样的路径对数:满足是一条的路径,是一条的路径,并且满足在点的时候,如果路线都经过点,则在该点时下一步的决策不同。

所以

显然地n=2的时候为=1(边界条件)

然后考虑路线的可能性。

第一种可能是第一步前进一步,那么是,第二种情况是

那么继续考虑第一种情况。。。就是

定义这样的路线对数在环长度为的时候为

那么考虑路线的可能性。

最后一步要么是,要么是

如果是,那就相当于一对的路线,并满足决策不同要求。。。

现在请翻到页首。。你会发现我们一开始讨论的两种情况的第二种就是找一对的路线,并满足决策不同要求。。

所以现在追加定义:

如果是,那就相当于一对的路线,这个的数目是

所以有递推式:

子任务1的另一种情况是

实际上也是

那么继续分类讨论推。(我分类讨论都要分到哭了)

路线第一步要么是,那么就是,参考一下的定义。。。会发现这就是

否则就是,那么就,也就是,参考一下定义,会发现这个是

整理一下,至此情况1分类讨论结果如下:

递推式未知。

子任务2

现在的目标是推出也就是

依旧采取分类讨论的方式。。。

因为路径的决策不能重复,所以路径的第一步只有两种可能:

第一步前进1格,第一步前进2格。

第一步前进2格,第一步前进1格。

容易发现这两种情况是对称的。

也就是说

稍微思考一下会发现有等式

所以说

综上我们有递推式:

边界值待补充中。。。

最后yy一下会发现

当然这个的推导得等我边界值弄完再说了。。。

很容易发现这个推导是不怎么费脑子的,就是分类讨论特别繁琐罢了。
但是我也懒得想(继)简(续)单(填)做(坑)法了。

Comments

comments powered by Disqus