結果

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

ソースコード

diff #
raw source code 

import sys

MOD = 998244353

def main():
    s = sys.stdin.readline().strip()
    n = len(s)
    
    # A va B lar pozitsiyalari
    a_pos = []
    b_pos = []
    for i, ch in enumerate(s):
        if ch == 'A':
            a_pos.append(i)
        else:
            b_pos.append(i)
    
    k = len(a_pos)  # A lar soni
    m = len(b_pos)  # B lar soni
    
    # A lar uchun DP
    # dpA[x] = oxirgi A x pozitsiyada bo'lgan usullar soni
    max_a = n  # maksimal pozitsiya
    dpA = [0] * (max_a + 1)
    
    # Boshlang'ich: birinchi A uchun
    if k > 0:
        first_a_limit = a_pos[0]  # x ≤ a_pos[0]
        for x in range(first_a_limit + 1):
            dpA[x] = 1
    
    # Keyingi A lar uchun
    for i in range(1, k):
        new_dpA = [0] * (max_a + 1)
        limit = a_pos[i]
        
        # Prefix sum
        prefix = 0
        for x in range(max_a + 1):
            prefix = (prefix + dpA[x]) % MOD
            if x <= limit:
                new_dpA[x] = prefix
        
        dpA = new_dpA
    
    # B lar uchun DP (o'ngdan chapga)
    dpB = [0] * (max_a + 1)
    
    if m > 0:
        last_b_limit = b_pos[-1]  # y ≥ b_pos[-1]
        for y in range(last_b_limit, n):
            dpB[y] = 1
    
    # B lar uchun orqaga
    for i in range(m - 2, -1, -1):
        new_dpB = [0] * (max_a + 1)
        limit = b_pos[i]
        
        # Suffix sum
        suffix = 0
        for y in range(n - 1, -1, -1):
            suffix = (suffix + dpB[y]) % MOD
            if y >= limit:
                new_dpB[y] = suffix
        
        dpB = new_dpB
    
    # Natijani hisoblash
    result = 0
    if k == 0:
        # Faqat B lar bor
        for i in range(n):
            result = (result + dpB[i]) % MOD
    elif m == 0:
        # Faqat A lar bor
        for i in range(n):
            result = (result + dpA[i]) % MOD
    else:
        # A lar va B lar
        # Har bir pozitsiya uchun: bu A bo'lishi yoki B bo'lishi mumkin
        # Lekin A va B lar S dagi tartibda bo'lishi kerak
        
        # S tartibida joylashish sharti
        # X dagi har bir pozitsiya S dagi mos keladigan belgiga ega
        
        # Oddiyroq yondashuv: kombinatorika
        # A lar va B lar uchun mustaqil hisoblab, keyin ularni birlashtiramiz
        
        total_a = sum(dpA) % MOD
        total_b = sum(dpB) % MOD
        
        # A lar va B lar joylashishi mumkin bo'lgan o'rinlar
        # Har bir A va B uchun o'z pozitsiyasi bor
        # A lar va B lar o'zaro joylashishi mumkin
        
        # Aslida, masalani soddaroq hisoblash mumkin
        
        # X dagi har bir belgi S dagi mos keladigan belgiga ega
        # Shunday qilib, X dagi i-pozitsiyadagi belgi S dagi i-pozitsiyadagi belgidan katta yoki teng bo'lishi kerak
        # (A uchun chapga, B uchun o'ngga siljishi mumkin)
        
        # DP[i] = S ning birinchi i belgisiga mos X ning birinchi i belgisini joylashtirish usullari
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(n):
            # X[i] da nima bo'lishi mumkin?
            if s[i] == 'A':
                # X[i] = A bo'lishi kerak
                dp[i + 1] = dp[i]
            else:  # s[i] == 'B'
                # X[i] = B bo'lishi kerak
                dp[i + 1] = dp[i]
            
            # Agar i > 0 va s[i-1:i+1] = "AB" bo'lsa, X[i-1] = B, X[i] = A bo'lishi mumkin
            # Bu holda AB -> BA bo'lgan
            if i > 0 and s[i-1] == 'A' and s[i] == 'B':
                # X[i-1] = B, X[i] = A
                # Bu holda (i-2) gacha bo'lgan istalgan joylashtirishdan keyin
                dp[i + 1] = (dp[i + 1] + dp[i-1]) % MOD
        
        result = dp[n]
    
    print(result % MOD)

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