結果

問題 No.1740 Alone 'a'
ユーザー lam6er
提出日時 2025-04-09 21:02:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 69 ms / 2,000 ms
コード長 1,888 bytes
コンパイル時間 392 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 82,380 KB
最終ジャッジ日時 2025-04-09 21:05:02
合計ジャッジ時間 4,286 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

n = int(input())
s = input().strip()

max_pow = 2 * 10**5 + 5
power25 = [1] * (max_pow)
for i in range(1, max_pow):
    power25[i] = (power25[i-1] * 25) % MOD

# Compute no_a_prefix for Case1 and Case2
no_a_prefix = [False] * (n + 1)
no_a_prefix[0] = True
for j in range(1, n + 1):
    no_a_prefix[j] = no_a_prefix[j-1] and (s[j-1] != 'a')

# Compute c array (number of valid chars less than s[j], not 'a')
c = [0] * n
for j in range(n):
    if s[j] == 'a':
        c[j] = 0
    else:
        c_val = ord(s[j]) - ord('a') - 1
        c[j] = max(0, c_val)

# Compute dp for Case2 (j < i) and prefix sum
dp_case2 = [0] * n
for j in range(n):
    if j <= n - 2:  # Ensure exponent is non-negative
        if no_a_prefix[j]:
            exponent = n - j - 2
            dp_case2[j] = (c[j] * power25[exponent]) % MOD
    else:
        dp_case2[j] = 0

prefix_case2 = [0] * (n + 1)
for j in range(n):
    prefix_case2[j+1] = (prefix_case2[j] + dp_case2[j]) % MOD

# Compute prefix_a for Case3
prefix_a = [0] * (n + 1)
for j in range(1, n + 1):
    prefix_a[j] = prefix_a[j-1] + (s[j-1] == 'a')

# Compute Case3: contribution when first differing j > i, with exactly one 'a' in s[0..j-1] and s[i] = 'a'
case3 = 0
for j in range(n):
    if prefix_a[j] == 1 and s[j] != 'a':
        exponent = (n - 1) - j
        if exponent < 0:
            term = 0
        else:
            term = (c[j] * power25[exponent]) % MOD
        case3 = (case3 + term) % MOD

total = 0

# Compute Case1 and Case2 for each i
for i in range(n):
    case1 = 0
    if no_a_prefix[i]:
        if i < n and s[i] > 'a':
            exponent_case1 = (n - 1 - i)
            if exponent_case1 >= 0:
                case1 = power25[exponent_case1] % MOD
    case2 = prefix_case2[i]  # sum of j < i
    total = (total + case1 + case2) % MOD

# Add Case3 contribution
total = (total + case3) % MOD

print(total)
0