Queries for Number of Palindromes

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

int main() {
    fast_io();

    string s;
    cin >> s;

    int n = s.length();

    vector<vector<bool>> is_palindrome(n, vector<bool>(n, false));

    for (int len = 1; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            if (len == 1) {
                is_palindrome[i][j] = true;
            } else if (len == 2) {
                is_palindrome[i][j] = (s[i] == s[j]);
            } else {
                is_palindrome[i][j] = (s[i] == s[j] && is_palindrome[i+1][j-1]);
            }
        }
    }

    vector<vector<int>> count(n, vector<int>(n, 0));

    for (int len = 1; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            if (len == 1) {
                count[i][j] = 1;
            } else if (len == 2) {
                count[i][j] = is_palindrome[i][j] + 2;
            } else {
                count[i][j] = count[i+1][j] + count[i][j-1] - count[i+1][j-1];
                count[i][j] += is_palindrome[i][j];
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << count[l - 1][r - 1] << " ";
    }
    cout << endl;

    return 0;
}