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


可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 2 – Asceticism
修行(Asceticism)
タイムマシンを手に入れたJOI 君は,約1200 年前の日本に遊びに行くことにした.そこで,JOI 君は,
弘法大師の名で知られる空海が,新たな修行の方法を考えている場に出会った.
空海は,次のような方法で修行をしようとしている.
• 空海はN 個の文からなるお経を読もうとしている.N 個の文には順序が定まっており,空海はその
順に文を読む必要がある.
• それぞれの文には1 以上N 以下の整数が1 つだけ付けられている.ただし,異なる文に同じ整数が
付けられていることはない.
• 整数i (1 ≦i ≦N) が付けられた文は,1 日をN 等分した中でi 番目の時間に読む必要がある.それぞ
れの文はとても短いので,この時間内に文を読み切ることができる.
空海は,ある日の始まりからこの修行を開始し,極力短い日数でこれらの修行を終えたい.しかし文に付
けられている整数によって,何日間必要かは変わってくる.そこで,空海に頼まれたJOI 君は,最短日数
ですべての文を読もうとしたときにK 日間かかるような,文への整数の付け方が何通りあるかを求めるこ
とにした.
課題
お経の文の個数N と,K が与えられたとき,すべて読むのに最短でちょうどK 日間かかるお経に書かれ
た整数の組み合わせの個数を,1 000 000 007 で割った余りを求めるプログラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
• 1 行目には,2 個の整数N, K が空白を区切りとして書かれている.これは,お経がN 個の文からな
り,すべて読むのに最短でちょうどK 日間かかるお経に書かれた整数の組み合わせの個数を求めた
いことを表す.
出力
すべて読むのに最短でちょうどK 日間かかるお経に書かれた整数の組み合わせの個数を,1 000 000 007
で割った余りを出力せよ.
修行– 1 / 2
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 2 – Asceticism
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦100 000.
• 1 ≦K ≦N.
小課題
この課題では小課題は全部で4 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [4 点]
• N ≦10.
小課題2 [20 点]
• N ≦300.
小課題3 [25 点]
• N ≦3 000.
小課題4 [51 点]
追加の制限はない.
入出力例
入力例1 出力例1
3 2 4
すべて読むのに最短でちょうど2 日間かかるお経は,以下の4 通りある.
• 最初の文に1,次の文に3,次の文に2 が付けられている.このとき,1 日目に最初の2 つの文(1 と
3 がそれぞれ付けられている) を読み,2 日目に最後の文(2 が付けられている) を読む.
• 最初の文に2,次の文に1,次の文に3 が付けられている.
• 最初の文に2,次の文に3,次の文に1 が付けられている.
• 最初の文に3,次の文に1,次の文に2 が付けられている.
入力例2 出力例2
10 5 1310354
修行– 2 / 2