HOJ 1285 - 文章力が、無い。
問題概要
$\large \displaystyle \sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } (|A - i| + |B - j|) \bmod 998244353$ を求めよ。
制約
- $1 \leq N,M \leq 10^9$
- $1 \leq A \leq N$
- $1 \leq B \leq M$
解説
$\sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } (|A - i| + |B - j|) \bmod 998244353 \ $は $(\sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } |A - i|) + (\sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } |B - j|) \bmod 998244353 \ $というように分割することができます。
$\sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } |A - i| \ $というのは、$M \times \sum_{ i = 1 }^{ N } |A - i| \ $というように変形できます。 また、$\sum_{i = 1}^{N} |A - i| \ $は$(\sum_{i = 0}^{A - 1} i) + (\sum_{i = 0}^{N - A + 1} i) \ $というように変形できます。
この値は簡単な計算で求めることができ、$\sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } |B - j| \ $も同じように変形させる事が出来ます。
よって、この問題は計算量$ \ O(1) \ $で解くことができます。
