← 返回题目列表

AtCoder · joisc2018_d

D. 禁欲主义

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

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

修行 (Asceticism) - 原题 PDF 第 1 页
原题PDF第1页
修行 (Asceticism) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 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