Language: C++

#include <memory>
#include <type_traits>
#include <utility>

template <class Key, class T> class splay_tst_associative_array {
public:
	using key_type = Key;
	using key_value = typename key_type::value_type;
	using value_type = T;
	using reference = value_type &;

	static_assert(::std::is_default_constructible<value_type>::value,
		"T must be default constructible");

private:
	template <class T> using observer_ptr = T *;
	class node_type;
	class next_ptr {
	public:
		::std::unique_ptr<node_type> ptr;
		typename splay_tst_associative_array::value_type value;
		next_ptr() : ptr(), value() {}
	};
	class node_type {
		using key_value = typename splay_tst_associative_array::key_value;

	public:
		key_value key;
		::std::unique_ptr<node_type> left, right;
		next_ptr middle;
		node_type(const key_value &key_) : key(key_), left(), right(), middle() {}
	};
	using pointer = ::std::unique_ptr<node_type>;
	using p_ptr = observer_ptr<pointer>;
	next_ptr root;

public:
	splay_tst_associative_array() : root() {}

	reference operator[](const key_type &key) {
		next_ptr *prev = &root;
		for (const auto &elm : key) {
			pointer ptr = ::std::move(prev->ptr);
			pointer sub_l, sub_r;
			p_ptr left = &sub_l, right = &sub_r;
			while (1) {
				if (!ptr)
					ptr = ::std::make_unique<node_type>(elm);
				if (!(ptr->key <= elm)) {
					if (!ptr->left)
						ptr->left = ::std::make_unique<node_type>(elm);
					if (!(ptr->left->key <= elm)) {
						*right = ::std::move(ptr->left);
						ptr->left = ::std::move((*right)->right);
						(*right)->right = ::std::move(ptr);
						right = &(*right)->left;
						ptr = ::std::move(*right);
					}
					else if (!(elm <= ptr->left->key)) {
						*right = ::std::move(ptr);
						right = &(*right)->left;
						*left = ::std::move(*right);
						left = &(*left)->right;
						ptr = ::std::move(*left);
					}
					else {
						*right = ::std::move(ptr);
						right = &(*right)->left;
						ptr = ::std::move(*right);
					}
				}
				else if (!(elm <= ptr->key)) {
					if (!ptr->right)
						ptr->right = ::std::make_unique<node_type>(elm);
					if (!(ptr->right->key <= elm)) {
						*left = ::std::move(ptr);
						left = &(*left)->right;
						*right = ::std::move(*left);
						right = &(*right)->left;
						ptr = ::std::move(*right);
					}
					else if (!(elm <= ptr->right->key)) {
						*left = ::std::move(ptr->right);
						ptr->right = ::std::move((*left)->left);
						(*left)->left = ::std::move(ptr);
						left = &(*left)->right;
						ptr = ::std::move(*left);
					}
					else {
						*left = ::std::move(ptr);
						left = &(*left)->right;
						ptr = ::std::move(*left);
					}
				}
				else {
					*left = ::std::move(ptr->left);
					ptr->left = ::std::move(sub_l);
					*right = ::std::move(ptr->right);
					ptr->right = ::std::move(sub_r);
					break;
				}
			}
			prev->ptr = ::std::move(ptr);
			prev = &prev->ptr->middle;
		}
		return prev->value;
	}
};

#include <algorithm>
#include <array>
#include <iostream>
#include <string>

int main() {
	int n;
	::std::string s;
	::std::cin >> n >> s;

	splay_tst_associative_array<
		::std::string,
		splay_tst_associative_array<::std::string, int>>
		sta;

	for (int i = 0;i < 1 << n;++i) {
		::std::array<::std::string, 2> t;
		for (int j = 0;j < n;++j)
			t[i >> j & 1].push_back(s[j]);
		++sta[t[0]][t[1]];
	}

	::std::reverse(s.begin(), s.end());
	long long ans = 0;

	for (int i = 0;i < 1 << n;++i) {
		::std::array<::std::string, 2> t;
		for (int j = 0;j < n;++j)
			t[i >> j & 1].push_back(s[j]);
		ans += sta[t[0]][t[1]];
	}

	::std::cout << ans << ::std::endl;
	return 0;
}


Compiler output:
a.cc:16:19: error: declaration of template parameter 'T' shadows template parameter
   16 |         template <class T> using observer_ptr = T *;
      |                   ^~~~~
a.cc:5:22: note: template parameter 'T' declared here
    5 | template <class Key, class T> class splay_tst_associative_array {
      |                      ^~~~~