fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define PI 3.14159265359
  4. #define DP(x, y) memset(x, y, sizeof x)
  5. #define all(x) x.begin(), x.end()
  6. #define read(x) freopen("x", "r", stdin);
  7. #define write(x) freopen("x", "w", stdout);
  8.  
  9. using namespace std;
  10.  
  11. ll gcd(ll a,ll b) { while(b) { ll x = a; a = b; b = x % b; } return a; }
  12. ll lcm(ll a,ll b) { return a / gcd(a, b) * b; }
  13. ll nC2(ll n) { return (n)*(n-1)/2; }
  14. ll summing(ll n) { return (n)*(n+1); }
  15.  
  16. ll ans=0, mod=1e9 + 9;
  17.  
  18. map<char,vector<char>> mp;
  19. map<char,ll>ind;
  20. vector<char> v{'a', 'e', 'i', 'o', 'u'};
  21. ll dp[5][200005];
  22.  
  23. ll counting(ll j, ll n, vector<char> &a, vector<char> &temp) {
  24.  
  25.     if (j == n) {
  26.         return 1;
  27.     }
  28.  
  29.     ll sum = 0;
  30.  
  31.     for (ll i=0; i<a.size(); i++) {
  32.  
  33.         if (~dp[ ind[a[i]] ][j]) {
  34.             sum += dp[ ind[a[i]] ][j];
  35.             continue;
  36.         }
  37.  
  38.         temp.push_back(a[i]);
  39.  
  40.         dp[ind[a[i]]][j] = counting(j+1, n, mp[a[i]], temp)%mod;
  41.  
  42.         temp.pop_back();
  43.  
  44.         sum += dp[ind[a[i]]][j]%mod;
  45.         sum %= mod;
  46.     }
  47.  
  48.     return (sum%mod);
  49. }
  50.  
  51. void solve() {
  52.  
  53.     ll n; cin >> n;
  54.  
  55.     DP(dp, -1);
  56.  
  57.     ind['a'] = 0;
  58.     ind['e'] = 1;
  59.     ind['i'] = 2;
  60.     ind['o'] = 3;
  61.     ind['u'] = 4;
  62.  
  63.     vector<char> c;
  64.     mp['a'].push_back('e');
  65.  
  66.     mp['e'].push_back('a');
  67.     mp['e'].push_back('i');
  68.  
  69.     mp['i'].push_back('a');
  70.     mp['i'].push_back('e');
  71.     mp['i'].push_back('o');
  72.     mp['i'].push_back('u');
  73.  
  74.     mp['o'].push_back('i');
  75.     mp['o'].push_back('u');
  76.  
  77.     mp['u'].push_back('a');
  78.  
  79.     ans = counting(0, n, v, c);
  80.  
  81.     cout << ans;
  82.  
  83. }
  84.  
  85. int main()
  86. {
  87.     ios::sync_with_stdio(false);
  88.     cin.tie(nullptr), cout.tie(nullptr);
  89.  
  90.     ll t=1;
  91.     //cin >> t;
  92.  
  93.     while (t--) {
  94.         solve();
  95.     }
  96.  
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 11384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/b0mzKe
language:
C++14 (gcc 8.3)
created:
16 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!