ABC105 D - Candy Distribution
復習日記
ABC105 D - Candy Distribution
均等に配れる飴の個数を取り出す組み合わせの総数を求める問題
最初に、制約から全パターンを試すのは無理(105 * 105)
ということはまずパターンをどうやって少なくするかだが、
これは1番目からi、j番目(i ≦ j)までの和をそれぞれとするとi番目からj番目の和はとあらわすことができる。
そのため先に先頭から累積和をもとめておけばパターンを網羅する計算量を落とすことができる。
次に、がMで割り切ることができるのはどのようなときか求める。
当然、がどちらもMの倍数であれば割り切ることができる。
がMで割った時に1余る場合がMで割って1余ればがMで割り切ることができる。
つまりMで割った時にあまりが同じもの同士がの組み合わせの候補となることがわかる。
このことから先に求めておいた累積和の配列を余りが同じ物ごとにまとめて数を数えたのち組み合わせを計算することで最終的な答えを求めることができる。