← 返回题目列表

AtCoder · joisc2010_stairs

stairs. 楼梯

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

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

階段 (Stairs) - 原题 PDF 第 1 页
原题PDF第5页
階段 (Stairs) - 原题 PDF 第 2 页
原题PDF第6页
可复制的 PDF 提取文本
Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                             Contest day 1 - Stairs

                            階段(Stairs)


 あなたは,階段の上り方が何通りあるかを調べたくなった.階段はN 段からなり,k(1 ≦k ≦N) 段目の
段差はhk mm である.
 あなたは,段差の和がP mm 以下の段を一度に上ることができる.階段を上るときに,同じ段で足踏み
したり,下ったりはしない.また,用いた段が同じ時に同じ上り方とみなす.

課題(TASK)
 階段の上り方の場合の数の1234567 による余りを求めよ.

制限(CONSTRAINTS)
   1 ≦N ≦500, 000      階段の段数
   1 ≦P ≦500, 000, 000    ジャンプ力
   1 ≦hk                       k 段目の階段の段差
   h1 + · · · + hN ≦500, 000, 000

入力(INPUT)

 標準入力から以下の入力を読み込め.

   • 1 行目には整数N とP が空白を区切りとして書かれている.

   • 続くN 行のうちのk 行目には整数hk が書かれている.

出力(OUTPUT)

 標準出力に以下のデータを出力せよ.

   • 1 行目にはあなたの階段の上り方の場合の数の1234567 による余りを表す,1 つの整数を含んでいな
   ければならない.

採点基準(GRADING)
  50 点分のテストグループにおいて,N は3,000 を超えない.




                                                                                    Page 1 of 2

Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                             Contest day 1 - Stairs

入出力例(EXAMPLE)
  入力例(Sample Input)  出力例(Sample Output)
   6 350               9
   315
   191
   98
   70
   126
   200

 この階段は6 段からなり,上り方は

   • 1, 2, 3, 4, 5, 6

   • 1, 2, 3, 4, 6

   • 1, 2, 3, 5, 6

   • 1, 2, 4, 5, 6

   • 1, 2, 4, 6

   • 1, 2, 5, 6

   • 1, 3, 4, 5, 6

   • 1, 3, 4, 6

   • 1, 3, 5, 6

の9 通りである.ただし,例えば1 段目と3 段目と5 段目を用いて6 段目に上る方法を1, 3, 5, 6 と表して
いる.





                                                                                    Page 2 of 2