Submission #75453474

Source Code Expand

#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;
}

Submission Info

Submission Time
Task C - Not Adjacent
User takakan448
Language C++23 (GCC 15.2.0)
Score 300
Code Size 1288 Byte
Status AC
Exec Time 6 ms
Memory 4032 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 2
AC × 28
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All min.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
min.txt AC 1 ms 3468 KiB
random_01.txt AC 5 ms 4004 KiB
random_02.txt AC 4 ms 3804 KiB
random_03.txt AC 5 ms 3788 KiB
random_04.txt AC 3 ms 3712 KiB
random_05.txt AC 5 ms 3880 KiB
random_06.txt AC 2 ms 3612 KiB
random_07.txt AC 5 ms 4032 KiB
random_08.txt AC 2 ms 3840 KiB
random_09.txt AC 5 ms 3904 KiB
random_10.txt AC 5 ms 3688 KiB
random_11.txt AC 6 ms 3880 KiB
random_12.txt AC 1 ms 3604 KiB
random_13.txt AC 6 ms 3948 KiB
random_14.txt AC 5 ms 3704 KiB
random_15.txt AC 6 ms 3948 KiB
random_16.txt AC 3 ms 3620 KiB
random_17.txt AC 6 ms 3960 KiB
random_18.txt AC 4 ms 3704 KiB
random_19.txt AC 6 ms 3908 KiB
random_20.txt AC 2 ms 3768 KiB
random_21.txt AC 6 ms 3924 KiB
random_22.txt AC 4 ms 3704 KiB
random_23.txt AC 6 ms 3920 KiB
random_24.txt AC 2 ms 3716 KiB
random_25.txt AC 6 ms 3908 KiB
sample_01.txt AC 1 ms 3468 KiB
sample_02.txt AC 1 ms 3380 KiB