C

C - String Coloring

agc026.contest.atcoder.jp

Time limit : 3sec / Memory limit : 1024MB

Score : 600 points

Problem Statement

You are given a string S of length 2N consisting of lowercase English letters.

There are 2^2N 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.
题意:，给你一个长度为2N的字符串，其中每个字母要么涂红要么涂蓝，问有多少种涂法使得从左往右读红字字母组成的字符串和从右往左读蓝色字母组成的字符串是一样的，

首先，我们从时间复杂度开始分析:如果直接暴力，那么时间复杂度是2^2N乘以一个东西，显然超时。但是我们注意到，如果把这道题转换为2^N乘以一个数，那么时间复杂度就能过地去了。那么接下来，我们的任务是把2^2N转换为2^N。那么由2N转换为N,我们就应该想到关键词------一半。于是，我们把这个字符串拆为两半来做，这样一来，就能达到时间复杂度的要求了。但问题是，左边字符串和右边字符串看起来好像没有任何关系，但实际上转换一下，两个字符串就有关系了:把右边的字符串先倒转，然后再把每一个颜色倒转，你就会发现一个神奇的东西:两个字符串从左往右读红色字符结果竟然是一样的!读蓝色也是!这样一来，这道题就可以开做了。

#include<map>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n;
long long ans;
char s[10005];
map<pair<string,string>,int>f;
int main(){
   scanf("%d%s",&n,s);
   for(int i=0;i<1<<n;i++){
       string a,b;
       for(int j=0;j<n;j++){
           if((i>>j)&1)a+=s[j];
           else b+=s[j];
       }
       f[{a,b}]++;
   }
   for(int i=0;i<1<<n;i++){
       string a,b;
       for(int j=0;j<n;j++){
       if((i>>j)&1)a+=s[2*n-1-j];
           else b+=s[2*n-1-j];
       }
       ans+=f[{a,b}];
   }
   printf("%lld",ans);
}