fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll fre[30];const ll mod=1e9+7;
  5. ll pre[30][1000006];vector<int>v[30];
  6. ll fac[1000006],inv[1000006];
  7. ll pow1(ll a,ll b)
  8. {
  9.     ll res=1;
  10.     while(b!=0)
  11.     {
  12.         if(b&1)
  13.             res=(res*a)%mod;
  14.         a=(a*a)%mod;
  15.         b>>=1;
  16.     }
  17.     return (res+mod)%mod;
  18. }
  19. int main()
  20. {
  21.     ios_base::sync_with_stdio(false);
  22.     cin.tie(NULL);
  23.     fac[0]=1,inv[0]=1;
  24.     for(int i=1;i<=1000002;i++)
  25.     {
  26.         fac[i]=(fac[i-1]*i)%mod;
  27.         inv[i]=pow1(fac[i],mod-2);
  28.     }
  29.     for(int i=0;i<=26;i++)fre[i]=0;
  30.     string s;cin>>s;int l=(int)s.length();
  31.     for(int i=0;i<=25;i++)
  32.     {
  33.         for(int j=0;j<=1000002;j++)
  34.             pre[i][j]=0;
  35.     }
  36.     for(int i=0;i<(int)s.length();i++)
  37.     {
  38.         fre[s[i]-'a']++;
  39.         pre[s[i]-'a'][i]=1;
  40.         v[s[i]-'a'].push_back(i);
  41.     }
  42.     for(int i=0;i<=25;i++)
  43.     {
  44.         for(int j=1;j<=1000002;j++)
  45.             pre[i][j]+=pre[i][j-1];
  46.     }
  47.     ll ans=0;
  48.     for(int i=0;i<=25;i++)
  49.     {
  50.         if(fre[i]>=4)
  51.         {
  52.             ll temp=fac[fre[i]];
  53.             temp=(temp*inv[4])%mod;
  54.             temp=(temp*inv[fre[i]-4])%mod;
  55.             ans=(ans+temp)%mod;
  56.         }
  57.     }
  58.  
  59.     for(int i=0;i<=25;i++)
  60.     {
  61.         int num=v[i].size();
  62.         for(int j=0;j<num-1;j++)
  63.         {
  64.             int a=v[i][j],b=v[i][j+1];
  65.             for(int k=0;k<=25;k++)
  66.             {
  67.                 if(i==k)continue;
  68.                 ll q=pre[k][b]-(pre[k][a]);
  69.                 ll after=(ll)num-pre[i][b];
  70.                 after=(after+1)%mod;
  71.                 ll before=((a-1)>=0? pre[i][a-1]:0);
  72.                 before=(before+1)%mod;
  73.                 before=((before)*(after))%mod;
  74.                 if(q>=2){
  75.                 ll temp=(q*(q-1))/2;
  76.                 temp=temp%mod;
  77.                 ans=(ans+((before*temp)%mod))%mod;}
  78.             }
  79.         }
  80.        // if(i==('h'-'a'))
  81.          //   cout<<ans;
  82.     }
  83.     cout<<(ans+mod)%mod<<"\n";
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 1.97s 253440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/E19cGY
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!