No.025 D

$H = 1$ の場合を考える.

DP で考えると, $i$ 列にはコンセントを刺さない/刺すの2パターンある. ここで言うコンセントを刺すとは, $i$ 列目に左側のプラグを刺すことを表す. 以下も同様である.

このときの組み合わせの数の列を $x_i$ とすると, $x_i$ は $x_{i-1}$ を使って $x_i = P_i x_{i-1}$ と表すことができる.

ここで, $P_i$ は $i$ 列目と $i+1$ 列目のコンセントキャップ (以下キャップ) の状態に依存する. $i$ 列目と $i+1$ 列目にキャップがない状態の場合は,

$$P_i = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$$

となり, $P_i$ の $j$ 行目を $P_{i,j}$ とすると, キャップの状態によって次のようになる.

• $P_{i,1}$ はキャップの状態の影響を受けない.
• $P_{i,2}$ は $i$ 列目か $i+1$ 列目にキャップがあれば $(0\ 0)$ となる.

なお, $W+1$ 列目には常にキャップがあると考える.

次に $H = 2$ の場合を考える.

$H = 1$ の場合と同様に, $i$ 列にはコンセントを刺さない/縦に刺す/1行目だけ横に刺す/2行目だけ横に刺す/1,2行目に横に刺すの5パターンがある.

このときの組み合わせの数の列を $y_i$ とすると, $y_i$ は $y_{i-1}$ を使って $y_i = Q_i y_{i-1}$ と表すことができる.

ここで, $Q_i$ は $i$ 列目と $i+1$ 列目のキャップの状態に依存する. $i$ 列目と $i+1$ 列目にキャップがない状態の場合は,

$$Q_i = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \end{pmatrix}$$

となり, $Q_i$ の $j$ 行目を $Q_{i,j}$ とすると, キャップの状態によって次のようになる.

• $Q_{i,1}$ はキャップの状態の影響を受けない.
• $Q_{i,2}$ は $i$ 列目にキャップがあれば $(0\ 0\ 0\ 0\ 0)$ となる.
• $Q_{i,3}$ は1行目の $i$ 列か $i+1$ 列にキャップがあれば $(0\ 0\ 0\ 0\ 0)$ となる.
• $Q_{i,4}$ は2行目の $i$ 列か $i+1$ 列にキャップがあれば $(0\ 0\ 0\ 0\ 0)$ となる.
• $Q_{i,5}$ は $i$ 列か $i+1$ 列にキャップがあれば $(0\ 0\ 0\ 0\ 0)$ となる.

どちらの場合も行列の総乗を計算するセグメントツリーにキャップがない状態の行列を入れておき, クエリごとにこれを更新して組み合わせの数を求める.

部分点2はこの方法で可能だが, 満点は $W$ がかなり大きいためもうひと工夫が必要となる.

そこでクエリを先読みして座標圧縮をする. キャップはその前の列までしか影響を与えないので, キャップの影響を受けない列はひとまとめにできる.

行列をひとまとめにするには繰り返し二乗法が使える.