結果

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

ソースコード

diff #
raw source code 

import sys
# input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
# verification-helper: PROBLEM https://judge.yosupo.jp/problem/bitwise_xor_convolution

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def fwht_pair(A: list[int], B: list[int], N: int):
    Z = len(A)
    for i in range(N):
        m = b = 1<<i
        while m < Z:
            a0, a1, b0, b1 = A[m^b], A[m], B[m^b], B[m]
            A[m^b], A[m], B[m^b], B[m] = a0+a1, a0-a1, b0+b1, b0-b1
            m = m+1|b
    return A, B

def fwht(A: list, N: int):
    Z = len(A)
    for i in range(N):
        m = b = 1<<i
        while m < Z:
            a0, a1 = A[m^b], A[m]
            A[m^b], A[m] = a0+a1, a0-a1
            m = m+1|b
    return A

def xor_conv(A: list, B: list, N: int, mod: int):
    assert len(A) == len(B)
    fwht_pair(A, B, N)
    for i, b in enumerate(B): A[i] = A[i]%mod * (b%mod) % mod
    fwht(A, N)
    inv = pow(len(A), -1, mod)
    for i, a in enumerate(A): A[i] = a%mod * inv%mod
    return A



n = ni()
a = na()
m = 19
f = [0] * (1 << m)
for i in range(n):
    f[i] += a[i]
g = [0] * (1 << m)
for i in range(n):
    g[i] += 1
mod = 998244353
h = xor_conv(f, g, 1 << m, 998244353)
ans = 0
for i in range(1 << m):
    ans += i * h[i] % mod
    ans %= mod

print(ans)
0