結果

問題 No.1958 Bit Game
ユーザー 8nd5t8nd5t
提出日時 2022-05-27 22:17:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 977 ms / 2,000 ms
コード長 2,067 bytes
コンパイル時間 275 ms
コンパイル使用メモリ 81,628 KB
実行使用メモリ 157,516 KB
最終ジャッジ日時 2023-10-20 20:24:04
合計ジャッジ時間 18,961 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 977 ms
157,516 KB
testcase_01 AC 680 ms
157,512 KB
testcase_02 AC 694 ms
157,504 KB
testcase_03 AC 689 ms
157,508 KB
testcase_04 AC 720 ms
157,512 KB
testcase_05 AC 666 ms
157,356 KB
testcase_06 AC 683 ms
157,504 KB
testcase_07 AC 666 ms
157,516 KB
testcase_08 AC 667 ms
157,512 KB
testcase_09 AC 669 ms
157,508 KB
testcase_10 AC 309 ms
98,272 KB
testcase_11 AC 400 ms
107,288 KB
testcase_12 AC 390 ms
122,924 KB
testcase_13 AC 481 ms
127,168 KB
testcase_14 AC 431 ms
110,756 KB
testcase_15 AC 341 ms
136,500 KB
testcase_16 AC 272 ms
108,624 KB
testcase_17 AC 555 ms
148,400 KB
testcase_18 AC 503 ms
148,268 KB
testcase_19 AC 333 ms
125,340 KB
testcase_20 AC 524 ms
121,580 KB
testcase_21 AC 390 ms
144,360 KB
testcase_22 AC 372 ms
105,252 KB
testcase_23 AC 277 ms
104,012 KB
testcase_24 AC 542 ms
131,112 KB
testcase_25 AC 309 ms
103,620 KB
testcase_26 AC 498 ms
124,300 KB
testcase_27 AC 330 ms
129,924 KB
testcase_28 AC 545 ms
126,092 KB
testcase_29 AC 368 ms
106,776 KB
testcase_30 AC 148 ms
83,912 KB
testcase_31 AC 149 ms
83,920 KB
testcase_32 AC 153 ms
84,380 KB
権限があれば一括ダウンロードができます

ソースコード

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