結果

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

ソースコード

diff #
raw source code 

import sys

MOD = 998244353

def main():
    S = sys.stdin.readline().strip()
    
    # 'A' lar uchun B qiymatlarini hisoblash
    B = []
    cnt = 0
    for i, ch in enumerate(S):
        if ch == 'A':
            # i+1 - cnt = pozitsiya - oldingi 'A' lar soni
            B.append(i + 1 - cnt)
            cnt += 1
    
    N = len(B)
    if N == 0:
        print(1)
        return
    
    # A massivini yaratish (eng kichik qiymatlar)
    A = [0] * N
    for i in range(1, N):
        A[i] = max(A[i], A[i - 1])
    
    # DP[j] = oxirgi elementi j bo'lgan ketma-ketliklar soni
    max_val = B[-1]
    dp = [0] * (max_val + 2)
    
    # Birinchi 'A' uchun boshlang'ich holat
    for j in range(A[0], B[0]):
        dp[j] = 1
    
    # Har bir keyingi 'A' uchun
    for i in range(1, N):
        new_dp = [0] * (max_val + 2)
        
        # Prefix sum hisoblash
        prefix = [0] * (max_val + 2)
        for j in range(max_val + 1):
            prefix[j + 1] = (prefix[j] + dp[j]) % MOD
        
        # Yangi qiymatlarni hisoblash
        for j in range(A[i], B[i]):
            # Barcha oldingi qiymatlar <= j uchun
            new_dp[j] = prefix[j + 1] % MOD
        
        dp = new_dp
    
    # Natijani hisoblash
    result = sum(dp) % MOD
    print(result)

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