No.936 Are

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 11
作問者 : leafirbyleafirby / テスター : otamay6otamay6
0 ProblemId : 3689 / 出題時の順位表
問題文最終更新日: 2019-12-07 23:42:41

2019/11/30 1:21分追記)想定解が間違っていた為リジャッジを行いました。申し訳ございません。

問題文

$Iot$くんと高橋くんは"アレ"をしています。
"アレ"のルールは以下の通りです。 高橋くんと$Iot$くんの指はそれぞれの手に$5$本ずつあります。
ただし、説明を簡単にする為に$Iot$くんの左手と右手の立っている指の本数を$(L_1,R_1)$、同様に高橋くんは$(L_2,R_2)$とする。

  1. 先攻、後攻を決める。
  2. 先攻が攻撃か、分割する。

    攻撃-相手の立っている本数が$0$でないどちらかの手に自身の立っている本数が$0$でないどちらかの手の立っている指の本数分だけ指を立たせる。
    その結果,相手が立てなければならない指の本数を$5$で割った余りが実際に相手が立たせる指の本数である。
    たとえば、高橋くんが$(2,4)$のとき、$3$で右手を攻撃すると高橋くんは$(2,2)$となる。

    分割-自身の$(L,R)$を再分配する。($5$の剰余を取ってから再分配しても良い。)
    このとき、再分配後の$(L,R)$を$(L',R')$とすると、$L+R=L'+R'$または$(L+R)>5$のとき、$(L+R)≡L'+R'(mod5)$を満たさなければならない。
    また、分配後,各指に分配したものの$5$で割った余りを立てる。
    ただし、$R'=L$かつ$L'=R$のように、入れ替えただけの操作は認めない。(もちろん$R'=R$かつ$L'=L$も認められない。)
    たとえば、$(2,1)→(3,0)$,$(3,4)→(1,1)$は認められるが$(3,3)→(3,3)$は認められない。
    また、$(1,4)→(0,0)$のように自滅することはできない。
  3. 後攻が同様に攻撃か分割する。
  4. $L+R$が$0$になった時点で$0$になった方が負けとなる。そうでなければ、$2$に戻る

現時点で$Iot$君の右手の立っている指の本数が$L_1$本、左手が$R_1$本,
高橋君の右手の立っている指の本数が$L_2$本、左手が$R_2$本です。
高橋君は、このターンで勝てる手がある場合必ずその手を取ります。
また、高橋君は次の相手のターンで負けるような行動は可能な限り取りません。(ただし、次の次の相手のターンまで読んでいる訳ではないことに注意してください。)
この時$Iot$君が$K$ターン以内に勝利する方法は何通りあるか$10^9+7$で割ったあまりを求めてください。
ただし、ここでは先行が奇数ターンに、後攻が偶数ターンに行動するものとします。(先攻、後攻については下記の制約を参照してください。)

入力

$N$ $K$
$L_1\ R_1\ L_2\ R_2$

入力は空白区切りで与えられる。
$N$は$0$か$1$かのどちらかである。
$N=0$の時、次に行動するのはIot君であり、$N=1$の時、次に行動するのは高橋君である。
$0\le L_1,R_1,L_2,R_2\le 4$
$L_1=R_1$のとき、$L_1≠0$
$L_2=R_2$のとき、$L_2≠0$
$0< K \le 20000$

出力

答えを$10^9+7$で割った余りを出力して、最後に改行を出力して下さい。

サンプル

サンプル1
入力
0 9 
1 1 1 1
出力
1112

$Iot$君が先攻のとき、最短$9$ターンで勝つことができます。

サンプル2
入力
1 20000
4 0 1 1
出力
0

$Iot$くんは$1$ターン目に必ず負けます。

サンプル3
入力
1 20000
1 2 2 1
出力
135466068

答えを$10^9+7$で割った余りを出力することに注意してください。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。