forked from Anuragcoderealy/Codenewhacktober
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBINARYSUB.cpp
More file actions
44 lines (37 loc) · 1.26 KB
/
BINARYSUB.cpp
File metadata and controls
44 lines (37 loc) · 1.26 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long int func(int index, string& s, vector<int>& dp, map<string, string>& hardcoded, string curr, set<string>& disset, long long int mod){
if(index < 0){
auto it = disset.find(curr);
if(it == disset.end()){
disset.insert(curr);
return 1;
}
return 0;
}
if(dp[index] != -1) return dp[index];
long long int takingone = func(index-1, s, dp, hardcoded, hardcoded[s.substr(index, 1)+curr], disset, mod);
long long int takingtwo = 0;
if(index-1 >= 0 && hardcoded.find(s.substr(index-1, 2)) != hardcoded.end())
takingtwo = func(index-2, s, dp, hardcoded, hardcoded[s.substr(index-1, 2)]+curr, disset, mod);
return dp[index] = (takingone+takingtwo) % 998244353;
}
long long int solve(){
string s;
cin >> s;
long long int n = s.length();
vector<int> dp(n, -1);
map<string, string> hardcoded {{"a", "01"}, {"b", "10"}, {"ab" , "010"}, {"ba" , "101"}};
set<string> disset;
cout << func(n-1, s, dp, hardcoded, "", disset, 998244353) << endl;
return 0;
}
int main() {
long long int t;
cin >> t;
while(t--){
solve();
}
return 0;
}