fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const int N = 1e4 + 5;
  6. const int K = 7;
  7. const int A = 26;
  8. const int M = 1e9 + 7;
  9. int sLen;
  10. string s;
  11. int dp[N][K][2];
  12.  
  13. int solve(int idx, int mod, bool isSmall){
  14.     if(idx == sLen){
  15.         return (mod == 0);
  16.     }
  17.     if(dp[idx][mod][isSmall] != -1)
  18.         return dp[idx][mod][isSmall];
  19.  
  20.     int ans = 0;
  21.     int id = s[idx] - 'a';
  22.  
  23.     int maxId = id + 1;
  24.     if(isSmall) maxId = A;
  25.  
  26.     for(int i = 0; i < maxId; i++){
  27.         ans += solve(idx + 1, (mod + i) % K, isSmall | (i < id));
  28.         if(ans >= M)
  29.             ans -= M;
  30.     }
  31.     return dp[idx][mod][isSmall] = ans;
  32. }
  33. int main()
  34. {
  35.     ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  36.     cin >> s;
  37.  
  38.     sLen = (int)s.size();
  39.  
  40.     memset(dp, -1, sizeof(dp));
  41.     cout << solve(0, 0, 0);
  42. return 0;
  43. }
  44.  
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/MY6Lui
language:
C++14 (gcc 8.3)
created:
5 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!