Submission #75446772

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LONGMAX 1e18
#define INTMAX 2147483647

int main(void)
{
    ll MOD = 998244353;
    string S;
    cin >> S;
    vector<ll> dp(3, 0); // a:0, b:1, c:2
    // 最後がaで終わる部分列の数がdp[0]
    // S[i]がaだったら、dp[a] = 1 + dp[b] + dp[c]
    // その文字自体と、そのときのdp[ほかのやつ]を加えるといい
    // この1をdp[a]にすると連続部分列を含むことになる
    for (ll i = 0, n = S.length(); i < n; i++)
    {
        if (S[i] == 'a')
        {
            dp[0] += (1 + dp[1] + dp[2]) % MOD;
            dp[0] %= MOD;
        }
        else if (S[i] == 'b')
        {
            dp[1] += (1 + dp[0] + dp[2]) % MOD;
            dp[1] %= MOD;
        }
        else
        {
            dp[2] += (1 + dp[0] + dp[1]) % MOD;
            dp[2] %= MOD;
        }
    }
    cout << (dp[0] + dp[1] + dp[2]) % MOD << endl;
    return 0;
}

Submission Info

Judge Result