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


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