問題概要
正整数 $A, B, C$ が与えられる．
\begin{align*}
\sum_{a = 1}^{A}\sum_{b = 1}^{B}\sum_{c = 1}^{C}abc
\end{align*}
を求めよ．
制約
- $1 \leq A, B, C \leq 10^9$
解法
ぐるるなどすると分かりますが，$\sum_{ i = 1 }^{x} = \frac{ x ( x + 1 ) } 2$ です．後の記述の簡略化のため，$s( x ) = \frac{ x ( x + 1 ) } 2$ とします．三重になった $\sum$ を内側から $s( x )$ の形で置き換えていくと，
\begin{align*}
\sum_{a = 1}^{A}\sum_{b = 1}^{B}\sum_{c = 1}^{C}abc
&= \sum_{a = 1}^{A}\sum_{b = 1}^{B}a b ( s( c ) ) \\
&= \sum_{a = 1}^{A}a ( s( b ) s( c ) ) \\
&= s( a )s( b )s( c )
\end{align*}
となり，この形ならば定数時間で求めることができます．
main = do [ a, b, c ] <- readIntegers print $ s a * s b * s c `mod` 998244353 s n = n * ( n + 1 ) `div` 2
