[meet in the middle]String Coloring

题目描述

You are given a string S of length 2N consisting of lowercase English letters.
There are 22N ways to color each character in S red or blue. Among these ways, how many satisfy the following condition?
The string obtained by reading the characters painted red from left to right is equal to the string obtained by reading the characters painted blue from right to left.
Constraints
1≤N≤18
The length of S is 2N.
S consists of lowercase English letters.

 

输入

Input is given from Standard Input in the following format:
N
S

 

输出

Print the number of ways to paint the string that satisfy the condition.

 

样例输入

复制样例数据

4
cabaacba

样例输出

4

 

提示

There are four ways to paint the string, as follows:
cabaacba
cabaacba
cabaacba
cabaacba

思路：meet in the middle搜索

#include <iostream>
#include<cstdio>
#include<string>
#include<map>
typedef long long ll;
using namespace std;

char s[20];
map< pair<string,string>,ll > mp;

int main()
{
    ll n;scanf("%lld",&n);
    scanf("%s",s);
    for(ll i=0;i<=(1<<n)-1;i++){
        string a,b;
        for(ll j=0;j<n;j++){
            if((i>>j)&1) a+=s[j];
            else b+=s[j];
        }
        mp[make_pair(a,b)]++;
    }
    ll ans=0;
    for(ll i=0;i<=(1<<n)-1;i++){
        string a,b;
        for(ll j=0;j<n;j++){
            if((i>>j)&1) a+=s[2*n-1-j];
            else b+=s[2*n-1-j];
        }
        ans+=mp[make_pair(a,b)];
    }
    printf("%lld\n",ans);
    return 0;
}