题意

把字符串每个字符染成白色或者黑色。使得从左往右看过去的黑色串等于从右往左看的白色串。

思路

看范围就很像就是搜索。考虑折半搜索，设左边的白色串为 $白_l$，左边的黑色串为 $黑_l$，右边的白色串为 $白_r$，右边的黑色串为 $黑_r$。

字符串$S$反过来看设为$S^T$

$白串$的长度要等于$黑串$ ，因为折半搜索，所以左边的串长度要等于右边的串。

得到 $|白_l| + |白_r| = |黑_l| + |黑_r|$ $|白_l| + |黑_l| = |白_r| + |黑_r|$ 相加得到 $|白_l|=|黑_r|$ 继而也得到了 $|白_r|=|黑_l|$

所以 $黑_l = 白_r^T$ $白_l^T = 黑_r$

所以只要把左边的方案记录起来$\{黑_l, 白_l^T\}$。右边只要查询$\{白_r^T, 黑_r\}$即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    string S;
    cin >> N >> S;

    map<string, ll> x[20];
    for (int i = 0; i < (1 << N); i++)
    {
        int cnt = 0;
        string s = "";
        for (int j = 0; j < N; j++)
        {
            if (i & (1 << j))
                s += S[j];
        }
        cnt = s.size();
        for (int j = N - 1; j >= 0; j--)
        {
            if (!(i & (1 << j)))
                s += S[j];
        }
        x[cnt][s]++;
    }
    map<string, ll> y[20];
    reverse(S.begin(), S.end());
    for (int i = 0; i < (1 << N); i++)
    {
        int cnt = 0;
        string s = "";
        for (int j = 0; j < N; j++)
        {
            if (i & (1 << j))
                s += S[j];
        }
        cnt = s.size();
        for (int j = N - 1; j >= 0; j--)
        {
            if (!(i & (1 << j)))
                s += S[j];
        }
        y[cnt][s]++;
    }

    ll ret = 0;
    for (int i = 0; i <= N; i++)
    {
        auto itr = x[i].begin();
        while (itr != x[i].end())
        {
            ret += (itr->second) * (y[i][itr->first]);
            ++itr;
        }
    }
    cout << ret << endl;
    return 0;
}