ARC107

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

A

数学っぽい問題だから、ぎょっとしたけど公式を調べながら解いたらギリギリ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できた！