概要

命名にあたって rack up という動詞を私は初めて知りました．

小課題 $1$ は全探索を用いて解くことができます．
小課題 $2$ において AC を得るためには，少し視点を変えてみる必要があるかもしれません．

問題原案：kusirakusira
改題：FplusFplusF, uni_kakurenbo

解説

小課題 $1$

現実的な実行時間で $4^K$ 通りをシミュレーションすることは難しいので，代わりに各 $i \scriptsize \; (1 \leq i \leq N)$ について，最終的に 点 $i$ に至るような移動経路の個数を求め，それに $P_i$ を掛けたものを合計することを考えましょう．

題中の $4$ つの向きへの移動はそれぞれ 左, 右, 下, 上 への移動と呼ぶことにします．

原点から 座標 $(x', y')$ に至る，長さ $K$ の経路がいくつあるか考えます．

それぞれの方向への移動が $l, r, d, u$ 回ずつあったとします． このとき，以下がすべて成り立ちます：

• $l + r + d + u = K$
• $r - l = x'$
• $u - d = y'$

この $3$ つの連立式は $4$ つの元を持つので，どれか $1$ つの元を固定すると他 $3$ つの元は一意に定まります．
ここでは $u$ を固定してみます．

また，上式の辺々を足し合わせることによって以下を得ます：

• $2(u + r) = K + x' + y'$

$t = \frac{1}{2}(K + x' + y')$ とすると，$r = t - u$ と表されます．

以上を用いて，

• $l = t - u - x'$
• $r = t - u$
• $d = u - y'$

と $l, r, d$ を $K, x, y, u$ によって表すことができました．

また，$4$ 方向へそれぞれ $l', r', d', u'$ 回移動するような経路の総数は以下のように表されます：

• $\displaystyle \frac{(l' + r' + d' + u')!}{l'! \, r'!\, d'!\, u'!}$

移動回数は非負の整数であることを考えると，結局，この問題の答えは以下に等しいことが分かります：

• $\displaystyle \Large \sum_{\substack{1 \leq i \leq N \\ 0 \leq u \leq K \\ 2 t_i \equiv 0 \pmod 2 \\ 0 \leq l_i(u), r_i(u), d_i(u) \leq K}} \!\!\!\!\!\!\!\!\! P_i \, \frac{K!}{l_i(u)!\, r_i(u)!\, d_i(u)!\, u!}$
  • ただし
    • $t_i = \frac{1}{2}(K + X_i + Y_i)$
    • $l_i(u) = t_i - u - X_i$
    • $r_i(u) = t_i - u$
    • $d_i(u) = u - Y_i$

この値は，答えの法を $P$ として， $\Theta((N + \log P)K)$ 時間などで求めることができます．

おまけ

$0 \leq l, r, d, u \leq K$ という条件ですが，実は $0 \leq l, r, d, u$ だけで十分です．

• $0 \leq l, r, d \therefore 0 \leq l + r + d \Leftrightarrow 0 \leq K - u \Leftrightarrow u \leq K$
• $0 \leq l, r, u \therefore 0 \leq l + r + u \Leftrightarrow 0 \leq K - d \Leftrightarrow d \leq K$
• $0 \leq l, d, u \therefore 0 \leq l + d + u \Leftrightarrow 0 \leq K - r \Leftrightarrow r \leq K$
• $0 \leq r, d, u \therefore 0 \leq r + d + u \Leftrightarrow 0 \leq K - l \Leftrightarrow l \leq K$

から従います．

小課題 $2$

※以下の解説中では度々 $t$ の文字が登場しますが，前項の $t$ とは別物ですのでご注意ください．

ベースとなるアイディアは Easy と変わらず，最終的に 点 $i$ に至るような移動経路の個数に $P_i$ を掛けたものを合計することを考えます．

以下の問題を高速に解く方法を考えてみましょう：

• 原点から 座標 $(X, Y)$ に至る，長さ $K$ の経路は何通りあるだろうか？

MojaMoja 君の座標を $(x', y')$ とします．
すると，どの方向に $1$ 回移動しても $(x' + y') \bmod 2$ の値は変化することが分かりま す．
ゆえに $(X + Y) \not\equiv K \pmod 2$ である場合，答えは $0$ です．

また明らかに，$X + Y > K$ である場合も到達は不可能なため，答えは $0$ です．

さらに，「原点から $(X, Y)$ に至る，長さ $K$ の経路の個数」と「原点から $(-X, Y)$ に至る，長さ $K$ の経路の個数」や「原点から $(X, -Y)$ に至る，長さ $K$ の経路の個数」はすべて一致しますから，$0 \leq X$ かつ $0 \leq Y$ としても一般性は保たれます．

したがって，以下では $0 \leq X, Y$ かつ $X + Y \leq K$ かつ $X + Y \equiv K \pmod 2$ である場合のみを考えます．

ここで，もし $X + Y = K$ であるならば，簡単に答えが求まることに着目します．
$X + Y = K$ であるときとそうでないときに分けて考えてみましょう．

$X + Y = K$ のとき

原点から $(X, Y)$ へ至る最短経路の個数が答えであるので，$X$ 個の → および $Y$ 個の ↑ を一列に並べるときの並べ方が何通りあるかを考えればよく，答えは $\begin{pmatrix} K \\ X \end{pmatrix}$ 通りです．

• なお $\begin{pmatrix} \cdot \\ \cdot \end{pmatrix}$ は二項係数であり，任意の $2$ 非負整数 $n, r$ に対して $\displaystyle \begin{pmatrix} n \\ r \end{pmatrix} = \frac{n!}{r! (n - r)!}$ が満たされる．

$X + Y < K$ のとき

うまく $X + Y = K$ の場合を利用できないでしょうか？

ここでは以下の事実に注目してみましょう：

• $x + y \leq k$ かつ $x + y \equiv k \pmod 2$ なる任意の $3$ 非負整数 $x, y, k$ に対して，$(x, y)$ は $x' + y' = k$ なる $3$ 非負整数 $x', y', t$ を用いて $(x, y) = (x' - t, y' - t)$ と表すことができる．
• また，このとき $2t = k - (x + y)$ である．

これは次のように証明できます：

• $f(x, y) = x + y$ とする．
• $f(x + t, y + t) = f(x, y) + 2t$ であり，$f(x, y) \leq K$ かつ $f(x, y) \equiv f(x + t, y + t) \pmod 2$ であることから，このような非負整数 $t$ は必ず存在する．
• なお，$2t = k - (x + y)$ であることは以上の議論から明らか．

さて，$(X, Y) = (X' - t, Y' - t) \scriptsize \; (X' + Y' = K)$ と表されるとき，「原点から $(X, Y)$ に至る，長さ $K$ の経路」は何通りあるでしょうか．

少し考えると，これは以下の問題の答えに一致することが分かります：

• 『原点から $(X', Y')$ へ至る最短経路 (→, ↑ の並び) にそれぞれに対して，「→ を ↓ に置き換えるか，↑ を ← に置き換える」という操作をちょうど $t$ 箇所について行ったとき，最終的な ←, →, ↑, ↓ の並び方は何通りあるだろうか．』
  • 置き換えを行う前の移動経路 (→, ↑ の並び) は相異なるので，その相異なる $2$ 文字 →, ↑ をそれぞれまた相異なる ↓, ← に置き換える操作によって得られる ←, →, ↑, ↓ の並びも，同様に相異なることが分かる．

ここで，置き換えを行う $t$ 箇所の選び方は $\begin{pmatrix} K \\ t \end{pmatrix}$ 通りありますから，$X' = X + t$ であることを踏まえると，はじめの問題に対して $X + Y < K$ のときの答えは次のように表されます：

• $\begin{pmatrix} K \\ X + t \end{pmatrix} \begin{pmatrix} K \\ t \end{pmatrix}$

なお，$X + Y = K$ のとき $t = 0$ であることから，この結果は，$X + Y = K$ の場合についても成り立ちます．

以上の議論を総じて，結局，この問題を，答えの法を $P$ として，$\Theta(N + K \log P)$ 時間などで解決できることがわかりました．

おまけ

この問題においては，$\sum_{\phi} \Phi_{\phi}(K) \leq 10^5$ という制約がありますから，テストケースごとに $O(N + K)$ 時間程度をかけることが可能ですが，$\Phi$ 個のテストケースに答える前に，$1 \leq k \leq$ なるすべての $k$ について $k!$ の値をあらかじめ求めておくことで，答えの法を $P$ として，この前計算に $\Theta(K \log P)$ 時間，各テストケースの処理に $\Theta(N)$ 時間 などで解くことができます．

解説：uni_kakurenbo

実装例