Submission #2843541

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Общий файл.
#include <ext/pb_ds/tree_policy.hpp> // Содержит класс tree_order_statistics_node_update


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;

#define pb push_back
#define fo(i, n) for(int i = 1; i <= n; ++i)

const int mod = 1e9 + 7;
const int N = 500500;
const int M = 10000;
const int inf = 2e9;
int n;
string s;
const int p = 37;
ll get_hash(string s) {
    int n = s.length();
    ll h = 0;
    for(int i = 0; i < n; ++i) {
        h = h * p + (s[i] - 'a' + 1);
    }
    return h;
}
map<ll, int> cnt[20];
ll ans;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s;
    for(int mask = 0; mask < (1 << n); ++mask) {
        string a, b;
        for(int i = 0; i < n; ++i) {
            if((1 << i) & mask) {
                a += s[i];
            } else b += s[i];
        }
        reverse(b.begin(), b.end());
        a += b;
        ll h = get_hash(a);
        cnt[__builtin_popcount(mask)][h]++;
    }
    for(int mask = 0; mask < (1 << n); ++mask) {
        string a, b;
        for(int i = n - 1; i >= 0; --i) {
            if((1 << i) & mask) {
                a += s[i + n];
            } else b += s[i + n];
        }
        reverse(b.begin(), b.end());
        a += b;
        ll h = get_hash(a);
        ans += cnt[__builtin_popcount(mask)][h];
    }
    cout << ans;
    return 0;
}

Submission Info

Judge Result