Kuroni and Impossible Calculation [Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!) C]

https://codeforces.com/contest/1305/problem/C

前提知識

• 鳩ノ巣原理

解説

https://codeforces.com/contest/1305/submission/72405810

天才的なひらめきを要する問題。
それがないと、modで個数分けして数え上げてみようだとか、絶対値をなんとかして取り外して分解？？だとか
爆発解法に走ってしまう（私です）。
ですが、まだC問題ということでちょっとやばそう、かつ順位表を見ても爆速解法が乱発しているので、
これはひらめきが求められている。

解法を説明する。
答えはmod Mで要求されているので、すべての計算はmod Mでやればいい。
配列Aもmod Mで考えてしまって問題ない。
この操作が重要で、これにより以下の性質が生まれる。
「配列Aの全部の要素をmod Mにすると、個数がM個を超えると必ず同じ値になる要素が出てくる」
これは鳩ノ巣原理であり、この状況になっているとabs(a[i] - a[j])=0となる部分が生まれるので、
全体の答えは0となる。

総括して説明すると、M<Nの場合は鳩ノ巣原理により必ず答えが0となる。
N≦Mの場合は、M≦10³なので、問題で与えられている計算式をそのまま計算しても間に合うのでやる。

int N, M, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];

    if (M < N) {
        cout << 0 << endl;
        return;
    }

    ll ans = 1;
    rep(i, 0, N) rep(j, i + 1, N) {
        ans *= abs(A[i] - A[j]);
        ans %= M;
    }
    cout << ans << endl;
}