No.612 Move on grid

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 60
作問者 : りあんりあん / テスター : tsutajtsutaj
1 ProblemId : 2004 / 出題時の順位表
問題文最終更新日: 2017-12-01 18:50:27

いつもの

Python では想定解法で TLE したので、PyPy で提出することをお勧めします。

問題文

3 次元グリッド上を点 $P$ が以下の規則に従って動きます。

  • 最初、時刻 0 において点 $P$ は原点 $(0, \ 0, \ 0)$ にある。
  • 時刻 $t$ において点 $P$ が格子点 $(x, \ y, \ z)$ にあるとき、時刻 $t + 1$ での点 $P$ の位置は、隣接する格子点
    • $(x + 1, \ y, \ z)$
    • $(x, \ y + 1, \ z)$
    • $(x, \ y, \ z + 1)$
    • $(x - 1, \ y, \ z)$
    • $(x, \ y - 1, \ z)$
    • $(x, \ y, \ z - 1)$
    のいずれかであり、また、これらの点に移動する確率は、それぞれ $\displaystyle \frac{1}{6}$ である。

このとき、点 $P$ の時刻 $T$ における座標 $(x, \ y, \ z)$ が $ \ d \leq ax + by + cz \leq e \ $ を満たす確率を $p$ とおくと、$6^T \times p$ は整数になります。

$6^T \times p$ を $10^9 + 7$ で割った余りを求めてください。

入力

$T$
$a$ $b$ $c$ $d$ $e$

1 行目に、問題文中に示された時刻 $T$ が与えられます。

2 行目に、問題文中の条件を表すパラメータ $a$, $b$, $c$, $d$, $e$ がこの順で半角スペース区切りで与えられます。

入力は全て整数で、以下の制約を満たします。

  • $1 \leq T \leq 500$
  • $|a|, \ |b|, \ |c| \leq 20$
  • $(a, \ b, \ c) \neq (0, \ 0, \ 0)$
  • $-10000 \leq d \leq e \leq 10000$

出力

$6^T \times p$ を $10^9 + 7$ で割った余りを出力してください。最後に改行してください。

サンプル

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

時刻 1 に 3 次元空間上の $x = 1$ という平面上にいれば良いので、$(1, 0, 0)$ に移動した場合に成立します。

確率は $\displaystyle \frac{1}{6}$ なので、 $\displaystyle 6 \times \frac{1}{6} = 1$ が答えになります。

サンプル2
入力
3
-2 0 0 -4 2
出力
202

サンプル3
入力
6
1 -1 0 0 0
出力
9024

サンプル4
入力
120
12 -1 2 -1212 1212
出力
504758737

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