/*
U ovom problemu potrebno je prebrojati ukupni broj rekurzivnih palindromskih (RP) particija
za dani broj n u oznaci f(n)
Jedna od ideja jest koristiti podijeli-pa-vladaj pristup koji se temelji na sljedecem:
a) Podijeli: dani broj n particioniraj s obzirom na parnost:
n = 2k = w+2j+w, za neki k>0 cijeli broj i j>=0 cijeli broj
n = 2k+1 = w+(2j+1)+w za neki k>0 i j>=0 cijeli broj
gdje w = k-j.
Pretpostavimo da je n=2k, dakle paran.
Tada je za sve j>=0 cijele brojeve, f(k-j) RP particija zajedno s 2j čine podskup od RP particija za n.
Ukupno, sumirajući po j=0,1,2,...,k dobivamo
f(n) = \sum^k_{j=0} f(k-j) (*)
što kad se oduzme s f(n-2) dobivamo rekurziju
f(n) = f(n-2)+f(n/2), za n = 2k (R1)
Ukoliko je n=2k+1, dakle neparan, f(k-j) RP particija zajedno s (2j+1) čine isto tako podskup od RP particija
za n, pa vrijedi f(n) = \sum^k_{j=0} f(k-j) što iz (*) zaključujemo
f(n) = f(n-1), za n = 2k+1 (R2)
b) Vladaj: racunaj f(n-1), f(n-2), f(n/2)
c) Spoji: spoji rjesenja prema (R1) i (R2)
**komentar: programski kod upravo implemntira ovo razmatranje. Dodatno, omogućuje memoizaciju: spremanje
vrijednosti jednom pozvanih rekurzivnih funkcija.
*/
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
using namespace std;
#define None 0
long *RP;
// ukoliko zelimo smanjiti broj poziva rekurzija spremamo rezultate jednom izracunatih rekurzija
#define NO_MEMO
// ukoliko zelimo smanjiti broj poziva rekurzija spremamo rezultate jednom izracunatih rekurzija
// odkomentirajte sljedeci redak
#define MEMO
#ifdef MEMO
#undef NO_MEMO
#endif
int PalindromePartition(int n)
{
if (n ==0 || n == 1)
{
# ifdef MEMO
RP[0] = RP[1] = 1;
#endif
return 1;
}
// else
#ifdef NO_MEMO
if ((n % 2) == 0) return PalindromePartition(n-2)+PalindromePartition(n/2);
else return PalindromePartition(n-1);
#endif
#ifdef MEMO
if((n%2)==0)
{
RP[n-2] = (RP[n-2] == None) ? PalindromePartition(n-2) : RP[n-2];
RP[n/2] = (RP[n/2] == None) ? PalindromePartition(n/2) : RP[n/2];
return (RP[n-2]+RP[n/2]);
}
else
{
RP[n-1] = (RP[n-1] == None) ? PalindromePartition(n-1) : RP[n-1];
return RP[n-1];
}
#endif
}
int main()
{
// ucitaj broj testova
int N;
cin >> N;
int num_of_Tests = 0;
// vrijednost
int n;
while(++num_of_Tests <= N)
{
cin >> n;
#ifdef MEMO
RP = new long[n];
memset(RP, None, sizeof(RP[0]) * n);
#endif
int sol = PalindromePartition(n);
cout << sol << endl;
#ifdef MEMO
delete [] RP;
#endif
}
return 0;
}