考え方
以下を愚直にやってみた．計算をミスらないように実装するのが大変．．．
アライグマ「F問題は算数なのだ……。行ごとの和を考えると、奇数行目と偶数行目がそれぞれ等差数列になってるから、和の公式を使ってO(1)で求められるのだ！」https://t.co/lOLl5CdmVI pic.twitter.com/p54IkCEMTQ
— 競技プログラミングをするフレンズ (@kyopro_friends) September 17, 2022
$x$方向には公差2，$y$方向には公差$2 M \times \text{(項数)}$となる．
初項$a_{0}$，公差$a$，項数$n$の等差数列の和は
\begin{aligned}
& a_{0} + (a_{0} + a) + \cdots +(a_{0} + (n - 1)a) \\
&= n a_{0} + a \sum_{k = 1}^{n - 1} k \\
&= n a_{0} + a\frac{(n - 1)n}{2}
\end{aligned}
& a_{0} + (a_{0} + a) + \cdots +(a_{0} + (n - 1)a) \\
&= n a_{0} + a \sum_{k = 1}^{n - 1} k \\
&= n a_{0} + a\frac{(n - 1)n}{2}
\end{aligned}
これを，奇数行目と偶数行目に分けて考える．
回答例
N, M = map(int, input().split()) mod = 998244353 def f(x, y): nx, ny = (x + 1) // 2, (y + 1) // 2 nx %= mod ny %= mod sum_odd = ny + (ny - 1) * ny # y方向 sum_odd %= mod sum_odd = nx * sum_odd + M * ny * (nx - 1) * nx # x方向 sum_odd %= mod # nx, ny = x // 2, y // 2 nx %= mod ny %= mod sum_even = ny * (M + 2) + (ny - 1) * ny # y方向 sum_even %= mod sum_even = nx * sum_even + M * ny * (nx - 1) * nx # x方向 sum_even %= mod return (sum_odd + sum_even) % mod def g(a, b, c, d): ret = f(b, d) ret -= f(a - 1, d) ret %= mod ret -= f(b, c - 1) ret %= mod ret += f(a - 1, c - 1) ret %= mod return ret Q = int(input()) for _ in range(Q): A, B, C, D = map(int, input().split()) print(g(A, B, C, D))
