fork download
copy 
  1. /*
  2. “You miss 100% of the shots you don't take”
  3. */
  4. #define numberOfDecimals(n) \
  5.     cout << fixed;          \
  6.     cout << setprecision(n);
  7. #include <bits/stdc++.h>
  8. #define file \
  9.     freopen("lex.in", "r", stdin);
  10. #define ll long long
  11. #define fast                          \
  12.     ios_base::sync_with_stdio(false); \
  13.     cin.tie(0);                       \
  14.     cout.tie(0);
  15. #define testCases      \
  16.     unsigned ll tests; \
  17.     cin >> tests;      \
  18.     while (tests--)
  19. #define MOD 1000000007LL
  20. using namespace std;
  21.  
  22. ll add(ll a, ll b)
  23. {
  24.     return (((a % MOD + b % MOD) % MOD) + MOD) % MOD;
  25. }
  26. ll mul(ll a, ll b)
  27. {
  28.     return (1ll * (a % MOD) * (b % MOD)) % MOD;
  29. }
  30.  
  31. ll n, m;
  32. string t;
  33.  
  34. map<char, bool> mp;
  35. ll dp[505][505][26][2];
  36.  
  37. ll rec(ll it1, ll it2, ll vowel, ll cnt)
  38. {
  39.     // cout << it1 << " " << it2 << "\n";
  40.     if (cnt * cnt > (n - cnt) || vowel == 2)
  41.         return 0;
  42.     if (it1 == n)
  43.         return (it2 == m);
  44.  
  45.     if (dp[it1][it2][cnt][vowel] != -1)
  46.         return dp[it1][it2][cnt][vowel];
  47.  
  48.     ll ans = 0;
  49.     bool is_cur_vow = ((it2 < m) && mp[t[it2]]);
  50.     ll no_of_vowel = 5, non_vowel = 21;
  51.  
  52.     if (m > it2)
  53.     {
  54.         ans = rec(it1 + 1, it2 + 1, is_cur_vow ? (vowel + 1) : 0, cnt + is_cur_vow);
  55.  
  56.         if (is_cur_vow)
  57.             no_of_vowel--;
  58.         else
  59.             non_vowel--;
  60.     }
  61.  
  62.     ans = add(ans, mul(no_of_vowel, rec(it1 + 1, it2, vowel + 1, cnt + 1)));
  63.     ans = add(ans, mul(non_vowel, rec(it1 + 1, it2, 0, cnt)));
  64.  
  65.     return dp[it1][it2][cnt][vowel] = ans;
  66. }
  67.  
  68. void solve()
  69. {
  70.     cin >> n >> m >> t;
  71.  
  72.     memset(dp, -1, sizeof dp);
  73.  
  74.     cout << rec(0, 0, 0, 0);
  75. }
  76.  
  77. int main()
  78. {
  79.     // file;
  80.     fast;
  81.     mp['a'] = mp['e'] = mp['i'] = mp['o'] = mp['u'] = true;
  82.     // testCases
  83.     solve();
  84. }
Success #stdin #stdout 0.02s 107200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/InIiiU
language:
C++ (gcc 8.3)
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!