Submission #2374698


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<map>
#include<bitset>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef pair<int,int> pint;
typedef long long ll;
const int inf   = 1e9+7;
const ll  longinf = 1LL<<60;
const ll mod=998244353;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

int main(){
  string s;cin>>s;
  int n=s.size();
  if(n==3){
    if(s[0]==s[1]&&s[1]==s[2])cout<<1<<endl;
    else if(s[0]==s[1]||s[1]==s[2])cout<<6<<endl;
    else if(s[0]==s[2])cout<<7<<endl;
    else cout<<3<<endl;
    return 0;
    }
  
  int b=0;
  rep(i,n){
    if(s[i]=='a')b+=2;
    if(s[i]=='b')b++;
    }
  ll ok=1,flag=1;
  rep(i,n-1){
    if(s[i]==s[i+1])flag=0;
    if(s[i]!=s[i+1])ok=0;
    }
  if(ok){
    cout<<1<<endl;
    return 0;
    }
  b%=3;
  ll dp[n][3][3],dpp[n][3][3];
  rep(i,3)rep(j,3)
    dp[0][i][j]=dpp[0][i][j]=0;
  dp[0][0][2]=dpp[0][0][2]=1;
  dp[0][1][1]=dpp[0][1][1]=1;
  dp[0][2][0]=dpp[0][2][0]=1;
  rep(i,n-1)rep(j,3){
    dp[i+1][0][j]=(dp[i][0][(j+1)%3]+dp[i][1][(j+1)%3]+dp[i][2][(j+1)%3])%mod;
    dp[i+1][1][j]=(dp[i][0][(j+2)%3]+dp[i][1][(j+2)%3]+dp[i][2][(j+2)%3])%mod;
    dp[i+1][2][j]=(dp[i][0][j]+dp[i][1][j]+dp[i][2][j])%mod;
    dpp[i+1][0][j]=(dpp[i][1][(j+1)%3]+dpp[i][2][(j+1)%3])%mod;
    dpp[i+1][1][j]=(dpp[i][0][(j+2)%3]+dpp[i][2][(j+2)%3])%mod;
    dpp[i+1][2][j]=(dpp[i][0][j]+dpp[i][1][j])%mod;
    }
  ll ans=flag;
  rep(i,3)ans+=dp[n-1][i][b]-dpp[n-1][i][b]+mod;
  ans%=mod;
  cout<<ans<<endl;
  return 0;    
  }

Submission Info

Submission Time
Task F - Normalization
User tempura0224
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1662 Byte
Status
Exec Time 23 ms
Memory 28676 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt
All 700 / 700 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, s1.txt, s2.txt, s3.txt, s4.txt
Case Name Status Exec Time Memory
01.txt 1 ms 256 KB
02.txt 1 ms 256 KB
03.txt 1 ms 256 KB
04.txt 1 ms 256 KB
05.txt 1 ms 256 KB
06.txt 1 ms 256 KB
07.txt 1 ms 256 KB
08.txt 1 ms 256 KB
09.txt 1 ms 256 KB
10.txt 1 ms 256 KB
11.txt 1 ms 256 KB
12.txt 1 ms 256 KB
13.txt 1 ms 256 KB
14.txt 1 ms 256 KB
15.txt 1 ms 256 KB
16.txt 1 ms 256 KB
17.txt 1 ms 256 KB
18.txt 1 ms 256 KB
19.txt 1 ms 256 KB
20.txt 1 ms 256 KB
21.txt 1 ms 256 KB
22.txt 1 ms 256 KB
23.txt 1 ms 256 KB
24.txt 1 ms 256 KB
25.txt 1 ms 256 KB
26.txt 1 ms 256 KB
27.txt 1 ms 256 KB
28.txt 1 ms 256 KB
29.txt 1 ms 256 KB
30.txt 1 ms 256 KB
31.txt 1 ms 256 KB
32.txt 1 ms 256 KB
33.txt 1 ms 256 KB
34.txt 1 ms 256 KB
35.txt 1 ms 256 KB
36.txt 1 ms 256 KB
37.txt 19 ms 23300 KB
38.txt 4 ms 2816 KB
39.txt 2 ms 1664 KB
40.txt 9 ms 11392 KB
41.txt 22 ms 28292 KB
42.txt 20 ms 25604 KB
43.txt 14 ms 18176 KB
44.txt 22 ms 27780 KB
45.txt 12 ms 14848 KB
46.txt 20 ms 25476 KB
47.txt 17 ms 22148 KB
48.txt 11 ms 13952 KB
49.txt 11 ms 13824 KB
50.txt 8 ms 9344 KB
51.txt 12 ms 15232 KB
52.txt 4 ms 3200 KB
53.txt 16 ms 20612 KB
54.txt 6 ms 6400 KB
55.txt 14 ms 17536 KB
56.txt 15 ms 18560 KB
57.txt 3 ms 2432 KB
58.txt 20 ms 25092 KB
59.txt 2 ms 896 KB
60.txt 15 ms 19588 KB
61.txt 3 ms 384 KB
62.txt 3 ms 384 KB
63.txt 8 ms 640 KB
64.txt 8 ms 640 KB
65.txt 6 ms 640 KB
66.txt 6 ms 640 KB
67.txt 22 ms 28676 KB
68.txt 22 ms 28676 KB
69.txt 22 ms 28676 KB
70.txt 22 ms 28676 KB
71.txt 22 ms 28676 KB
72.txt 22 ms 28676 KB
73.txt 23 ms 28676 KB
74.txt 22 ms 28676 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB
s4.txt 1 ms 256 KB