Submission #2374335


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,c=0;
  rep(i,n){
    if(s[i]=='a'){b+=2;c+=2;}
    if(s[i]=='b')b++;
    if(s[i]=='c')c++;
    }
  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;c%=3;
  ll dp[n][3][3][3],dpp[n][3][3][3];
  rep(i,3)rep(j,3)rep(k,3)
    dp[0][i][j][k]=dpp[0][i][j][k]=0;
  dp[0][0][2][2]=dpp[0][0][2][2]=1;
  dp[0][1][1][0]=dpp[0][1][1][0]=1;
  dp[0][2][0][1]=dpp[0][2][0][1]=1;
  rep(i,n-1)rep(j,3)rep(k,3){
    dp[i+1][0][j][k]=(dp[i][0][(j+1)%3][(k+1)%3]+dp[i][1][(j+1)%3][(k+1)%3]+dp[i][2][(j+1)%3][(k+1)%3])%mod;
    dp[i+1][1][j][k]=(dp[i][0][(j+2)%3][k]+dp[i][1][(j+2)%3][k]+dp[i][2][(j+2)%3][k])%mod;
    dp[i+1][2][j][k]=(dp[i][0][j][(k+2)%3]+dp[i][1][j][(k+2)%3]+dp[i][2][j][(k+2)%3])%mod;
    dpp[i+1][0][j][k]=(dpp[i][1][(j+1)%3][(k+1)%3]+dpp[i][2][(j+1)%3][(k+1)%3])%mod;
    dpp[i+1][1][j][k]=(dpp[i][0][(j+2)%3][k]+dpp[i][2][(j+2)%3][k])%mod;
    dpp[i+1][2][j][k]=(dpp[i][0][j][(k+2)%3]+dpp[i][1][j][(k+2)%3])%mod;
    }
  ll ans=flag;
  rep(i,3)ans+=dp[n-1][i][b][c]-dpp[n-1][i][b][c]+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 1876 Byte
Status
Exec Time 53 ms
Memory 84996 KB

Test Cases

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 2 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 43 ms 68868 KB
38.txt 6 ms 8064 KB
39.txt 4 ms 4608 KB
40.txt 22 ms 33408 KB
41.txt 52 ms 83716 KB
42.txt 47 ms 75908 KB
43.txt 34 ms 53504 KB
44.txt 52 ms 82308 KB
45.txt 28 ms 43648 KB
46.txt 47 ms 75140 KB
47.txt 41 ms 65412 KB
48.txt 26 ms 41088 KB
49.txt 26 ms 40448 KB
50.txt 17 ms 27264 KB
51.txt 29 ms 44672 KB
52.txt 6 ms 8832 KB
53.txt 38 ms 60676 KB
54.txt 13 ms 18304 KB
55.txt 33 ms 51456 KB
56.txt 34 ms 54784 KB
57.txt 6 ms 6912 KB
58.txt 47 ms 73988 KB
59.txt 3 ms 2304 KB
60.txt 36 ms 57604 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 53 ms 84996 KB
68.txt 53 ms 84996 KB
69.txt 52 ms 84996 KB
70.txt 53 ms 84996 KB
71.txt 53 ms 84996 KB
72.txt 53 ms 84996 KB
73.txt 53 ms 84996 KB
74.txt 53 ms 84996 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