結果
問題 |
No.2046 Ans Mod? Mod Ans!
|
ユーザー |
![]() |
提出日時 | 2025-04-05 10:37:57 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,083 bytes |
コンパイル時間 | 948 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 111,352 KB |
最終ジャッジ日時 | 2025-04-05 10:38:05 |
合計ジャッジ時間 | 7,199 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 WA * 13 |
ソースコード
import typing class FenwickTree: '''Reference: https://en.wikipedia.org/wiki/Fenwick_tree''' def __init__(self, n: int = 0) -> None: self._n = n self.data = [0] * n def add(self, p: int, x: typing.Any) -> None: assert 0 <= p < self._n p += 1 while p <= self._n: self.data[p - 1] += x p += p & -p def sum(self, left: int, right: int) -> typing.Any: assert 0 <= left <= right <= self._n return self._sum(right) - self._sum(left) def _sum(self, r: int) -> typing.Any: s = 0 while r > 0: s += self.data[r - 1] r -= r & -r return s MOD = 10 ** 9 + 7 N = int(input()) A = list(map(int,input().split())) A.sort() Amax = A[-1] ft = FenwickTree(Amax + 1) t1 = 0 t2 = 0 for i in range(N): t1 += A[i] * (2 * i - N + 1) for i in reversed(range(N)): a = A[i] tmp = 0 for j in range(a,Amax+1,a): tmp += j * ft.sum(j,min(j+a,Amax+1)) tmp %= MOD ft.add(a,1) t2 += tmp t2 %= MOD print((t2-t1)%MOD)