結果

問題 No.1171 Runs in Subsequences
ユーザー lam6er
提出日時 2025-03-20 21:11:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 79 ms / 2,000 ms
コード長 877 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 88,616 KB
最終ジャッジ日時 2025-03-20 21:13:20
合計ジャッジ時間 2,242 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

S = input().strip()
N = len(S)

# Precompute powers of 2 modulo MOD up to N
pow2 = [1] * (N + 2)
for i in range(1, N + 2):
    pow2[i] = (pow2[i-1] * 2) % MOD

from collections import defaultdict

char_positions = defaultdict(list)
for idx, c in enumerate(S):
    char_positions[c].append(idx)

sum_sub = 0

for c in char_positions:
    positions = char_positions[c]
    sum_c = 0
    for j in range(len(positions)):
        pos = positions[j]
        if j == 0:
            sum_c = pow2[pos]
            continue
        exponent = N - pos - 1
        if exponent < 0:
            term = 0
        else:
            term = (sum_c * pow2[exponent]) % MOD
        sum_sub = (sum_sub + term) % MOD
        sum_c = (sum_c + pow2[pos]) % MOD

# Compute N * pow2[N-1] mod MOD
pow_N_1 = pow2[N-1]
total = (pow_N_1 * N) % MOD
ans = (total - sum_sub) % MOD

print(ans)
0