AtCoder ABC 177 C - Sum of product of pairs (灰色, 300 点) - けんちょんの競プロ精進記録茶色 diff にはなると思ったけど、灰色 diff だった...「/2」が必要と感じて詰まる人も多いと思ったのに... 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての に対しての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと まず、すべてのペアに対する総和を愚直に計算しようと思ったら、次のような for 文を書くと思う。 long long res = 0; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { res += A[i] * A[j] % 1000000007; res %= 1000000007; } } しかしこれでは の計算量となって間に合わないので、工夫が必要となる。 このとき、受験数学に慣れている人なら、ノータイムで次のような式変形をすると
