← 返回题目列表

Codeforces · 575/H

H. 机器人

中文机器翻译题面 查看原题

Sasha 和 Ira 是两个最好的朋友。但他们不仅仅是朋友,他们还是软件工程师和人工智能专家。他们正在开发一种算法,让两个机器人玩两人游戏。该游戏是合作和回合制的。在每个回合中,其中一名玩家会采取行动(无论是哪个玩家,玩家的回合可能不会交替)。

Sasha 和 Ira 正在开发的机器人算法通过跟踪游戏所处的状态来工作。每次机器人移动时,状态都会发生变化。而且,由于游戏非常动态,它永远不会回到过去任何时候已经处于的状态。

Sasha 和 Ira 是完美主义者,希望他们的算法具有最佳获胜策略。他们注意到,在最佳获胜策略中,两个机器人各自精确地进行了 N 步。但是,为了找到最佳策略,他们的算法需要分析游戏的所有可能状态(他们还没有了解 alpha-beta 修剪)并选择最佳的移动顺序。

他们担心算法的效率,并想知道需要分析的游戏状态总数是多少?

输入

第一行也是唯一一行包含整数 N。

- 1 ≤ N ≤ 106

输出

输出应包含一个整数 - 可能状态的数量以 109 + 7 为模。

示例

输入 #1

2

输出 #1

19

注意

开始:游戏处于状态A。

- 第 1 回合:任一机器人都可以移动(第一个机器人为红色,第二个机器人为蓝色),因此第一回合后有两种可能的状态 – B 和 C。
- 第 2 回合:在状态 B 和 C 中,任一机器人都可以再次进行回合,因此可能的状态列表扩展为包括 D、E、F 和 G。
- 第 3 回合:红色机器人在状态 D 时已经进行了 N=2 次移动,因此它无法再进行任何移动。它可以在状态 E、F 和 G 时进行移动,因此将状态 I、K 和 M 添加到列表中。同样,蓝色机器人在 G 状态时无法移动,但在 D、E 和 F 状态下可以移动,因此添加了 H、J 和 L 状态。
- 第4回合:红色机器人在H、I和K状态下已经进行了N=2次移动,因此它只能在J、L和M状态下移动,因此添加了P、R和S状态。蓝色机器人在 J、L 和 M 状态时无法移动,而只能在 H、I 和 K 状态下移动,因此添加了 N、O 和 Q 状态。

总的来说,他们的算法需要分析 19 种可能的游戏状态。