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


可复制的 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