BCU30 F - 数列と計算

• 問題
• AC

区間$[l,r)$に関する掛け算$a_l a_{l+1} ... a_{r-1}$が何回足されるかを数えればよい。区間の右端を揃えて数えると下の表のようになる:

1	2	3	4	5
$a_1 \cdot 2^3$	$a_1a_2 \cdot 2^2$	$a_1a_2a_3 \cdot 2$	$a_1a_2a_3a_4 \cdot 1$	$a_1a_2a_3a_4a_5 \cdot 1$
	$a_2 \cdot 2^2$	$a_2a_3 \cdot 2$	$a_2a_3a_4 \cdot 1$	$a_2a_3a_4a_5 \cdot 1$
		$a_3 \cdot 2^2$	$a_3a_4 \cdot 2$	$a_3a_4a_5 \cdot 2$
			$a_4 \cdot 2^2$	$a_4a_5 \cdot 2^2$
				$a_5 \cdot 2^3$

（幅の関係で$N=5$でやったけど、$N=6$くらいのほうがわかりやすいかも）

上の表から、$a_x$を右端とする掛け算の総和から$a_{x+1}$を右端とする掛け算の総和を得るには、だいたい$a_{x+1} / 2$を掛ければよいということがわかる。この係数で帳尻を合わせるために少し改変すると、次のようになる:

0	1	2	3	4	5
$2^4$	$a_1 \cdot 2^3$	$a_1a_2 \cdot 2^2$	$a_1a_2a_3 \cdot 2$	$a_1a_2a_3a_4 \cdot 1$	$a_1a_2a_3a_4a_5 \cdot 1$
	$2^3$	$a_2 \cdot 2^2$	$a_2a_3 \cdot 2$	$a_2a_3a_4 \cdot 1$	$a_2a_3a_4a_5 \cdot 1$
		$2^3$	$a_3 \cdot 2^2$	$a_3a_4 \cdot 2$	$a_3a_4a_5 \cdot 2$
			$2^3$	$a_4 \cdot 2^2$	$a_4a_5 \cdot 2^2$
				$2^3$	$a_5 \cdot 2^3$
					$2^3$

したがって$\operatorname{dp}[0] := 2^{N-1}$で初期化したあと、$\operatorname{dp}[x] := \operatorname{dp}[x-1]\cdot a_{x}/2 + 2^{N-2}$と更新していけばよさそう。ただし、最後だけは$1/2$を掛けずに$\operatorname{dp}[N] := a_{N}\operatorname{dp}[N-1] + 2^{N-2}$とする。

$\operatorname{dp}[1]$から$\operatorname{dp}[N]$までを、不要な$2^{N-2}$を引きながら足していけば、答えが得られる。

---

端が含まれると足される回数が変わるということを整理するのに時間がかかった。