Product Modulo [AtCoder Grand Contest 047 C]

https://atcoder.jp/contests/agc047/tasks/agc047_c

前提知識

• FFT/NTT
• 原子根

解説

https://atcoder.jp/contests/agc047/submissions/15795698

隠してはあるが、最初の1手が分かれば一気に（高度）典型化する。

主客転倒

全ての組み合わせに対して、とある計算をして総和を求める。
組合せはO(N²)でこのままでは間に合わない。
主客転倒をしてみよう。
とある計算の計算結果はP未満となる。
よって、計算結果の方を考えてみると、O(P)であり、こっちの方が筋がよさそう。

計算結果起点で考えてみると、
計算結果がxとなる組合せをcomb[x]とすると、答えはx*comb[x]の総和となる。

comb配列の計算

よって、comb配列が求まれば答えが計算可能。
comb[x] := (A[i] * A[j]) % P = x、かつ、i＜jであるような(i,j)の組
これは、類題になじみがある人がみると、ピンとくる条件になっている。畳み込み計算に帰着ができる。
comb[x] := (A[i] * A[j]) % P = xであるような(i,j)の組
i,jの大小関係を取っ払おう。
これを計算した後に、A[i]*A[i]のパターンを引いて、全体を÷2すれば同じが答えが得られる。

畳み込み計算（簡単版）

comb[x] := (A[i] * A[j]) % P = xであるような(i,j)の組
これを計算するのだが、
f[x] := A[i] + A[j] = xであるような(i,j)の組
であると考えてみる。
これはそれほど難しくなく、g[x] := A[i]=xであるiの個数として、配列gと配列gで普通の畳み込みをすれば求めることができる。
まず、これが分からない場合は畳み込み計算、もしくは、FFTについて勉強してきてほしい。

今回の畳み込み計算

今回は添え字部分が和ではなく、積になっている。
この場合の常套テクとして、原始根変換がある。
Pの原始根gをまずは探す。
そして、A[i] = g^B[i]のように変換していく。
すると、A[i] * A[j]はg^{B[i] + B[j]}のように変換ができ、積を指数部の和として考えてFFTするようにする。

…とまぁ、解説したが、自分はこの辺は何となく理解なので、何とも言えない。
以下資料を参照した方がいい。

• 解説 No.931 Multiplicative Convolution - yukicoder
• articles/pre-seisuuron.pdf at pre-releases · kirika-comp/articlesの31ページ

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

    vector<int> v(1 << 18);
    rep(i, 0, N) v[A[i]]++;

    auto comb = convolutionMulModP(v, v, P);

    ll ans = 0;
    int n = comb.size();
    rep(i, 0, n) ans += 1LL * comb[i] * i;
    rep(i, 0, N) ans -= (1LL * A[i] * A[i]) % P;
    cout << ans / 2 << endl;
}