結果
問題 |
No.1171 Runs in Subsequences
|
ユーザー |
|
提出日時 | 2025-07-02 09:56:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 843 bytes |
コンパイル時間 | 3,317 ms |
コンパイル使用メモリ | 281,272 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-07-02 09:56:28 |
合計ジャッジ時間 | 4,425 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/segtree> #include <atcoder/modint> using namespace std; const int M = 26; constexpr int md = 1e9 + 7; using mint = atcoder::static_modint<md>; struct Monoid { mint sum, cnt; static Monoid op(Monoid a, Monoid b) { return Monoid{a.sum + b.sum, a.cnt + b.cnt}; } static Monoid e() { return Monoid{0, 0}; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); string S; cin >> S; atcoder::segtree<Monoid, Monoid::op, Monoid::e> dp(M); for(char ch: S) { Monoid cur = dp.get(ch - 'a'); Monoid all = dp.all_prod(); all.sum -= cur.sum; all.cnt -= cur.cnt; cur.sum *= 2, cur.cnt *= 2; cur.sum += all.sum + all.cnt; cur.cnt += all.cnt; cur.sum += 1, cur.cnt += 1; dp.set(ch - 'a', cur); } mint ans = dp.all_prod().sum; cout << ans.val() << "\n"; }