geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC207E Mod i

ABC iとj独立に計算

前に解説読んでよくわからなかったので寝かしていましたが、今回やってみたら解けました。

まず、以下に頻出の考え方について説明します。

ある整数列 $A$ の $A_i$ を末尾とする連続した部分列 $A_j,A_{j+1},...,A_i$ の要素の和が $M$ の倍数となるような、全ての $j$ を求めることを考えます。

$S_k=A_1+...+A_k$ とすると、

$A_j,A_{j+1},...,A_i$ の和は $S_i - S_{j-1}$ なので、

これが $M$ の倍数であるためには、

$S_i - S_{j-1} \equiv 0 \ (mod \ M)$

が成り立つ必要があり、したがって、

$S_i \equiv S_{j-1} \ (mod \ M)$

が成り立つような $j$ は全て条件を満たします。

$i$ を1から順に探索し、その過程で、 $S_i \ mod\ M$ を記録しておけば、 $O(N)$ で、全ての $A_i$ を末尾とした数列について計算できます。

この考え方を前提とし、本題に移ります。

まず、一例として、問題の条件を満たすような $i$ を末尾とした3分割の方法の総数を求めてみます。

これは前述した考え方を使うと、 $S_i \equiv S_{j-1} \ (mod \ 3)$ を満たすような $j$ の全てで、連続した部分列 $A_j,A_{j+1},...,A_i$ の要素の和が $3$ の倍数となります。

そのため、 $A_1,...,A_{j-1}$ を2分割するような分割の方法全てに対して、 $A_j,...,A_i$ の部分列を付加し、3分割された数列を作り出すことができます。

そこで、以下のようなDPを考えます。

$dp[i][j][k]:=$ $A_i$ を末尾とした $j$ 個に分割された数列であり、 $S_i \ mod\ (j+1)$ が $k$ であるものの総数

( $j$ 個に分割された数列については、次の $j+1$ の余りを保存しなければいけないことに注意)

遷移は、各 $A_i$ を末尾とする数列を $j$ 個に分割する場合、

$A_x\ (1 \leq x \leq i-1)$ を末尾とする数列が $j-1$ 個に分割されていて、

　　かつ、

$k=S_i\ mod\ j$ としたとき、 $S_x\ mod\ j$ が $k$ であるもの

に $A_{x+1},...,A_{i}$ を付加できる( $x$ と $x+1$ の間で分割できる)ので、

$dp[i][j][S_i\ mod \ (j+1)]$ += $dp[1][j-1][k]+...+dp[i-1][j-1][k]$

となります。

このままだと、状態数 $N^3$ と計算量 $O(N^3)$ となります。

そこで、

$dp[j][k]:=$ $j$ 個に分割された数列であり、「要素の和 $\ mod\ (j+1)$ 」が $k$ であるものの総数

とすると、総数は累積和的に計算できるようになり、末尾の情報も不要となります。

遷移は、

$dp[j][S_i\ mod \ (j+1)]$ += $dp[j-1][k]$

状態数 $N^2$ と計算量 $O(N^2)$ となります。

(但し、 $j$ は分割の個数の多いほうから更新)

この遷移に基づいて、 $A_{N-1}$ までの値を計算し、最後に $A_N$ を考慮したときに更新された分の和をとれば答えとなります。

提出コード：https://atcoder.jp/contests/abc207/submissions/25645338