結果

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

ソースコード

diff #
raw source code 

import sys

MOD = 998244353

def main():
    S = sys.stdin.readline().strip()
    
    # 'A' pozitsiyalarini topish
    positions = []
    for i, ch in enumerate(S):
        if ch == 'A':
            positions.append(i)
    
    n = len(positions)
    if n == 0:
        print(1)
        return
    
    # Har bir 'A' uchun B qiymatini hisoblash
    B = [0] * n
    for i in range(n):
        # pozitsiya - oldingi 'A' lar soni
        B[i] = positions[i] + 1 - i
    
    # DP: dp[x] = oxirgi qiymati x bo'lgan ketma-ketliklar soni
    max_val = max(B)
    dp = [0] * (max_val + 2)
    
    # Birinchi 'A' uchun
    start = 0  # A[0] = 0
    end = B[0]
    for x in range(start, end):
        dp[x] = 1
    
    # Prefix sum massivi
    prefix = [0] * (max_val + 2)
    
    # Keyingi 'A' lar uchun
    for i in range(1, n):
        # Prefix sumni yangilash
        prefix[0] = 0
        for x in range(max_val + 1):
            prefix[x + 1] = (prefix[x] + dp[x]) % MOD
        
        # Yangi DP qiymatlarini hisoblash
        new_dp = [0] * (max_val + 2)
        start = 0  # A[i] = 0 (masala shartiga ko'ra)
        end = B[i]
        
        for x in range(start, end):
            new_dp[x] = prefix[x + 1]  # barcha <= x qiymatlari yig'indisi
        
        dp = new_dp
    
    # Natija
    result = sum(dp) % MOD
    print(result)

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