No.936 Are
Added 2019/11/30 1:21) The intended solution was incorrect, so a rejudge was performed. We apologize.
Problem Statement
$Iot$ and Takahashi are playing "Are".
The rules of "Are" are as follows.
Takahashi and $Iot$ each have $5$ fingers on each hand.
To simplify the explanation, let $(L_1,R_1)$ denote the numbers of raised fingers on $Iot$'s left and right hands, and similarly let $(L_2,R_2)$ denote those of Takahashi.
- Decide who moves first and who moves second.
- The first player either attacks or splits.
Attack - Choose one of the opponent's hands whose number of raised fingers is not $0$ and one of your own hands whose number of raised fingers is not $0$. The opponent raises as many additional fingers on the chosen hand as there are raised fingers on your chosen hand.
The remainder when the resulting number of fingers the opponent has to raise is divided by $5$ is the number of fingers the opponent actually raises.
For example, when Takahashi has $(2,4)$, attacking his right hand with $3$ makes Takahashi $(2,2)$.
Split - Redistribute your own $(L,R)$. (You may also redistribute after taking the remainder modulo $5$.)
Here, letting $(L',R')$ be the $(L,R)$ after the redistribution, it must satisfy $L+R=L'+R'$ or, when $(L+R)>5$, $(L+R)≡L'+R'(mod5)$.
Also, after the distribution, the remainder modulo $5$ of what was distributed to each finger is raised.
However, an operation that merely swaps the hands, such as $R'=L$ and $L'=R$, is not allowed. (Of course, $R'=R$ and $L'=L$ is not allowed either.)
For example, $(2,1)→(3,0)$ and $(3,4)→(1,1)$ are allowed, but $(3,3)→(3,3)$ is not allowed.
Also, you cannot defeat yourself, as in $(1,4)→(0,0)$.
- The second player likewise either attacks or splits.
- As soon as $L+R$ becomes $0$, the player whose value became $0$ loses. Otherwise, return to step $2$.
Currently, the number of raised fingers on $Iot$'s right hand is $L_1$ and on his left hand is $R_1$,
and the number of raised fingers on Takahashi's right hand is $L_2$ and on his left hand is $R_2$.
If Takahashi has a move that wins on this turn, he always takes that move.
Also, Takahashi avoids, whenever possible, any action that would make him lose on the opponent's next turn. (Note, however, that he does not look ahead as far as the opponent's turn after that.)
Find the number of ways for $Iot$ to win within $K$ turns, modulo $10^9+7$.
Here, the first player acts on odd-numbered turns and the second player acts on even-numbered turns. (For who moves first and second, refer to the constraints below.)
Input
$N$ $K$ $L_1\ R_1\ L_2\ R_2$
The input is given separated by spaces.
$N$ is either $0$ or $1$.
When $N=0$, the next to act is Iot, and when $N=1$, the next to act is Takahashi.
$0\le L_1,R_1,L_2,R_2\le 4$
When $L_1=R_1$, $L_1≠0$
When $L_2=R_2$, $L_2≠0$
$0< K \le 20000$
Output
Output the answer modulo $10^9+7$, followed by a newline at the end.
Sample
Sample 1
Input
0 9 1 1 1 1
Output
1112
When $Iot$ moves first, he can win in a minimum of $9$ turns.
Sample 2
Input
1 20000 4 0 1 1
Output
0
$Iot$ always loses on turn $1$.
Sample 3
Input
1 20000 1 2 2 1
Output
135466068
Note that you must output the answer modulo $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
leafirby
otamay6