[AtCoder] ABC105 D – Candy Distribution

Candy Distribution

https://atcoder.jp/contests/abc105/tasks/abc105_d

考え方

題意

数列 \( A \) の部分列の和が \( M \) の倍数となるものの個数を答えます。

方針

部分列の和の組み合わせは \( \dfrac{N(N – 1)}{2} \) 通りありますが、累積和 \( B \) を用いて、\( B_i \mod M \) の個数を数えます。この値を \( C_i \) とすると、\( \dfrac{C_i (C_i – 1)}{2} \) の総和が答えとなります。これは、ある部分列の和は、\( B_i – B_j \) と表現できるので、その組み合わせを考えていることになるからです。

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする