notepad.exe

つまり覚え書き

ABC105 D - Candy Distribution

復習日記

ABC105 D - Candy Distribution

ABC105 D - Candy Distribution

均等に配れる飴の個数を取り出す組み合わせの総数を求める問題

最初に、制約から全パターンを試すのは無理(105 * 105)

ということはまずパターンをどうやって少なくするかだが、
これは1番目からi、j番目(i ≦ j)までの和をそれぞれ B_i、B_jとするとi番目からj番目の和は B_j - B_iとあらわすことができる。 そのため先に先頭から累積和をもとめておけばパターンを網羅する計算量を落とすことができる。


次に、 B_i、B_jがMで割り切ることができるのはどのようなときか求める。

当然、 B_i、B_jがどちらもMの倍数であれば割り切ることができる。
B_iがMで割った時に1余る場合B_jがMで割って1余れば B_j - B_iがMで割り切ることができる。 つまりMで割った時にあまりが同じもの同士がlとrの組み合わせの候補となることがわかる。

このことから先に求めておいた累積和の配列を余りが同じ物ごとにまとめて数を数えたのち組み合わせを計算することで最終的な答えを求めることができる。

提出コード