Advertisement
iccjoc

amogus

Nov 11th, 2024
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.75 KB | None | 0 0
  1. #include <fstream>
  2. using namespace std;
  3. ifstream cin("scode.in");
  4. ofstream cout("scode.out");
  5. int combos(string s)
  6. {
  7.     int a = 1, n = s.size();
  8.     if((n & 1) == 0 || n == 1) // A -> A
  9.         return 1;
  10.     if(s.substr(0, n/2) == s.substr(n/2, n/2))      // ABC -> AB + ABC
  11.         a += combos(s.substr(n/2, n/2+1));
  12.     if(s.substr(0, n/2) == s.substr(n/2+1, n/2))    // ABC -> ABC + AB
  13.         a += combos(s.substr(0, n/2+1));
  14.     if(s.substr(0, n/2) == s.substr(n/2+1, n/2))    // ABC -> BC + ABC
  15.         a += combos(s.substr(n/2, n/2+1));
  16.     if(s.substr(1, n/2) == s.substr(n/2+1, n/2))    // ABC -> ABC + BC
  17.         a += combos(s.substr(0, n/2+1));
  18.     return a;
  19. }
  20. int main()
  21. {
  22.     string s;
  23.     cin >> s;
  24.     cout << combos(s) - 1;
  25. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement