fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int mod=998244353,N=8e6+5;
  5. vector<int> A[N];
  6. int dp[N];
  7. signed main()
  8. {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(0);
  11.     cout.tie(0);
  12.     string S;
  13.     cin>>S;
  14.     int n=S.size();
  15.     set<string> s[n+1];
  16.     s[n].insert(S);
  17.     int cnt=2;
  18.     map<string,int> mp;
  19.     map<string,bool> mp1;
  20.     mp[S]=1;
  21.     for(int a=n-1;a>0;a--){
  22.         for(auto f:s[a+1]){
  23.             string d=f.substr(0,a),e=f.substr(1,a);
  24.             if(!mp1[d]){
  25.                 mp[d]=cnt;
  26.                 mp1[d]=1;
  27.                 cnt++;
  28.             }
  29.             if(d!=e&&!mp1[e]){
  30.                 mp[e]=cnt;
  31.                 mp1[e]=1;
  32.                 cnt++;
  33.             }
  34.             if(d==e) A[mp[f]].push_back(mp[d]);
  35.             else{
  36.                 A[mp[f]].push_back(mp[d]);
  37.                 A[mp[f]].push_back(mp[e]);
  38.             }
  39.             s[a].insert(d);
  40.             s[a].insert(e);
  41.         }
  42.     }
  43.     int sum=0;
  44.     dp[1]=1;
  45.     for(int a=1;a<=cnt-1;a++){
  46.         for(int b:A[a]){
  47.             dp[b]+=dp[a];
  48.             dp[b]%=mod;
  49.         }
  50.     }
  51.     for(int a=1;a<=cnt-1;a++){
  52.         sum+=dp[a];
  53.         sum%=mod;
  54.     }
  55.     cout<<sum;
  56. }
  57.  
Success #stdin #stdout 0.24s 212396KB
comments (?)
stdin
copy 
asjnkajsndiashdgiasdgjosaidosidnonsdjfwkjvnksdshdbahfaiushfiauhriwuhrenuywqeurwrweiwuehgieuwhfiwuhiewufhqwiuhrwqniwqhriwqfkewfewkfeoifjewoefijwoeijoifjeoifoguedkwmlazoasokxosfwodfjwoifjeoifjoewifwefewfpewfelfwepwflewfwjdqjifqwfqfqisjqwertyuiopasdfghjkllllllllllllzxcvbnm
stdout
copy 
924571468
https://ideone.com/Iv6f5d
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!