部分列の倍数
/icons/hr.icon
問題文
長さ$ Nの数列$ Aがあります。この数列の$ i文字目から$ j文字目$ (1 \leq i \leq j \leq N)の連続した部分列の総和が、$ 2023の倍数となるような$ (i, j)の組み合わせの個数を求めよ。
/icons/hr.icon
解説
数列$ Aの累積和$ Sを考えます。
例えば以下のような数列を考えてみます。
$ 5
$ 4 \quad 570 \quad 1020 \quad 433 \quad 10
このような数列の部分列の総和が$ 2023の倍数になる組み合わせは$ (2, 4)です。
この時、$ S := [0, 4, 574, 1594, 2027, 2037] となります。
$ (2, 4)が$ 2023の倍数になるということは$ (1, 4) - (1, 1)の和が$ 2023の倍数になることと同値です。
つまり、$ S[4] - S[1] \equiv 0 \pmod {2023} が成り立つ必要があります$ \left(S[i] := \sum_{k=0}^{i} A[k] \right) 。
式変形を行うと、$ S[4] \equiv S[1] \pmod {2023} になります。
ということで、後は余りが長さ$ 2023の配列$ Tを用意し、
$ T[i] = S[i] \pmod {2023} となる個数 と定義し、後は$ \sum_{i=0}^{2022} \dfrac{T[i] \times (T[i] - 1)}{2} で求めることができました。