ABC177-Cの別解と逆元の簡単な実例

想定読者…幾何学的な別解が好きな人、逆元がよくわからん人

　先日AtCoderBeginnerContest177が行われました。私は4完でした（くやしい）。C問題の解説にあった別解が面白かったのと、逆元の簡単な実例になりそうだったので、逆元よくわからん人向けに僭越ながら解説記事を書きます。

# 問題

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/6bc1521d-2473-4e60-6604-23b33261589d.png)

　[リンク](https://atcoder.jp/contests/abc177/tasks/abc177_c)

# まずは想定解

　結論的には、$A_i$の累積和を$S_i$とすると、答えは$A_i \cdot S_{i-1}$の累積和となります。$1,2,3,4$という組み合わせだと、$1*2+1*3+1*4+2*3+2*4+3*4=35$が答えになりますが、$1*2+(1+2)\*3+(1+2+3)*4$という風に変換すれば見通しがよいかと思われます。

　以下、実装。

```c++
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;
 
const ll MOD = 1000000007;
 
int main(){
  int n;
  cin >> n;
  ll ans = 0;
  ll sum = 0;
  rep(i,n){
    int a;
    cin >> a;
    ans = (ans + sum*a)%MOD;
    sum = (sum + a)%MOD;
  }
  cout << ans << endl;
}
```

# 幾何的な理解

　これは[解説](https://atcoder.jp/contests/abc177/editorial/88)にめちゃくちゃわかりやすい図が乗っているので転載させていただきます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/5e82665b-41c4-48ef-6b5d-d2768a43e904.png)
（解説より引用）

　つまり、求めるべき面積は上の正方形の約半分にあたる部分になります。

　これは数式的に直観することもできます。よく因数分解で$$(a+b)^2=a^2+2ab+b^2 \\\\ (a+b+c)^2=a^2+b^2+c^2+2ab+2bc+2ca$$　という式を見ると思いますが、この中の$a^2$や$b^2$といった部分を覗いた上で1/2すると、それぞれの変数のペアをかけたものの和が残ることがわかります。本番でこれに気づきたかった……。

　このことから、$A_i$の総和を二乗したものから、**$A_i$の二乗をしたものの総和**（日本語の違いに注意）を引いて、それを1/2にしたものが答えになることがわかります。式にすると$$\frac{1}{2}[(\Sigma A_i)^2-\Sigma A_i^2]$$　となります。

# 単純に割ればいい？

　ここからが本題なのですが、では上の計算を単純に実装すればいいかというとそうではありません。この問題で求めるのは$100000007$で割った余りだからです。なぜこのような余りを求めさせられるかというと、巨大な数を扱うのに、余りを使うと都合が良いからです。

　余り（剰余）は、2倍したら2倍（の後で剰余を取り直したもの）になりますし、2を足したら+2（の後で剰余を取り直したもの）になります。例えば19を17で割った余りは2ですが、38を17で割った余りは4です。足し算も同様に素直な計算となります。つまり、巨大な数を扱うアルゴリズムをちゃんと設定できているかを、巨大ではない数だけを扱いながら検証できるのです。

　しかし割り算だけは話が複雑になります。例えば19を17で割った余りは2ですが、19/2を17で割った余りは1ではありません。普通の四則演算における逆数にように、それを作用させたら余りも1/2になるような何かが必要です。

# 逆元

　それが**逆元**です。正確には逆元（作用させたら1になるような何か）はより広い概念ですが、競プロでは主にこの剰余の逆元のことを指して使われるようです。

　この例で言えば、逆元は9になります。19*9=171となり、17で割った余りは1になっていることがわかります。シンプルな例でいえば、2*9=18で余り1になることから、逆元となることがわかります。物理的にはあらゆる数に対して**かけたらちょうど余り1になる**ような数をうまいこと見つけたら、それが逆元となります。3だったら3*6=18で6、4だったら4*13=52で13です。

　あまり規則性はなさそうですが、では、任意の数に対する逆元は、うまいこと余り1になる数を総当りで試していくしかないのでしょうか？

# 逆元の見つけ方

　当然そのような悲劇的なことはなく、任意の剰余を以下から計算できる（ただし**素数の剰余に限る**）ことがフェルマーの小定理（not最終定理）によって示されています。

$$a^{p-2}\\\\a=剰余、p=割る数（素数）$$　

　先の例で言えば、$2^{15} = 1927*17+9$、$3^{15}=844053*17+6$となることから、逆元が求められていることがわかります。

# 話を問題に戻すと

　元々の話は、$1000000007$で割った余りを半分にするような数が必要ということでした。これは$$2^{1000000005}$$　を計算することにより求められます。1000000005乗！　気の遠くなるような膨大な数になり、これをそのまま実装するとそれだけで計算量が爆発してしまいますが、プログラムでは二分累乗などで工夫することにより制限時間内に求めることができます。

　……が、実は2の逆元ならすぐに求めることができます。割る素数に1を足して2で割ればいいのです。

$$(1000000007 + 1)/2 = 500000004\\\\2*500000004 = 1000000007 + 1$$

　このような楽ができるのは2の場合のみですが。
　
　要は、500000004をかけた後の剰余が正しい答えになります。

# 実装

　以下、c++による実装になります。

```c++
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;

const ll MOD = 1000000007;

int main(){
  int n;
  cin >> n;
  ll sum = 0;
  ll par = 0;
  rep(i,n){
    int a;
    cin >> a;
    par = (par+a*a)%MOD;
    sum = (sum+a)%MOD;
  }
  ll ans = (sum*sum-par+MOD)%MOD;
  ans = (ans*500000004)%MOD;
  cout << ans << endl;
}
```

　ちなみに計算量は$O(n)$で全然変わりませんｗ　オシャレ解法ですね。