結果
問題 |
No.1171 Runs in Subsequences
|
ユーザー |
|
提出日時 | 2020-11-17 15:14:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 723 bytes |
コンパイル時間 | 677 ms |
コンパイル使用メモリ | 79,412 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 08:17:42 |
合計ジャッジ時間 | 1,575 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; long long l[200020]; long long r[200020]; long long sum[30] = {}; int main() { string s; cin >> s; long long n = s.size(); long long t = 1; for (int i = 0; i < n; i++) { l[i] = t; r[n - i - 1] = t; t *= 2; t %= 1000000007; } long long ans = 1; for (int i = 1; i < n; i++) { ans *= 2; ans %= 1000000007; } ans *= n; ans %= 1000000007; for (int i = 0; i < n; i++) { int num = int(s[i] - 'a'); ans -= sum[num] * r[i] % 1000000007; sum[num] += l[i]; sum[num] %= 1000000007; ans %= 1000000007; } if (ans < 0) { ans += 1000000007; } cout << ans << endl; }