問題
解説
問題を解く際に行う計算を、式で表すと以下のようになります。
この解を \(S\) と置きます。
$$ S = a \times b + a \times (b+1) + ... + (a+1) \times b + (a+1) \times (b+1) + ... + c \times (d-1) + c \times d $$
この式は、以下のように因数分解できます。
$$ S = (a + (a+1) + ... + c) \times (b + (b+1) + ... + d) $$
\(a\) から \(c\) まで、 \(b\) から \(d\) まではそれぞれ連続する自然数の区間なので、 等差数列の和を求める方法を使って \(O(1)\) で求めることができます。
よってこの問題を \(O(1)\) で解くことができました。
別解
\( T := a + (a+1) + ... + c\) と置きます。 \(T\) を累積和、等差数列の和などを使ってあらかじめ求めておきます。
\(S\) は \(T\) を使って以下のように表すことができます。
$$ S = T \times b + T \times (b+1) + ... + T \times d $$
\( T \) をあらかじめ求めておけば、 \(S\) は \( O(N) \) で求めることができ、 \(T\) も \( O(N) \) で求めることができるため、全体の計算量は \( O(N) \) となります。
制約が十分小さいため、この方法でも求めることができます。
表の縦、あるいは横に注目して、まとめて足していくイメージです。これを縦横両側から行うと、最初の解法になります。
Writer解
Python、 \( O(N) \) 。
余談
- 「九九の和」で検索すると、解法を得られます。サンプルには、九九の和を求める入力例があったのですが、これを受けて削除しました。
