Codeforces Round #395 (Div. 1) C. Timofey and remoduling

n 個の数が与えられる。これを並び替えて mod m 上での等差数列にできるかどうか判定せよ。可能なら初項と公差を示せ。

等差数列の総和は $n\times (a_1+a_n)/2$ で計算できる。このことを使うと、初項を決め打ちすれば $a_n$ が何であるかを求められる。 $a_n$ が何であるかが分かれば公差 $d$ も求められる。

このようにすることで初項、公差の候補がたかだか $n$ 個得られる。ある組み合わせに対して正しいかどうかを判定するには、愚直にやると $O(n \log n)$ 程度かかる（set を使えば）。

やりたいことは $\{a_1,a_2,\ldots,a_n\}$ と $\{a,a+d,a+2d,\ldots,a+(n-1)d\}$ が集合の意味で一致するかどうかを判定することである。等価比較であればハッシュは使えないだろうか？

等差数列の長さ・初項・公差の情報だけから高速に計算できるようなものでないと役に立たない。色々考えた結果、等差数列の二乗和はそこそこ良さそうなハッシュだと判断した。実際、これで通る。

n=1,n=m のケースに注意。