No.503

1回の操作で配列の長さは $N-K+1$ になるので, 操作の回数は $s = \lfloor N/(K-1) \rfloor$ である. ただし, $N$ を $K-1$ で割った余りが $0, 1$ のときは, 最後から2つ前に $K$ 個以下の配列になるので, 操作の回数は1回少ない.

このとき最後に残る配列の個数は $t = N-s(K-1)$ 個である.

$D = 1$ のときは $\{1, 1, \dots, 1\}$ にしかならないので, その和は $t$ である.

$D > 1$ のときは, $\{D^{a_1}, D^{a_2}, \dots, D^{a_t}\}$ になる. ただし, $\sum a_i = s$ である.

このような $a_1, a_2, \dots, a_t$ の組み合わせの数を $A(t, s)$, そのときの配列の和を $B(t, s)$ とすると,

$$\begin{align} A(t, s) &= \sum_{i=0}^s A(t-1, s-i) \\ B(t, s) &= \sum_{i=0}^s (D^iA(t-1,s-i)+B(t-1,s-i)) \end{align}$$

となる. これをそのまま計算すると $O(s^2t)$ となって間に合わない. そこで,

$$\begin{align} X(t, s) &= \sum_{i=0}^s D^i A(t-1, s-i) \\ Y(t, s) &= \sum_{i=0}^s B(t-1, s-i) \end{align}$$

とすると,

$$\begin{align} A(t, s) &= A(t-1, s) + \sum_{i=0}^{s-1} A(t-1, s-1-i) = A(t-1, s) + A(t, s-1) \\ X(t, s) &= A(t-1, s) + \sum_{i=0}^{s-1} D D^i X(t-1, s-1-i) = A(t-1, s) + DX(t, s-1) \\ Y(t, s) &= B(t-1, s) + \sum_{i=0}^{s-1} B(t-1, s-1-i) = B(t-1, s) + Y(t, s-1) \\ B(t, s) &= X(t, s) + Y(t, s) \end{align}$$

となるので, $O(st) = O(N)$ となってこれならば間に合う.