小杜又在玩游戏了！这回他玩的是跑酷游戏！
小杜又在玩游戏了！这回他玩的是跑酷游戏！ 已知该跑酷地图长为n，有3层，可以理解为一张3×n的地图。令人新奇的是，这张跑酷地图有一些弹射机关。假设玩家现在位置为(x,y)(x,y)(x,y)。 每一秒钟，如果玩家没有踩到机关，玩家可以正常向前移动一格；如果玩家踩到机关，即当前玩家位置上存在一个机关，弹射机关会立即随机触发以下一种状态： 1. 上升：将玩家向上向前弹射一格，即将玩家瞬间移动到(max(1,x−1),y+1)( max(1,x-1) , y+1 )(max(1,x−1),y+1)； 2. 跳跃：将玩家向前弹射两格，即将玩家瞬间移动到(x,min(n,y+2))( x , min(n,y+2) )(x,min(n,y+2))； 3. 下降：将玩家向下向前弹射一格，即将玩家瞬间移动到(min(3,x+1),y+1)( min(3,x+1) , y+1 )(min(3,x+1),y+1)。 如下图所示。 已知小杜起始位于(1,1)(1,1)(1,1)，求小杜最终到达(1,n)(1,n)(1,n), (2,n)(2,n)(2,n), (3,n)(3,n)(3,n)的方案数（对998244353取模）。 （如果两种方案被认为是不同的，那么至少存在一个机关，触发的状态不同）
标签： HBC247497对称二叉树 数据结构 树 搜索减枝 搜索小杜跑酷题解
