qbpal.cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define vi vector<int>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define popcnt __builtin_popcount
#define getbit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()

typedef vector<int> bigNum;

string s;
bigNum f[125][125];

const int BASE = 1e9;

bigNum operator+(bigNum a, bigNum b){
    while (a.size() < b.size()) a.push_back(0);
    while (a.size() > b.size()) b.push_back(0);
    int n = a.size(), d = 0;
    bigNum c; c.resize(n);
    for (int i = 0; i < n; i++){
        c[i] = (a[i] + b[i] + d) % BASE;
        d = (a[i] + b[i] + d) / BASE;
    }
    if (d) c.push_back(d);
    return c;
}

bigNum operator-(bigNum a, bigNum b) {
    while (b.size() < a.size()) b. push_back(0);
    int n = a.size(), d = 0;
    bigNum c; c.resize(n);
    for (int i = 0; i < n; i++){
        if (a[i] >= b[i] + d){
            c[i] = a[i] - (b[i] + d);
            d = 0;
        }
        else{
            c[i] = (a[i] + BASE) - (b[i] + d);
            d = 1;
        }
    }
    return c;
}

ostream& operator<<(ostream &os, bigNum a){
    int n = a.size();
    cout << a[n-1];
    for (int i = n - 2; i >= 0; i--){
        cout << setw(9) << setfill('0') << a[i];
    }
    return os;
}

bigNum cal(int a, int b)
{
    if (a > b) return bigNum(1,1);
    if (a == b) return bigNum(1,2);
    if (f[a][b] != bigNum(1,-1)) return f[a][b];

    bigNum ans = cal(a+1,b) + cal(a,b-1) - cal(a+1,b-1);
    if (s[a] == s[b]) ans = ans + cal(a+1,b-1);

    f[a][b] = ans;
    return ans;
}

void solve()
{
    cin >> s;
    int n = s.size();
    for (int i = 0 ; i <= n; i++)
        for (int j = 0 ; j <= n; j++)
            f[i][j] = bigNum(1,-1);
    cout << cal(0,n-1) - bigNum(1,1);
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
        cout << '\n';
    }
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}