ARC 107 | A - Simple Math

問題

https://atcoder.jp/contests/arc107/tasks/arc107_a

考えたこと

ABCが$1 \leq A, B, C \leq 10^9$なのでそのまま計算するとTLEになる。式を簡単にすることを考える。

シグマは添字に関係のない定数は外だしできるので以下のように変形できる。

$$\sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} abc$$

$$\sum_{a=1}^{A} a \sum_{b=1}^{B} b \sum_{c=1}^{C} c \tag{1}$$

ここで

$$\sum_{x=1}^{N} x = \frac{N (N-1)}{2}$$

なので$(1)$は以下のように変形できる。

$$\frac{A (A-1)}{2} \times \frac{B (B-1)}{2} \times \frac{C (C-1)}{2}$$

これで$O(1)$で値が求められるようになった。

コード

実装時のTips

• using mint = modint998244353;を使う

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

using mint = modint998244353;

int main() {
  ll A, B, C;
  cin >> A >> B >> C;
  mint cv = C * (C + 1) / 2;
  mint bv = B * (B + 1) / 2;
  mint av = A * (A + 1) / 2;
  mint ans = av * bv * cv;
  cout << ans.val() << endl;
}

参考

• https://atcoder.jp/contests/arc107/editorial/260
• https://www.wolframalpha.com/input/?i=Sum[+Sum[+Sum[+abc%2C+{c%2C+1%2C+C}]%2C+{b%2C+1%2C+B}]%2C+{a%2C+1%2C+A}]&lang=ja

WolframeAlpha知らなかった。式展開してくれて便利。