https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1558

10617 - Again Palindrome.cpp

#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

string s;
const int MAX = 61;
ll cache[MAX][MAX];

ll nWays(int st, int en) {
    if(st == en)
        return 1;
    if(st+1 == en) {
        return 2 + (s[st] == s[en]);
    }

    ll &ret = cache[st][en];
    if(ret != -1)
        return ret;
    ret = 0;

    if(s[st] == s[en])
        ret += nWays(st+1, en-1) + 1;

    ret += nWays(st, en-1);
    ret += nWays(st+1, en);
    ret -= nWays(st+1, en-1);

    return ret;
}

int main() {
    int t;
    cin>>t;
    while(t--) {
        clr(cache, -1);
        cin>>s;
        cout << nWays(0, s.length()-1) << endl;
    }
    return 0;
}