HOJ 1189 - スライム討伐
問題概要
$N \ $体のスライムがおり、$i \ $番目のスライムのぷよぷよ度は$ \ p_i \ $である。
ぷよぷよ度が$ \ a \ $のスライムが威力$ \ b \ $の攻撃を受けたとき、$a \leq b \ $ならばスライムはやられてしまうが、$a \gt b \ $ならばぷよぷよ度が$ \ \lfloor \frac{a}{2} \rfloor \ $のスライム二体に分裂する。
一回の攻撃の威力$ \ P \ $であるとき、全てのスライムを倒すのに必要な攻撃回数を$ \ 10^9 + 7 \ $で割った余りを求めよ。
制約
- $1 \leq N \leq 10^6$
- $1 \leq P \leq 10^{18}$
- $1 \leq p_i \leq 10^{18}$
解説
ぷよぷよ度が$ \ H \ $のスライム$ \ 1 \ $体に勝つために必要な攻撃回数を$ \ f(H) \ $とします。このとき、 $\begin{eqnarray} f(H) = \begin{cases} 2 \times f(\lfloor \frac{H}{2} \rfloor) + 1 & (H \gt P) \\ 1 & (H \leq P) \end{cases} \end{eqnarray}$
となります。この定義に従って各$ \ p_i \ $について再帰的に計算することで答えを求めることができます。
また、$f(H) \ $を求める計算量は$ \ O(\log H) \ $となります。
