結果
問題 | No.1848 Long Prefixes |
ユーザー | 👑 rin204 |
提出日時 | 2024-05-05 17:01:35 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 9,796 bytes |
コンパイル時間 | 3,327 ms |
コンパイル使用メモリ | 257,284 KB |
実行使用メモリ | 14,408 KB |
最終ジャッジ日時 | 2024-05-05 17:01:42 |
合計ジャッジ時間 | 6,230 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 34 ms
14,408 KB |
testcase_01 | AC | 25 ms
14,404 KB |
testcase_02 | AC | 36 ms
14,272 KB |
testcase_03 | AC | 35 ms
14,400 KB |
testcase_04 | AC | 25 ms
14,404 KB |
testcase_05 | AC | 38 ms
13,808 KB |
testcase_06 | AC | 35 ms
13,384 KB |
testcase_07 | AC | 25 ms
13,812 KB |
testcase_08 | AC | 34 ms
13,508 KB |
testcase_09 | AC | 33 ms
13,740 KB |
testcase_10 | AC | 28 ms
13,972 KB |
testcase_11 | AC | 34 ms
13,964 KB |
testcase_12 | AC | 31 ms
13,364 KB |
testcase_13 | AC | 23 ms
13,772 KB |
testcase_14 | AC | 37 ms
13,968 KB |
testcase_15 | AC | 3 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 1 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 1 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 1 ms
5,376 KB |
testcase_32 | AC | 1 ms
5,376 KB |
testcase_33 | AC | 16 ms
7,872 KB |
testcase_34 | AC | 20 ms
11,372 KB |
testcase_35 | AC | 7 ms
5,376 KB |
testcase_36 | AC | 13 ms
7,556 KB |
testcase_37 | AC | 15 ms
9,992 KB |
testcase_38 | AC | 17 ms
9,072 KB |
testcase_39 | AC | 15 ms
7,684 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <int MOD> struct Modint { int x; Modint() : x(0) {} Modint(int64_t y) { if (y >= 0) x = y % MOD; else x = (y % MOD + MOD) % MOD; } Modint &operator+=(const Modint &p) { x += p.x; if (x >= MOD) x -= MOD; return *this; } Modint &operator-=(const Modint &p) { x -= p.x; if (x < 0) x += MOD; return *this; } Modint &operator*=(const Modint &p) { x = int(1LL * x * p.x % MOD); return *this; } Modint &operator/=(const Modint &p) { *this *= p.inverse(); return *this; } Modint &operator%=(const Modint &p) { assert(p.x == 0); return *this; } Modint operator-() const { return Modint(-x); } Modint &operator++() { x++; if (x == MOD) x = 0; return *this; } Modint &operator--() { if (x == 0) x = MOD; x--; return *this; } Modint operator++(int) { Modint result = *this; ++*this; return result; } Modint operator--(int) { Modint result = *this; --*this; return result; } friend Modint operator+(const Modint &lhs, const Modint &rhs) { return Modint(lhs) += rhs; } friend Modint operator-(const Modint &lhs, const Modint &rhs) { return Modint(lhs) -= rhs; } friend Modint operator*(const Modint &lhs, const Modint &rhs) { return Modint(lhs) *= rhs; } friend Modint operator/(const Modint &lhs, const Modint &rhs) { return Modint(lhs) /= rhs; } friend Modint operator%(const Modint &lhs, const Modint &rhs) { assert(rhs.x == 0); return Modint(lhs); } bool operator==(const Modint &p) const { return x == p.x; } bool operator!=(const Modint &p) const { return x != p.x; } bool operator<(const Modint &rhs) const { return x < rhs.x; } bool operator<=(const Modint &rhs) const { return x <= rhs.x; } bool operator>(const Modint &rhs) const { return x > rhs.x; } bool operator>=(const Modint &rhs) const { return x >= rhs.x; } Modint inverse() const { int a = x, b = MOD, u = 1, v = 0, t; while (b > 0) { t = a / b; a -= t * b; u -= t * v; std::swap(a, b); std::swap(u, v); } return Modint(u); } Modint pow(int64_t k) const { Modint ret(1); Modint y(x); while (k > 0) { if (k & 1) ret *= y; y *= y; k >>= 1; } return ret; } friend std::ostream &operator<<(std::ostream &os, const Modint &p) { return os << p.x; } friend std::istream &operator>>(std::istream &is, Modint &p) { int64_t y; is >> y; p = Modint<MOD>(y); return (is); } static int get_mod() { return MOD; } }; struct Arbitrary_Modint { int x; static int MOD; static void set_mod(int mod) { MOD = mod; } Arbitrary_Modint() : x(0) {} Arbitrary_Modint(int64_t y) { if (y >= 0) x = y % MOD; else x = (y % MOD + MOD) % MOD; } Arbitrary_Modint &operator+=(const Arbitrary_Modint &p) { x += p.x; if (x >= MOD) x -= MOD; return *this; } Arbitrary_Modint &operator-=(const Arbitrary_Modint &p) { x -= p.x; if (x < 0) x += MOD; return *this; } Arbitrary_Modint &operator*=(const Arbitrary_Modint &p) { x = int(1LL * x * p.x % MOD); return *this; } Arbitrary_Modint &operator/=(const Arbitrary_Modint &p) { *this *= p.inverse(); return *this; } Arbitrary_Modint &operator%=(const Arbitrary_Modint &p) { assert(p.x == 0); return *this; } Arbitrary_Modint operator-() const { return Arbitrary_Modint(-x); } Arbitrary_Modint &operator++() { x++; if (x == MOD) x = 0; return *this; } Arbitrary_Modint &operator--() { if (x == 0) x = MOD; x--; return *this; } Arbitrary_Modint operator++(int) { Arbitrary_Modint result = *this; ++*this; return result; } Arbitrary_Modint operator--(int) { Arbitrary_Modint result = *this; --*this; return result; } friend Arbitrary_Modint operator+(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) { return Arbitrary_Modint(lhs) += rhs; } friend Arbitrary_Modint operator-(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) { return Arbitrary_Modint(lhs) -= rhs; } friend Arbitrary_Modint operator*(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) { return Arbitrary_Modint(lhs) *= rhs; } friend Arbitrary_Modint operator/(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) { return Arbitrary_Modint(lhs) /= rhs; } friend Arbitrary_Modint operator%(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) { assert(rhs.x == 0); return Arbitrary_Modint(lhs); } bool operator==(const Arbitrary_Modint &p) const { return x == p.x; } bool operator!=(const Arbitrary_Modint &p) const { return x != p.x; } bool operator<(const Arbitrary_Modint &rhs) { return x < rhs.x; } bool operator<=(const Arbitrary_Modint &rhs) { return x <= rhs.x; } bool operator>(const Arbitrary_Modint &rhs) { return x > rhs.x; } bool operator>=(const Arbitrary_Modint &rhs) { return x >= rhs.x; } Arbitrary_Modint inverse() const { int a = x, b = MOD, u = 1, v = 0, t; while (b > 0) { t = a / b; a -= t * b; u -= t * v; std::swap(a, b); std::swap(u, v); } return Arbitrary_Modint(u); } Arbitrary_Modint pow(int64_t k) const { Arbitrary_Modint ret(1); Arbitrary_Modint y(x); while (k > 0) { if (k & 1) ret *= y; y *= y; k >>= 1; } return ret; } friend std::ostream &operator<<(std::ostream &os, const Arbitrary_Modint &p) { return os << p.x; } friend std::istream &operator>>(std::istream &is, Arbitrary_Modint &p) { int64_t y; is >> y; p = Arbitrary_Modint(y); return (is); } static int get_mod() { return MOD; } }; int Arbitrary_Modint::MOD = 998244353; using modint9 = Modint<998244353>; using modint1 = Modint<1000000007>; using modint = Arbitrary_Modint; std::vector<int> Z_algorithm(const std::string &S) { int n = S.size(); std::vector<int> Z(n); Z[0] = n; int i = 1; int j = 0; while (i < n) { while (i + j < n && S[j] == S[i + j]) j++; Z[i] = j; if (j == 0) { i++; continue; } int k = 1; while (i + k < n && k + Z[k] < j) { Z[i + k] = Z[k]; k++; } i += k; j -= k; } return Z; } template <typename T> std::vector<int> Z_algorithm(const std::vector<T> &S) { int n = S.size(); std::vector<int> Z(n); Z[0] = n; int i = 1; int j = 0; while (i < n) { while (i + j < n && S[j] == S[i + j]) j++; Z[i] = j; if (j == 0) { i++; continue; } int k = 1; while (i + k < n && k + Z[k] < j) { Z[i + k] = Z[k]; k++; } i += k; j -= k; } return Z; } using mint = modint1; void solve() { int n; cin >> n; vector<ll> A(n); for (auto &a : A) cin >> a; string S; cin >> S; mint ans = 0; vector<pair<long long, char>> B; char b = S[0]; long long row = 0; for (int i = 0; i < n; i++) { if (b == S[i]) { row += A[i]; } else { B.emplace_back(row, b); b = S[i]; row = A[i]; } } B.emplace_back(row, b); n = B.size(); if (n == 1) { mint ans = B[0].first * (B[0].first + 1) / 2; cout << ans << endl; return; } vector<ll> cum(n + 1, 0); for (int i = 0; i < n; i++) { cum[i + 1] = cum[i] + B[i].first; } auto Z = Z_algorithm(B); auto B2 = B; B2.erase(B2.begin()); auto Z2 = Z_algorithm(B2); for (int i = 0; i < n; i++) { int z = Z[i]; ans += cum[i + z] - cum[i]; if (i + z < n and B[z].second == B[i + z].second) { ans += min(B[z].first, B[i + z].first); } if (B[0].second == B[i].second) { ll x = B[0].first; ll y = B[i].first - 1; if (x < y) { ans += x * (y - x); y = x; } ans += y * (y + 1) / 2; if (B[0].first < B[i].first) { ll z = Z2[i]; mint tmp = cum[i + 1 + z] - cum[i + 1]; if (B[z + 1].second == B[i + z + 1].second) { tmp += min(B[z + 1].first, B[i + z + 1].first); } ans += tmp; } } // cout << i << " " << ans << endl; } cout << ans << endl; } int main() { cin.tie(0)->sync_with_stdio(0); cout << fixed << setprecision(12); int t; t = 1; // cin >> t; while (t--) solve(); return 0; }