概要

各項の寄与を考えてみましょう．

問題原案：kusirakusira

解説

$\displaystyle |S| = \prod A < (2^{30})^{10^5}$ であり，現実的な実行時間で $S$ の要素をすべて列挙して答えを求めることは不可能です．

そこで，$A$ の各項が答えにどれだけ影響を与えるかを求め，それをすべての項に対して合計することを考えます．

$P \coloneqq \prod A$ とします．

$i \scriptsize \; (1 \leq i \leq N)$ 項目 ($X_i$ とします) を固定したとき，その他の項の値の組み合わせとしてありうるものは $\displaystyle A_1 \times A_2 \times \cdots \times A_{i-1} \times A_{i+1} \times \cdots A_N = \frac{P}{A_i} \eqqcolon W_i$ 通りです．

そして，その $W_i$ 通りについて $X_i = 1, 2, \ldots, A_i$ の場合をそれぞれ考え，その総和を求めればよいので，結局 $i$ 項目の寄与は以下に等しいです：

• $(1 \times W_i + 2 \times W_i + \cdots + A_i \times W_i) \\ = (1 + 2 + \cdots + A_i) W_i \\ = \frac{1}{2}\,A_i \, (A_i + 1) W_i \\ = \frac{1}{2}\,A_i \, (A_i + 1) \frac{P}{A_i} \\ = \frac{1}{2}\, (A_i + 1) P \\$

これを各 $i$ について足し合わせたものが答えであり，これは $\Theta(N)$ 時間などで求められます．

解説：uni_kakurenbo

実装例