コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1820 (記事作成時点)
供養
解法
- $A_{1}$ から $A_{i}$ までの累積和を $C_{i}$ とする
- $i \lt j$ および $1 \le k \le N$ について $C_{i} \equiv C_{j}\; (\mathrm{mod}\; k)$ のとき、$A_{i}$ で終端している、合計が $k$ で割り切れる $B_{k}$ に $A_{i + 1}, \dots, A_{j}$ を追加した $B_{k}^{'}$ もまた合計が $k$ で割り切れる
- 上記の性質を踏まえてDPを実施する
- $\mathit{DP}_{i, j}$ を、$B_{i}$ を $A_{j}$ で終端するパターン数とする
- $\mathit{DP}_{0, 0} = 1, \mathit{DP}_{0, j \ge 1} = 0$ とする
- $1 \le i \le N$ について以下を実施する
- 長さ $i$ の配列 $M $ を用意する
- $M_{C_{i - 1} \% i} = \mathit{DP}_{i - 1, i}$ とする
- $i \le j \le N$ について、$\mathit{DP}_{C_{j} \% i} = M_{C_{j} \% i}$ とし、$M_{C_{j} \% i} に \mathit{DP}_{i - 1, j}$ を加算する
- $\sum_{i}\mathit{DP}_{i, N}$ が答え
実装
計算量は $O(N^{2})$
公式解説
躓いた点
