結果

問題 No.1504 ヌメロニム
ユーザー gew1fw
提出日時 2025-06-12 19:15:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,674 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 171,460 KB
最終ジャッジ日時 2025-06-12 19:16:07
合計ジャッジ時間 5,566 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 WA * 1 TLE * 1 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def ntt(a, invert=False):
    n = len(a)
    log_n = (n).bit_length() - 1
    for i in range(n):
        j = 0
        for k in range(log_n):
            j |= ((i >> k) & 1) << (log_n - 1 - k)
        if i < j:
            a[i], a[j] = a[j], a[i]
    root = pow(3, (MOD - 1) // n, MOD) if not invert else pow(3, MOD - 1 - (MOD - 1) // n, MOD)
    roots = [1] * (n // 2)
    for k in range(1, n // 2):
        roots[k] = roots[k - 1] * root % MOD
    for m in range(1, log_n + 1):
        m_h = 1 << (m - 1)
        m_2 = 1 << m
        for i in range(0, n, m_2):
            for j in range(i, i + m_h):
                x = a[j]
                y = a[j + m_h] * roots[(j - i) * (n // m_2)] % MOD
                a[j] = (x + y) % MOD
                a[j + m_h] = (x - y) % MOD
    if invert:
        inv_n = pow(n, MOD - 2, MOD)
        for i in range(n):
            a[i] = a[i] * inv_n % MOD

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

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    S = input[1]

    max_fact = N
    fact = [1] * (max_fact + 1)
    for i in range(1, max_fact + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (max_fact + 1)
    inv_fact[max_fact] = pow(fact[max_fact], MOD-2, MOD)
    for i in range(max_fact-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

    A = [0] * N
    B = [0] * N
    for i in range(N):
        if S[i] == 'i':
            A[i] = 1
        if S[i] == 'n':
            B[i] = 1

    B_reversed = B[::-1]
    conv = convolution(A, B_reversed)
    C = [0] * (N-1)
    len_B = N
    for d in range(N-1):
        k = d + 1
        idx = len_B - 1 - k
        if 0 <= idx < len(conv):
            C[d] = conv[idx] % MOD

    D = [0] * (N-1)
    for d in range(N-1):
        if d < len(C):
            D[d] = C[d] * fact[d] % MOD
        else:
            D[d] = 0

    B2 = [inv_fact[l] for l in range(N)]
    B2_reversed = B2[::-1]
    conv2 = convolution(D, B2_reversed)

    sum_result = [0] * (N-1)
    len_B2 = N
    for k in range(N-1):
        pos = k + len_B2 - 1
        if pos < len(conv2):
            sum_result[k] = conv2[pos] % MOD
        else:
            sum_result[k] = 0

    X = [0] * (N-1)
    for k in range(N-1):
        X[k] = sum_result[k] * inv_fact[k] % MOD

    xor = 0
    for x in X:
        xor ^= x
    print(xor % MOD)

if __name__ == "__main__":
    main()
0