結果

問題 No.3041 非対称じゃんけん
コンテスト
ユーザー timi
提出日時 2025-02-28 22:04:45
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,122 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 74,640 KB
最終ジャッジ日時 2025-02-28 22:04:48
合計ジャッジ時間 3,313 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 28 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    from sys import stdin, setrecursionlimit
    input = stdin.readline
    readline = stdin.readline
    import sys
    sys.setrecursionlimit(10**7)
    from collections import deque
    # https://atcoder.jp/contests/practice2/submissions/16789717 より
    mod, g, ig = 998244353, 3, 332748118
    W = [pow(g, (mod-1)>>i, mod) for i in range(24)]
    iW = [pow(ig, (mod-1)>>i, mod) for i in range(24)]

    def NTT(k, A): # k: int, &A: List[int]
        for l in range(k, 0, -1):
            d = 1<<l - 1
            U = [1]
            for i in range(d):
                U.append(U[-1] * W[l] % mod)
            
            for i in range(1<<k - l):
                for j in range(d):
                    s = i*2*d + j
                    A[s], A[s+d] = (A[s]+A[s+d]) % mod, U[j] * (A[s]-A[s+d]) % mod

    def iNTT(k, A): # k: int, &A: List[int]
        for l in range(1, k + 1):
            d = 1<<l - 1
            for i in range(1<<k - l):
                u = 1
                for j in range(i*2*d, (i*2+1)*d):
                    A[j+d] *= u
                    A[j], A[j+d] = (A[j]+A[j+d]) % mod, (A[j]-A[j+d]) % mod
                    u = u * iW[l] % mod

    def convolve(A, B): # A,B: List[int]
        n0 = len(A) + len(B) - 1
        k = (n0).bit_length()
        n = 1 << k
        A = A + [0] * (n-len(A))
        B = B + [0] * (n-len(B))
        C = [0] * n # Aをそのまま使ったほうが早い
        NTT(k, A)
        NTT(k, B)
        for i in range(n):
            C[i] = A[i] * B[i] % mod
        iNTT(k, C)
        invn = pow(n, mod-2, mod) # fftとifftの係数1/Nの分
        for i in range(n0):
            C[i] = C[i] * invn % mod
        return C[:n0] # List[int]

    N,F = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    C = list(map(int,input().split()))
    D=[1];c=1
    for i in range(3):
      E=[0]*61
      E[A[i]]+=1;E[B[i]]+=1;E[C[i]]+=1
      c+=max(A[i],B[i],C[i])
      D=list(convolve(D,E))
      D=D[:c]
      ans=0 
      for d in D:
        if d!=0:
          ans+=1 
      print(ans)
main()
0