結果

問題 No.3768 Sum of Difference of XOR
コンテスト
ユーザー apricity
提出日時 2026-07-04 04:59:31
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 2,349 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 84 ms
コンパイル使用メモリ 64,828 KB
実行使用メモリ 932,564 KB
最終ジャッジ日時 2026-10-16 20:52:07
合計ジャッジ時間 100,198 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/env pypy3
MOD = 998244353

def fhwt(a, inv=False):
    n = len(a)
    assert (n&(n-1)) == 0
    i = 1
    while i < n:
        for j in range(0,n,i<<1):
            for k in range(0,i):
                s,t = a[j+k], a[j+k+i]
                a[j+k] = s+t
                a[j+k+i] = s-t
        i <<= 1
    if inv:
        for i in range(n):
            a[i] //= n

def bitwise_xor_convolution(a, b):
    n = len(a)
    assert (n&(n-1)) == 0
    assert len(b) == n
    _a = a[:]
    _b = b[:]
    fhwt(_a); fhwt(_b)
    for i in range(n):
        _a[i] *= _b[i]
    fhwt(_a, inv=True)
    return _a

B = 18
MX = 1<<B

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

f = [0 for _ in range(MX)]
for i in range(n):
    f[a[i]] += 1
ff = bitwise_xor_convolution(f,f)
ans_sum = 0
for x in range(MX):
    ans_sum += x*ff[x]*(n-2)*(n-3)*2
    ans_sum %= MOD
sum_f = [0 for _ in range(MX+1)]
sum_fi = [0 for _ in range(MX+1)]
for i in range(MX):
    sum_f[i+1] = sum_f[i] + ff[i]
    sum_fi[i+1] = sum_fi[i] + ff[i]*i
ans_min = 0
for x in range(MX):
    ans_min += ff[x] * (x*(sum_f[MX]-sum_f[x]) + sum_fi[x])
    ans_min += 2*x*ff[x]
    ans_min %= MOD

ax = [[[[0 for _ in range(2)] for _ in range(B)] for _ in range(2)] for _ in range(B)]
for i in range(n):
    for j in range(B):
        for k in range(B):
            ax[j][a[i]>>j&1][k][a[i]>>k&1] += 1


ay = [[[0 for _ in range(2)] for _ in range(B)] for _ in range(MX*2)]
for i in range(n):
    for j in range(B):
        ay[MX+a[i]][j][a[i]>>j&1] += 1

b = [[0 for _ in range(2)] for _ in range(B)]
for x in range(MX):
    for j in range(B):
        b[j][x>>j&1] += f[x]*f[x]

for s in range(MX-1, 0, -1):
    for i in range(B):
        for j in range(2):
            ay[s][i][j] += ay[s*2][i][j] + ay[s*2+1][i][j]
    d = B - s.bit_length()
    sz0 = ay[s*2][0][0] + ay[s*2][0][1]
    sz1 = ay[s*2+1][0][0] + ay[s*2+1][0][1]
    for i in range(B):
        cnt = ax[d][1][i][0] * ay[s*2+1][i][1] + ax[d][1][i][1] * ay[s*2+1][i][0]
        ans_min -= 4 * 2 * sz0 * cnt * (1<<i)
        cnt = ax[d][0][i][0] * ay[s*2][i][1] + ax[d][0][i][1] * ay[s*2][i][0]
        ans_min -= 4 * 2 * sz1 * cnt * (1<<i)
        ans_min %= MOD

for i in range(n):
    for j in range(B):
        ans_min -= 4 * (b[j][1-(a[i]>>j&1)]) * (1<<j)
        ans_min %= MOD
print((ans_sum - ans_min * 2) % MOD)
0