結果
問題 |
No.1845 Long Substrings
|
ユーザー |
![]() |
提出日時 | 2025-04-09 21:02:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 741 bytes |
コンパイル時間 | 478 ms |
コンパイル使用メモリ | 82,244 KB |
実行使用メモリ | 121,688 KB |
最終ジャッジ日時 | 2025-04-09 21:03:59 |
合計ジャッジ時間 | 4,231 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
MOD = 10**9 + 7 def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 A = list(map(int, input[idx:idx+N])) idx += N S = input[idx] total = 1 from collections import defaultdict last = defaultdict(int) for i in range(N): c = S[i] m = A[i] prev_total = total prev_last = last[c] new_total = ( ( (m + 1) * prev_total - m * prev_last ) % MOD + MOD ) % MOD new_last = ( ( m * prev_total - (m - 1) * prev_last ) % MOD + MOD ) % MOD total = new_total last[c] = new_last answer = (total - 1 + MOD) % MOD print(answer) if __name__ == "__main__": main()