結果

問題 No.3662 yuu Hates Sigma Problem
コンテスト
ユーザー sepa38
提出日時 2026-08-13 19:01:25
言語 PyPy3
(7.3.23)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 180 ms / 2,000 ms
+ 866µs
コード長 867 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 265 ms
コンパイル使用メモリ 96,108 KB
実行使用メモリ 114,560 KB
最終ジャッジ日時 2026-08-30 13:01:25
合計ジャッジ時間 8,859 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
subtask1. 20 % AC * 19
subtask2. 30 % AC * 13
subtask3. 50 % AC * 49
合計 2.5 * 100% = 250 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

"""
Ai の寄与分を考える
\sum_{j=0}^{N-1} (i \oplus j)
これも bit ごとに考えた方が良さそう
0 ~ N-1 では、ある bit が t 個立ってて、N-t 個立ってない
i でこの bit が立っているなら、この bit の寄与分は N - t
i でこの bit が立っていないなら、この bit の寄与分は t
"""

n = int(input())
a = list(map(int, input().split()))


assert 1 <= n <= 5*10**5
assert len(a) == n
assert 0 <= min(a)
assert max(a) <= 5*10**5


m = 20
bit_count = [0] * m
for i in range(n):
    for j in range(m):
        if i & (1 << j):
            bit_count[j] += 1

ans = 0
mod = 998244353
for i in range(n):
    ai = a[i]
    for j in range(m):
        if i & (1 << j):
            ans += ai * (1 << j) * (n - bit_count[j])
        else:
            ans += ai * (1 << j) * bit_count[j]

        ans %= mod

print(ans)
0