← 返回题目列表

AtCoder · autumn_fest_10

J. 火车忍者

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

配点

満点
140
部分点1
20
部分点2
40

問題文

当尝试乘坐平时上下班乘的电车的相反方向时,车内很空,感觉非常好。这列电车会开到哪里呢……偶然看到窗外整齐排列的电线杆群时,感觉那里似乎站着忍者。

电线杆沿数轴的整数点排列。最初从车窗看,左端为坐标0H看到连续排列的电线杆。在时刻0时,忍者站在坐标0的电线杆上。从0时刻开始,根据以下规则状况发生变化。

  • 忍者站在电线杆上时,必须始终处于车窗投射的范围内。
  • 从车窗可见的范围在速度为1时沿数轴正方向移动。
  • 如果忍者在整数时间站在电线杆上,那么时间[\sqrt{D}]只需花费,就可以沿数轴正方向跳到D个前方的电线杆,或者在原地消失,两者之一。 但是[x],x表示下面的最大整数。
    • D是正整数。
    • 一旦开始跳跃,就会在着陆前悬空。
    • 如果消除了姿势,那么之后它将再也不会出现,也不需要满足其他否定条件。

時刻T而忍者已经消失,也没有悬空。求忍者在满足条件的同时移动的组合个数1000003除以 的余数。注意忍者在时刻0以及T也可以消失。


入力形式

输入以以下格式给出。


H\ T

出力形式

输出组合的个数为一行。

制約

  • 1 ≤ H ≤ 77
  • 0 ≤ T ≤ 777777777
  • 输入值全为整数。

以上为基本否定。

本题的判定设置了20分的测试用例组。该组包含的测试用例除了满足基本否定之外,还满足以下否定条件。

  • 1 ≤ H ≤ 22
  • 0 ≤ T ≤ 22222

本题的判定设置了40分的测试用例组。该组包含的测试用例除了满足基本否定之外,还满足以下否定条件。

  • 1 ≤ H ≤ 22

入力例 1

1 2345

出力例 1

2346

因为忍者跳跃时只能一次跳一根,所以每个时刻的脱离组合各有一种,共2345+1=2346种。


入力例 2

3 1

出力例 2

4

4种情况:0, 0->1, 0->2, 0->3


入力例 3

3 2

出力例 3

11

入力例 4

20 70300

出力例 4

8512

作者:uwi