mod計算の注意【競技プログラミング】

# はじめに
- AtCoderのコンテスト問題を解くとき、解答は(mod 1000000007)で答えよ！、のような指示文がよく出てくるよね。で、下記みたいなコードをよく書くよね。
```swift
let m = 1000000007
for i in 1..<N {
    for j in 0..<i {
        dp[i] += dp[j] + i
        dp[i] %= m // --- これはＯＫ？（途中で実行）
    }
}
print(dp[N])
```
- 単純に題意を満たすなら、これ
```swift
let m = 1000000007
for i in 1..<N {
    for j in 0..<i {
        dp[i] += dp[j] + i
    }
}
print(dp[N] % m) // 本来はコレ！！！
```
- 僕は深く考えずに、前者の書き方（途中で実行）をしていたけど、なんでコレが許されるのか整理したい。
- また、どのような場合に、これ（途中で実行）がアウトなのか、整理したい。

# 剰余の公式
- 以前、[有理数のmod表記の投稿](https://qiita.com/kei_tnk/items/4a643b2f47d2aa919a1b)で書いたけど、こんな感じです。
- （mod m）のとき A ≡ B かつ C ≡ D ならば、下記が成立する。以降、それぞれ「公式1.」「公式2.」「公式3.」と呼ぶ。
    1. A+C ≡ B+D　（左記より、A-C ≡ B-Dも成立する)
    2. A×C ≡ B×D　（左記より、$A^n ≡ B^n$も成立する)
    3. mとnが素であり、かつ、nがAとBの公約数であるとき、A/n ≡ B/n
    ※「mとnが素である」とは、「mとnの公約数は1のみ」という意味
    - 公式3.については、公式2.からの派生みたい（C=1/n）だけど、mとnが素でないときは駄目であることに注意する。
        - 例えば、m=8のとき、A=12、B=36に対し、12≡36(≡4)である
            - このとき、「mと素なn=3」により、A/n , B/nを考えると、4≡12(≡4)である
            - しかし、「mと素でないn=4」により、A/n , B/nを考えると、3≢9 となる。

# 公式に基づく、mod計算の解説
- 公式1,2により、下記①②は(mod m)において、同じ結果となる。
```swift
///①
A[0] = N % m // ㋐
for i in 1..<N {
    A[i] = (a % m) * (b % m) + (c % m) + A[i - 1] // ㋑
    A[i] %= m // ㋒
}

///②
A[0] = N // ㋓
for i in 1..<N {
    A[i] = a * b + c + A[i - 1] // ㋔
}
    A[N] %= m // ㋕
```
- 一応説明すると、
    - ㋐と㋓において、A[0]は合同がなりたつ。
    - ㋑と㋒と㋔において、A[i]は合同が成り立つ。
    - ㋔の最後と、㋕において、A[N]は、値も位置している。

# mod計算の注意
- 問題例①
- まずは、アホみたいな例だけど、下記のような問題は注意
    - N個の土地それぞれの「土地の面積Si」(i in 0..<N)、「土地の金額Pi」(i in 0..<N)を(mod m)で答えよ。また、最も土地単価の高い土地の番号を求めよ。
    - ここで、当然だけど、(mod m)表示された「Pi/Si」で土地単価は求められない。
- 問題例②
- 次に、少し複雑になるけど、全方位木dpで楽しようとしたら駄目よ、と言う話。
    - 全方位木dpとは、通常、一つの頂点のみで行う[木dp](https://qiita.com/kei_tnk/items/bf2165a09c741e900391)を全ての頂点で計算量を少なくして実行するアルゴリズムです。一つの頂点で行う木dpはO(N)の計算量なので、工夫をしないで全頂点に対して行うと、$O(N^2)$の計算量となります。
    - 下図は頂点0を根としたときのdp[i]の情報の流れ。
![スクリーンショット 0006-11-04 19.08.12.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2733720/9d2f7cd9-8506-7cdd-c43a-48f5cdb9c4da.jpeg)
    - この時、各頂点に格納されている値をA[i]とし、`dp[i] = A[i] × 子のdp × 子のdp × ..`となる木dpだったとする。この時、以下のとおりなのは当然分かるよね。
        - <font color=lightblue>dp[5]</font> = A[5] + dp[7] × dp[8]
        - dp[3] = A[3] + dp[4] × <font color=lightblue>dp[5]</font> × dp[6]
    - それじゃあ、「<font color=red>dp[0]が算出済みである</font>」ことを前提としたとき、新たに、「<font color=lightgreen>頂点3を根とする場合の解</font>」はどうやって求められるだろうか？
    - 根を3とするdp配列をndpとして、解をndp[3]とするとき、実は、たった3回のステップで計算出来る。
    ![スクリーンショット 0006-11-04 19.30.43.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2733720/7e57c31e-9080-3c7d-3f48-100e4734423c.jpeg)
    - 具体的には、頂点⓪の再計算 ⇒ ②の再計算 ⇒ ③の再計算です。
        - 頂点⓪：ndp[0] = A[0] + (dp[0] - A[0]) / dp[2] // 頂点②の影響を除去
        - 頂点②：ndp[2] = A[2] + (dp[2] - A[2]) / dp[3] × ndp[0] // 頂点③の影響を除去し、頂点⓪の影響を追加
        - 頂点③：ndp[3] = A[3] + (dp[3] - A[3]) × ndp[2] // 頂点②の影響を追加
    - このように、一度計算の終わったdp配列と新たに生成するndpで計算可能なので、2×Nの計算量となるので、単純にN回の木dpを行う場合の$O(N^2)$より大幅に削減できました。めでたし、めでたし...って思うじゃん？
    - この手のdpに乗算が現れる問題って、とてつもない数字なるから、(mod m)で答えろって問題が多いのよね。
    - で、上記の頂点⓪②のステップの計算を見て欲しいんだけど、除算にdpの値を使っちゃってるのよね。あちゃー。
    - (mod m)しちゃった後のdp[2]やdp[3]が、丁度(dp[0]-A[0])や(dp[2]-A[2])の約数である事なんて､確約されてないから、使えんがね〜。

# 終わりに
- 今回、こんな話をしちゃったのは、前記の問題例②のアホアホなミスを正にやっちまったからです。
- 今後の戒めとして、この投稿をしておきます。
- じゃあ結局、問題例②みたいな問題はどうやって解くの？という方は、[こちら](https://qiita.com/kei_tnk/items/1d088c01dce5b2209c8e)へ｡