結果

問題 No.3370 AB → BA
コンテスト
ユーザー Aralov Otabek
提出日時 2026-01-08 23:31:54
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 1,129 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 283 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 54,652 KB
最終ジャッジ日時 2026-01-08 23:31:57
合計ジャッジ時間 1,955 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353
PRIMITIVE_ROOT = 3

def modinv(x):
    return pow(x, MOD-2, MOD)

def ntt(a, invert):
    n = len(a)
    j = 0
    for i in range(1,n):
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j ^= bit
        if i < j:
            a[i],a[j] = a[j],a[i]
    length = 2
    while length <= n:
        wlen = pow(PRIMITIVE_ROOT,(MOD-1)//length,MOD)
        if invert:
            wlen = modinv(wlen)
        for i in range(0,n,length):
            w = 1
            for j in range(i,i+length//2):
                u = a[j]
                v = a[j+length//2]*w % MOD
                a[j] = (u+v) % MOD
                a[j+length//2] = (u-v+MOD)%MOD
                w = w*wlen % MOD
        length <<= 1
    if invert:
        ninv = modinv(n)
        for i in range(n):
            a[i] = a[i]*ninv % MOD

def convolution(a,b):
    n = 1
    while n < len(a)+len(b)-1:
        n <<= 1
    fa = a+[0]*(n-len(a))
    fb = b+[0]*(n-len(b))
    ntt(fa,False)
    ntt(fb,False)
    for i in range(n):
        fa[i] = fa[i]*fb[i] % MOD
    ntt(fa,True)
    return fa[:len(a)+len(b)-1]
0