結果

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

ソースコード

diff #
raw source code 

MOD = 998244353

class ModInt:
    def __init__(self, x):
        self.x = x % MOD
    def __add__(self, other):
        return ModInt(self.x + other.x)
    def __sub__(self, other):
        return ModInt(self.x - other.x)
    def __mul__(self, other):
        return ModInt(self.x * other.x)
    def __repr__(self):
        return str(self.x)
    def __getitem__(self, i):
        return self.x[i]
    def __len__(self):
        return len(self.x)

def convolution(a, b):
    # Naive convolution (Rust NTT o'rniga)
    n, m = len(a), len(b)
    res = [ModInt(0) for _ in range(n + m - 1)]
    for i in range(n):
        for j in range(m):
            res[i+j] += a[i]*b[j]
    return res

def calc(a, b, f, g):
    n = len(a)
    a = list(a)
    b = list(b)
    for i in range(1, n):
        a[i] = max(a[i-1], a[i])
        b[i] = min(b[i-1] + len(g)-1, b[i])
    for i in reversed(range(1, n)):
        a[i-1] = max(a[i-1], a[i]-len(g)+1)
        b[i-1] = min(b[i-1], b[i])
    if any(x>=y for x,y in zip(a,b)):
        return []

    state = [ModInt(0)]*(b[-1])
    for i in range(len(f)):
        if i < len(state):
            state[i] = f[i]
    # Rustdagi recursive multiplications va truncations sodda shaklda:
    for i in range(n):
        state = convolution(state, g)
        l, r = a[i], b[i]
        state = state[l:r]
    return state

s = input().strip()
h = 1
a = []
b = []
for c in s:
    if c=='B':
        h += 1
    else:
        a.append(0)
        b.append(h)
if not a:
    print(1)
    exit()

n = len(b)
len_total = n + b[-1]
l = [0]*len_total
r = [10**9]*len_total
l[len_total-1] = b[-1]-1
for i,(aa,bb) in enumerate(zip(a,b)):
    l[i+aa] = aa
    r[i+bb] = bb

f0 = [ModInt(1)]
g = [ModInt(1), ModInt(1)]
ans_poly = calc(l,r,f0,g)
ans = ModInt(0)
for x in ans_poly:
    ans += x
print(ans)
0