AtCoder Beginner Contest 105：D - Candy Distribution
問題
N 個の箱があり，それぞれ A_i (1 <= i <= N) 個キャンディーが入っている．ここで，任意の個数の連続する箱を選び，それらの箱に入っているキャンディーの合計が M で割り切れるようにしたい．連続する箱の選び方は何通りあるか．
解法
まず，和の mod は mod の和なので A_i を全て mod M し，累積和を取る．ここで，累積和をとる段階でも mod M する（最初に累積和をとってから mod M の方がスマート）．ここで，A_i = A_j な i, j の組が見つかればその組は問題に当てはまる選び方になる．
この i, j の組を高速に求めたいので，map で A_i の値をカウントしておき，A_i ごとに Comb( A_i の個数, 2) をすればよい．あとは全ての A_i について同様に計算し，それらの和が答えになる．ここで，A_i = 0 の時は i, i も選び方に入るので注意．
解答
Submission #3066597 - AtCoder Beginner Contest 105
１発 AC だったのでよかった．
