結果

問題 No.2356 Back Door Tour in Four Seasons
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:41:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 250 ms / 2,000 ms
コード長 1,278 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 134,912 KB
最終ジャッジ日時 2025-03-31 17:43:14
合計ジャッジ時間 7,939 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    
    sum_A = 0
    U = []
    F = []
    W = []
    P_count = 0
    
    for _ in range(N):
        S_i = input[ptr]
        A_i = int(input[ptr+1])
        ptr += 2
        sum_A += A_i
        
        if S_i == 'U':
            U.append(A_i)
        elif S_i == 'F':
            F.append(A_i)
        elif S_i == 'W':
            W.append(A_i)
        elif S_i == 'P':
            P_count += 1
    
    # Compute inv(N-1)
    inv_N_1 = pow(N-1, MOD-2, MOD) if (N-1) != 0 else 0
    # base = (N-2) / (N-1) mod MOD
    base = ( ( (N - 2) % MOD ) * inv_N_1 ) % MOD
    
    def compute_sum(As):
        res = 0
        for a in As:
            x = pow(base, a, MOD)
            term = (1 - x) % MOD
            res = (res + term) % MOD
        return res
    
    u_sum = compute_sum(U)
    f_sum = compute_sum(F)
    w_sum = compute_sum(W)
    
    # Compute sum_S
    sum_S = u_sum * f_sum % MOD
    sum_S = sum_S * w_sum % MOD
    sum_S = sum_S * P_count % MOD
    
    # Compute P = (N-1)^sum_A mod MOD
    P = pow(N-1, sum_A, MOD)
    
    # Answer is (P * sum_S) mod MOD
    print((P * sum_S) % MOD)

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