結果

問題 No.1958 Bit Game
ユーザー 8nd5t8nd5t
提出日時 2022-05-27 22:17:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 656 ms / 2,000 ms
コード長 2,067 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 158,796 KB
最終ジャッジ日時 2024-09-20 16:02:34
合計ジャッジ時間 17,204 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right
import sys,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_1(): return list(map(lambda x:int(x)-1, sys.stdin.readline().split()))
def err(x): print(x); exit()

class Combination:
    """
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

mod = 998244353
m = 18
n,x,y = inpl()
a = inpl()
b = inpl()
res = 0
p = [1]
for i in range(n):
    p.append(p[-1]*x*y%mod)
for d in range(m):
    cnta = cntb = 0
    ans = 0
    for aa in a:
        if (aa>>d)%2:
            cnta += 1
    for bb in b:
        if (bb>>d)%2:
            cntb += 1
    if cnta == 0 or cntb == 0:
        continue
    zero = pow(x-cnta,n-1,mod)
    one = pow(cntb,n,mod)
    inv_x_cnta = pow(x-cnta,mod-2,mod)
    inv_cntb = pow(cntb,mod-2,mod)
    for i in range(n):
        ans += p[i]*cnta%mod*one%mod*zero
        ans %= mod
        zero = zero*inv_x_cnta%mod
        one = one*inv_cntb%mod
    res += ans*pow(2,d,mod)
    res %= mod
print(res)
0