fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define all(x) x.begin(), x.end()
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace __gnu_pbds;
  9. template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10. template <typename T, typename R> using o_map = tree<T, R, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  11. typedef long long ll;
  12.  
  13. #define inf 1e9
  14. #define MOD 1000000007
  15. #define vint vector<int>
  16. #define vll vector<ll>
  17. #define no cout << "NO" << endl;
  18. #define yes cout << "YES" << endl;
  19.  
  20. string s;
  21. int n;
  22. vector<vector<set<string>>> dp;
  23.  
  24. set<string> f(int i, int type) {
  25.     if (i == n) return {""} ;
  26.     if (i == n - 1) {
  27.         return {string(1, s[n-1])};
  28.     }
  29.  
  30.     if (!dp[i][type].empty()) {
  31.         return dp[i][type];
  32.     }
  33.  
  34.     set<string>& st = dp[i][type];
  35.     st.insert(s.substr(i, n - i));
  36.  
  37.  
  38.  
  39.     if (type == 0) {
  40.         set<string> st1 = f(i+1, 0);
  41.         st.insert(all(st1));
  42.         char c = s[i];
  43.         set<string> st2 = f(i+2, 1);
  44.         for (auto &e : st2) {
  45.             string s1 = string(1, c) + e;
  46.             st.insert(s1);
  47.         }
  48.         return st ;
  49.     }
  50.     set < string > st2 = f(i+1 , 1) ;
  51.     st.insert(all(st2)) ;
  52.  
  53.     return st;
  54. }
  55.  
  56. void solve() {
  57.     cin >> n;
  58.     cin >> s;
  59.     dp.assign(n, vector<set<string>>(2));
  60.  
  61.     set<string> ans = f(0, 0);
  62.     cout << ans.size() << endl;
  63. }
  64.  
  65. int main() {
  66.     ios::sync_with_stdio(false);
  67.     cin.tie(nullptr);
  68.  
  69. #ifndef ONLINE_JUDGE
  70.     freopen("input.txt", "r", stdin);
  71.     freopen("output.txt", "w", stdout);
  72. #endif
  73.  
  74.     int t = 1;
  75.     cin >> t;
  76.     while (t--) {
  77.         solve();
  78.     }
  79.     return 0;
  80. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/tqw7d6
language:
C++ (gcc 8.3)
created:
7 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!