AGC026 C - String Coloring

問題

長さ2Nの文字列Sを「赤色で塗った文字列を左から右に読んだもの と 青色で塗った文字列を右から左に読んだもの が同じになる」ように塗る方法は何通りあるか求める

解法

半分全列挙
前半N文字の塗り方を決め、赤/青で塗った文字列をx/yとすると、条件を満たすには後半N文字で赤/青で塗る文字列はそれぞれreverseしたy/xである必要がある
ex) 前半が abcd なら後半は dbとcaでないといけない

実装

前半部分でx,yのpairを列挙してmapで数えて、後半部分でそれを使って↑のように答えを数える

ll n, res;
string s;
map<pair<string,string>, ll> a;
 
signed main() {
	cin >> n >> s;
	rep(i,1<<n) {
		string x, y;
		rep(j,n) (i>>j&1 ? x : y).push_back(s[j]);
		a[{x,y}]++;
	}
	rep(i,1<<n) {
		string x, y;
		rep(j,n) (i>>j&1 ? y : x).push_back(s[n+j]);
		reverse(all(x)), reverse(all(y));
		res += a[{x,y}];
	}
	cout << res << endl;
}