提出 #75453474

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const long long INF = (1LL << 62) - (1LL << 31) - 1;
int di[4] = {-1,0,1,0};
int dj[4] = {0,-1,0,1};

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

int main() {
    int mod = 998244353;
    string s; cin >> s;
    int size = s.size();
    int l = 0, r = 0, nxt = 1;
    ll ans = 0;
    ll d = modinv(2, mod);
    while (l < size && r < size) {
        if (nxt >= size) {
            ll n = r - l + 1;
            ll cnt = ((n * (n+1)) % mod) * d % mod;
            ans += cnt;
            ans %= mod;
            r++;
            l = r;
            nxt = r + 1;
            continue;
        }
        while (s[r] != s[nxt]) {
            if (nxt > size - 1) break;
            r = nxt;
            if (nxt + 1 < size) {
                nxt++;
            }
        }
        ll n = r - l + 1;
        ll cnt = ((n * (n+1)) % mod) * d % mod;
        ans += cnt;
        ans %= mod;
        r++;
        l = r;
        nxt = r + 1;
    }
    cout << ans << endl;
    return 0;
}

提出情報

ジャッジ結果