No.214 Prime Dice and Composite Dice (3-Medium)
タグ : / 解いたユーザー数 40
作問者 :
LayCurse
Problem Statement
A prime die is a die whose faces have the integers \(2,3,5,7,11,13\) written on them.
A composite die is a die whose faces have the integers \(4,6,8,9,10,12\) written on them.
In a certain sugoroku game, you start at square \(0\) and reach the goal when you arrive at square \(N\).
Each turn, you roll \(P\) prime dice and \(C\) composite dice. Let \(x\) be the sum of the rolled values; if you are currently at square \(k\), you move to square \(\min(k+x, N)\).
Treating the prime dice as indistinguishable from each other and the composite dice as indistinguishable from each other, write a program that computes the number of patterns of ways to reach the goal, \({\rm mod}\ 1000000007\ (10^9+7)\).
Input
$N$ $P$ $C$
\(1 \leq N \leq 1000000000000000000 = 10^{18}\)
\(0 \leq P \leq 50\)
\(0 \leq C \leq 50\)
\(P + C \geq 1\)
Output
Output the number of patterns of ways to reach the goal, \({\rm mod}\ 1000000007\).
Print a newline after the output.
Sample
Sample 1
Input
1 1 1
Output
36
You always reach the goal in \(1\) turn.
Depending on which face the prime die shows and which face the composite die shows, there are \(6 \times 6 = 36\) patterns.
Sample 2
Input
1 2 0
Output
21
As in Sample 1, you always reach the goal in \(1\) turn.
However, since the prime dice are indistinguishable, the outcomes of the \(2\) prime dice are the \(21\) patterns \((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)\).
Sample 3
Input
5 2 0
Output
41
In the \(20\) cases where the first outcome is not \((2,2)\), you reach the goal in \(1\) turn.
If the first outcome is \((2,2)\), it takes \(1\) more turn, and there are \(21\) patterns for the outcome of turn \(2\).
Sample 4
Input
6 2 0
Output
61
In the \(19\) cases where the first outcome is not \((2,2), (2,3)\), you reach the goal in \(1\) turn.
If the first outcome is \((2,2), (2,3)\), it takes \(1\) more turn, and there are \(21\) patterns each for the outcome of turn \(2\).
Sample 5
Input
1 10 10
Output
9018009
You always reach the goal in \(1\) turn, but the number of patterns of dice outcomes is not so small.
Sample 6
Input
100000 8 12
Output
144097395
Do your best. Ho ho!
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。