← 返回题目列表

AtCoder · joisc2011_keycards

keycards. 卡钥匙(钥匙卡)

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

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

カードキー (Keycards) - 原题 PDF 第 1 页
原题PDF第4页
カードキー (Keycards) - 原题 PDF 第 2 页
原题PDF第5页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                         Contest Day 2 – Keycards

                   カードキー(Keycards)


  JOI の春合宿が行われる施設の宿泊棟の部屋の鍵は,カードに穴がいくつか開いた形状をしている.穴
を開ける位置の候補はN 個あり,これらのうちいくつかに穴を開けた2N 枚の異なる鍵が作られた.
 あなたは,JOI の春合宿のための1 枚以上2N 枚以下の鍵をまとめて受け取った.穴を開ける候補の位置
を合わせて鍵を重ねてみたあなたは,ちょうどK か所,受け取ったすべての鍵に穴が開いている位置があ
ることに気づいた.
 このようなことが起こるような,受け取った鍵の組み合わせは何通りあるだろうか.答えを1 000 000 007
(素数) で割った余りを求めよ.


課題

 N とK が与えられたとき,答えを1 000 000 007 で割った余りを求めるプログラムを作成せよ.


制限

   1 ≦N ≦1 000 000 穴を開ける位置の候補の個数
   0 ≦K ≦N    受け取ったすべての鍵に穴が開いている位置の個数


入力

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

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


出力

 標準出力に鍵の組み合わせの個数を表す1 行を出力せよ.出力の1 行目には,答えを1 000 000 007 で
割った余りを書け.


採点基準

 採点用データのうち,配点の30%分については,N ≦10 を満たす.
 採点用データのうち,配点の70%分については,N ≦1 000 を満たす.





                     カードキー– 1 / 2

Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                         Contest Day 2 – Keycards


入出力の例

 入力例1        出力例1
 3 3                  1

 N = 3 の時,鍵は全部で8 枚存在するが,ここでは以下のように鍵に名前をつける.

                   穴の開き方 名前

                            ϕ
                    ○      A
                     ○     B
                      ○    C
                    ○○    AB
                     ○○    BC
                    ○ ○    AC
                    ○○○   ABC

 たとえばABC という1 枚の鍵だけを受け取った場合,受け取ったすべての鍵に穴が開いている位置の
数は3 か所である.また,それ以外の受け取り方では,受け取ったすべての鍵に穴が開いている位置の数
が3 か所になることはない.したがって,条件を満たす鍵の受け取り方は1 通りである.


 入力例2        出力例2
 3 2                  6

  {AB, ABC} という2 枚の鍵を受け取った場合,受け取ったすべての鍵に穴が開いている位置の数は2 か
所である.同様に,{AC, ABC}, {BC, ABC}, {AB}, {AC}, {BC} という受け取り方をした場合にも,受け取っ
たすべての鍵に穴が開いている位置の数は2 か所となる.


 入力例3        出力例3
 3 1                  30

 条件を満たす鍵の受け取り方は,{A}, {A, AB}, {A, AC}, {A, ABC}, {A, AB, AC}, {A, AB, ABC}, {A, AC,
ABC}, {A, AB, AC, ABC}, {AB, AC}, {AB, AC, ABC} など30 通りである.


 入力例4        出力例4
 3 0                  218





                     カードキー– 2 / 2