結果

問題 No.1740 Alone 'a'
ユーザー lam6er
提出日時 2025-03-26 16:00:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,192 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 82,560 KB
最終ジャッジ日時 2025-03-26 16:01:23
合計ジャッジ時間 4,674 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

N = int(input())
S = input()

# Precompute has_a: has_a[pos] is True if S[0..pos-1] contains 'a'
has_a = [False] * (N + 1)
for pos in range(1, N + 1):
    has_a[pos] = has_a[pos-1] or (S[pos-1] == 'a')

# Precompute pow25: pow25[k] = 25^k mod MOD
pow25 = [1] * (N + 1)
for k in range(1, N + 1):
    pow25[k] = (pow25[k-1] * 25) % MOD

# Precompute g array: g[pos] is the number of non-a strings of length pos lex smaller than S's prefix of length pos
g = [0] * (N + 1)
for pos in range(1, N + 1):
    current_char = S[pos-1]
    if current_char == 'a':
        g[pos] = 0
    else:
        prefix_equal = 1 if not has_a[pos] else 0
        current_c = ord(current_char) - ord('b')
        if current_c < 0:
            current_c = 0
        term = (g[pos-1] * 25) % MOD
        term = (term + prefix_equal * current_c) % MOD
        g[pos] = term

# Precompute f array: f[i] is the number of non-a strings lex smaller than S's suffix starting at i
f = [0] * (N + 2)  # Using N+2 to avoid index issues
for i in range(N-1, -1, -1):
    if S[i] == 'a':
        f[i] = 0
    else:
        m = N - i
        current_char = S[i]
        current_c = ord(current_char) - ord('b')
        if current_c < 0:
            current_c = 0
        term = (current_c * pow25[m-1]) % MOD
        if current_char >= 'b' and current_char <= 'z':
            term = (term + f[i+1]) % MOD
        f[i] = term

ans = 0
for pos in range(N):
    current_has_a = has_a[pos]
    # Case 1: contribution from prefix being lex smaller than S's prefix (0..pos-1)
    if not current_has_a:
        prefix_less = g[pos]
    else:
        prefix_less = 0
    suffix_length = N - pos - 1
    pow_suffix = pow25[suffix_length] if suffix_length >= 0 else 1
    case1 = (prefix_less * pow_suffix) % MOD

    # Case 2: contribution from prefix being equal to S's prefix (non-a) and then 'a' at pos
    case2 = 0
    if not current_has_a:
        if S[pos] > 'a':
            case2 = pow_suffix
        elif S[pos] == 'a':
            suffix_start = pos + 1
            case2 = f[suffix_start] if suffix_start <= N else 0
    case2 %= MOD

    total = (case1 + case2) % MOD
    ans = (ans + total) % MOD

print(ans)
0