Problem:


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 \leq N \leq 18

The length of S is 2N.

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

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

Sample Input 1

4
cabaacba

Sample Output 1

4

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

cabaacba

cabaacba

cabaacba

cabaacba

Sample Input 2

11
mippiisssisssiipsspiim

Sample Output 2

504

Sample Input 3

4
abcdefgh

Sample Output 3

0

Sample Input 4

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 4

9075135300

The answer may not be representable as a 32-bit integer.



Sample input:
4
cabaacba


Sample output:
4

Submission status: Runtime Error

Solution code:
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  string s1 = S.substr(0, N);
  string s2 = S.substr(N);
  map<pair<string,string>, ll> cnt;
  for(int i = 0; i < 1 << N; i++) {
    string red = "";
    string blue = "";
    for(int j = 0; j < N; j++) {
      if (i >> j & 1) {
        red += s2[j];
      } else {
        blue += s2[j];
      }
    }
    string red_rev = red, blue_rev = blue;
    reverse(red_rev.begin(), red_rev.end());
    reverse(blue_rev.begin(), blue_rev.end());

    cnt[mp(red_rev, blue_rev)]++;
  }

  ll ans = 0;
  for (int i = 0; i < 1 << N; i++) {
    string red = "";
    string blue = "";
    for(int j = 0; j < N; j++) {
      if (i >> j & 1) {
        red += s1[j];
      } else {
        blue += s1[j];
      }
    }
    ans += cnt[mp(red, blue)];
  }
  cout << ans << endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int dp[50][50];

ll comb(ll n, ll r) {
  if (dp[n][r]) return dp[n][r];
  if (n == r) return dp[n][r] = 1;
  if (r == 0) return dp[n][r] = n;
  return dp[n][r] = comb(n - 1, r - 1) + comb(n - 1, r); 
}

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  string s1 = S.substr(0, N);
  string s2 = S.substr(N);
  map<pair<string,string>, ll> cnt;
  for(int i = 0; i < 1 << N; i++) {
    string red = "";
    string blue = "";
    for(int j = 0; j < N; j++) {
      if (i >> j & 1) {
        red += s2[j];
      } else {
        blue += s2[j];
      }
    }
    string red_rev = red, blue_rev = blue;
    reverse(red_rev.begin(), red_rev.end());
    reverse(blue_rev.begin(), blue_rev.end());

    cnt[mp(red_rev, blue_rev)]++;
  }

  ll ans = 0;
  for (int i = 0; i < 1 << N; i++) {
    string red = "";
    string blue = "";
    for(int j = 0; j < N; j++) {
      if (i >> j & 1) {
        red += s1[j];
      } else {
        blue += s1[j];
      }
    }
    ans += cnt[mp(red, blue)];
  }
  cout << ans << endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
T = int(input())
ABCD = [list(map(int,input().split())) for _ in range(T)]

for a,b,c,d in ABCD:
    if a < b:
        print('No')
        continue
    if d < b:
        print('No')
        continue
    tmp = a % b
    if tmp > c:
        print('No')
        continue
    if d % b == 0:
        print('Yes')
        continue
    if c >= b-1:
        print('Yes')
        continue
    if a%2 == 0 and b%2 == 0 and d %2 == 0 and b-c == 2:
        print('Yes')
        continue
    #print('No')

    a /= c
    b /= c
    d /= c
    c = 1
    now = a
    dp = [a]
    for _ in range(c+2):
        if now < b:
            print('No')
            break
        now %= b
        if now in dp:
            print('Yes')
            break
        if now > c:
            print('No')
            break
        dp.append(now)
        now += d
    print('No')

Submission status: Runtime Error

Solution code:
18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa