結果
問題 | No.1845 Long Substrings |
ユーザー |
👑 |
提出日時 | 2022-02-18 22:09:25 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 829 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 30,592 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-29 09:02:37 |
合計ジャッジ時間 | 2,163 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
#include <stdio.h> const int Mod = 1000000007; void add_BIT(int N, long long BIT[], int i, int k) { while (i <= N) { BIT[i] += k; i += (i & -i); } } long long sum_BIT(long long BIT[], int r) { long long sum = 0; while (r > 0) { sum += BIT[r]; r -= (r & -r); } return sum; } int main() { int i, N, A[200001]; char S[200003]; scanf("%d", &N); for (i = 1; i <= N; i++) scanf("%d", &(A[i])); scanf("%s", &(S[1])); int last[26] = {}, dp[200001]; long long BIT[200001] = {}; long long ans = 0; for (i = 1, dp[0] = 1; i <= N; i++) { dp[i] = (sum_BIT(BIT, i - 1) - sum_BIT(BIT, last[S[i] - 'a']) + dp[last[S[i] - 'a']]) % Mod; last[S[i] - 'a'] = i; ans += (long long)dp[i] * A[i] % Mod; add_BIT(N, BIT, i, (long long)dp[i] * A[i] % Mod); } printf("%lld\n", ans % Mod); fflush(stdout); return 0; }