結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 623 ms
158,208 KB
testcase_01 AC 629 ms
158,520 KB
testcase_02 AC 632 ms
158,336 KB
testcase_03 AC 634 ms
158,464 KB
testcase_04 AC 656 ms
158,080 KB
testcase_05 AC 642 ms
158,336 KB
testcase_06 AC 628 ms
158,796 KB
testcase_07 AC 629 ms
158,336 KB
testcase_08 AC 632 ms
158,460 KB
testcase_09 AC 627 ms
158,080 KB
testcase_10 AC 305 ms
99,484 KB
testcase_11 AC 380 ms
108,320 KB
testcase_12 AC 393 ms
123,648 KB
testcase_13 AC 459 ms
127,360 KB
testcase_14 AC 429 ms
111,616 KB
testcase_15 AC 352 ms
137,452 KB
testcase_16 AC 268 ms
109,292 KB
testcase_17 AC 561 ms
149,416 KB
testcase_18 AC 485 ms
148,480 KB
testcase_19 AC 323 ms
128,388 KB
testcase_20 AC 547 ms
122,368 KB
testcase_21 AC 403 ms
145,368 KB
testcase_22 AC 375 ms
106,260 KB
testcase_23 AC 284 ms
105,776 KB
testcase_24 AC 566 ms
132,096 KB
testcase_25 AC 326 ms
104,704 KB
testcase_26 AC 492 ms
124,932 KB
testcase_27 AC 316 ms
131,180 KB
testcase_28 AC 538 ms
127,104 KB
testcase_29 AC 360 ms
107,520 KB
testcase_30 AC 155 ms
84,352 KB
testcase_31 AC 150 ms
84,736 KB
testcase_32 AC 146 ms
85,248 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