ARC107

ARC107 色々調べながら A だけぎりぎり AC できたので、まとめておこうとおもう。

A

Simple Math

数学っぽい問題だから、ぎょっとしたけど公式を調べながら解いたらギリギリ AC できた。 とりあえず必要なところだけ抜粋。

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
mod = 998244353

def solve():
    a,b,c = LI()
    ans = a*b*c*(a+1)*(b+1)*(c+1) * pow(8,-1,mod) % mod
    print(ans)
    return

if __name__ == "__main__":
    solve()

まず、シグマってなんだっけと思いながら例 1 を見てみたら、for 文で解けそうな感じだった。

けど、制約をみたら1<= A,B,C <= 10**9だった… とりあえず、

ans = 0
for i in range(1,a+1):
    for j in range(1,b+1):
        for k in range(1,c+1):
            ans += i*j*k
print(ans%mod)

こんな感じで書いてみて例 1 が解けたので、イメージ通りで一安心。 どうすれば計算量減らせるのかな～と思いながら調べてたら、等差数列の和の公式が出てきた。

n(n+1)/2すると、差が 1 で 1 から n までの数列の和が求められるらしいのでそれを使ってみる。

ans = a*(a+1)/2 * b*(b+1)/2 * c*(c+1)/2
print(int(ans%mod))

これで例 1 も通ることが確認できたので、解けた！と思いきや、例 2 が合わない。

調べたら mod の含む割り算は逆数を用いないといけないことがわかった。

python3.8 以降ではpow(n,-1,<mod>)を使えば逆数が得られるようだ。

ans = a*b*c*(a+1)*(b+1)*(c+1) * pow(8,-1,mod)
print(ans%mod)

2で 3 回割っているので、8にまとめてpow()に入れた。 他の計算式もちょっとまとめて完成。

これで AC できた！