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

はじめに

• AtCoderのコンテスト問題を解くとき、解答は(mod 1000000007)で答えよ！、のような指示文がよく出てくるよね。で、下記みたいなコードをよく書くよね。

let m = 1000000007
for i in 1..<N {
    for j in 0..<i {
        dp[i] += dp[j] + i
        dp[i] %= m // --- これはＯＫ？（途中で実行）
    }
}
print(dp[N])

• 単純に題意を満たすなら、これ

let m = 1000000007
for i in 1..<N {
    for j in 0..<i {
        dp[i] += dp[j] + i
    }
}
print(dp[N] % m) // 本来はコレ！！！

• 僕は深く考えずに、前者の書き方（途中で実行）をしていたけど、なんでコレが許されるのか整理したい。
• また、どのような場合に、これ（途中で実行）がアウトなのか、整理したい。

剰余の公式

• 以前、有理数のmod表記の投稿で書いたけど、こんな感じです。
• （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)において、同じ結果となる。

///①
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を全ての頂点で計算量を少なくして実行するアルゴリズムです。一つの頂点で行う木dpはO(N)の計算量なので、工夫をしないで全頂点に対して行うと、$O(N^2)$の計算量となります。
  • 下図は頂点0を根としたときのdp[i]の情報の流れ。
    
  • この時、各頂点に格納されている値をA[i]とし、dp[i] = A[i] × 子のdp × 子のdp × ..となる木dpだったとする。この時、以下のとおりなのは当然分かるよね。
    • dp[5] = A[5] + dp[7] × dp[8]
    • dp[3] = A[3] + dp[4] × dp[5] × dp[6]
  • それじゃあ、「dp[0]が算出済みである」ことを前提としたとき、新たに、「頂点3を根とする場合の解」はどうやって求められるだろうか？
  • 根を3とするdp配列をndpとして、解をndp[3]とするとき、実は、たった3回のステップで計算出来る。
    
  • 具体的には、頂点⓪の再計算 ⇒ ②の再計算 ⇒ ③の再計算です。
    • 頂点⓪：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])の約数である事なんて､確約されてないから、使えんがね〜。

終わりに

• 今回、こんな話をしちゃったのは、前記の問題例②のアホアホなミスを正にやっちまったからです。
• 今後の戒めとして、この投稿をしておきます。
• じゃあ結局、問題例②みたいな問題はどうやって解くの？という方は、こちらへ｡