問題一覧 > 通常問題

No.213 素数サイコロと合成数サイコロ (3-Easy)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 128 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 52
作問者 : LayCurseLayCurse
1 ProblemId : 443 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:32

問題文

素数サイコロとはそれぞれの面に 2,3,5,7,11,13 の整数が書かれているサイコロである。
合成数サイコロとはそれぞれの面に 4,6,8,9,10,12 の整数が書かれているサイコロである。
あるスゴロクでは、0 のマスからスタートし、N のマスに辿り着いたらゴールである。
各ターン、P 個の素数サイコロと C 個の合成数サイコロを振り、出た目の和を x として、今いるマスが k ならば min(k+x,N) のマスに移動する。
それぞれ素数サイコロと合成数サイコロは区別できないとして、ゴールする方法のパターン数を mod 1000000007 (109+7) で求めるプログラムを書いて下さい。

入力

N P C

1N1000000000000000000=1018
0P5
0C5
P+C1

出力

ゴールする方法パターン数 mod 1000000007 を出力して下さい。
出力した後には改行して下さい。

サンプル

サンプル1
入力
1 1 1
出力
36

1 ターンで必ずゴールできます。
素数サイコロがどの目が出るか、合成数サイコロがどの目が出るかで 6×6=36 パターンあります。

サンプル2
入力
1 2 0
出力
21

サンプル1と同様に 1 ターンで必ずゴールできます。
しかし、素数サイコロは区別できないので、2 つの素数サイコロの出目は (2,2),(2,3),(2,5),(2,7),(2,11),(2,13),(3,3),(3,5),(3,7),(3,11),(3,13),(5,5),(5,7),(5,11),(5,13),(7,7),(7,11),(7,13),(11,11),(11,13),(13,13)21 パターンになります。

サンプル3
入力
5 2 0
出力
41

最初の出目が (2,2) でない 20 通りの場合は、1 ターンでゴールできます。
最初の出目が (2,2) であれば、もう 1 ターンかかり、2 ターン目の出目は 21 パターンあります。

サンプル4
入力
6 2 0
出力
61

最初の出目が (2,2),(2,3) でない 19 通りの場合は、1 ターンでゴールできます。
最初の出目が (2,2),(2,3) であれば、もう 1 ターンかかり、2 ターン目の出目はそれぞれ 21 パターンずつあります。

サンプル5
入力
1 5 5
出力
63504

必ず 1 ターンでゴールできますが、サイコロの出目のパターンの数はそんなに小さくありません。

サンプル6
入力
100000 4 5
出力
906961798

頑張るのじゃ。ほっほー。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。