結果
問題 |
No.1171 Runs in Subsequences
|
ユーザー |
|
提出日時 | 2024-04-02 22:35:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 558 bytes |
コンパイル時間 | 2,338 ms |
コンパイル使用メモリ | 197,112 KB |
最終ジャッジ日時 | 2025-02-20 19:42:16 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using ll = long long; using namespace atcoder; using mint = modint; int main() { mint::set_mod((ll)1e9 + 7); string S;cin >> S; int N = S.size(); vector<mint> dp(N + 1, 0); mint ans = 0; vector<mint> T(26, 0); vector<mint> U(26, 0); for (int i = 1;i <= N;i++) { dp[i]++; int now = S[i - 1] - 'a'; for (int c = 0;c < 26;c++) { dp[i] += T[c] + (c == now ? 0 : U[c]); } T[now] += dp[i]; U[now] += mint(2).pow(i - 1); ans += dp[i]; } cout << ans.val() << endl; }