fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sti string
  4. #define bit(n,i) ((n>>i) &1)
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define maxn 20005
  7. #define fi first
  8. #define se second
  9. #define i18 __int128_t
  10.  
  11.  
  12. using namespace std;
  13.  
  14. ll f[maxn];
  15. ll nxt[maxn][35];
  16. const ll mod=111539786;
  17. ll block[maxn];
  18.  
  19. int main()
  20. {
  21.     itachi
  22.     int test;
  23.     cin>>test;
  24.     while(test--){
  25.         sti tmp;cin>>tmp;
  26.         int n=1;
  27.         sti s="";
  28.         memset(f,0,sizeof(f));
  29.         for(int i=0;i<tmp.size();){
  30.             char c=tmp[i++];
  31.             s.push_back(c);
  32.             ll val=0;
  33.             while(i<tmp.size() && (tmp[i]>='0' && tmp[i]<='9')){
  34.                 val=val*10+(tmp[i]-'0');
  35.                 i++;
  36.             }
  37.             block[n]=val;
  38.             n++;
  39.         }
  40.         s=' '+s;
  41.         for(int j=0;j<26;j++) nxt[n+1][j]=n+1;
  42.         for(int i=n;i>=0;i--){
  43.             for(int j=0;j<26;j++) nxt[i][j]=nxt[i+1][j];
  44.              nxt[i][s[i]-'a']=i;
  45.         }
  46.         f[0]=1; block[0]=1;
  47.         for(int i=0;i<=n;i++){
  48.             for(int j=0;j<26;j++){
  49.                 if(nxt[i+1][j]<=n){
  50.                     if(j!=(s[i]-'a')){
  51.                         f[nxt[i+1][j]]=(f[nxt[i+1][j]]+((block[i]*f[i])%mod)%mod);
  52.                     }
  53.                     else {
  54.                         f[nxt[i+1][j]]+=f[i];
  55.                         f[nxt[i+1][j]]%=mod;
  56.                     }
  57.                 }
  58.             }
  59.         }
  60.         ll ans=0;
  61.         for(int i=1;i<=n;i++) {
  62.             ans=(ans+(f[i]*block[i])%mod)%mod;
  63.         }
  64.         cout<<ans<<'\n';
  65.     }
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nDLuym
language:
C++14 (clang 8.0)
created:
2 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!