SRM528 div.1 500 SPartition

SPartition.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;

ll dp[21][21];
int s[40], L, N;

ll rec(int x, int y, int bit) {
  if (x + y == L) return 1;
  if (dp[x][y] != -1) return dp[x][y];

  ll ret = 0;
  if (x < N and s[x+y] == (bit >> x & 1)) ret += rec(x+1, y, bit);
  if (y < N and s[x+y] == (bit >> y & 1)) ret += rec(x, y+1, bit);
  return dp[x][y] = ret;
}    

struct SPartition {
  ll getCount(string _s) {
    L = _s.size(), N = L / 2;
    int o_cnt = 0;
    for (int i = 0; i < L; i++) s[i] = _s[i] == 'o', o_cnt += s[i];
    if (o_cnt % 2) return 0;
    o_cnt >>= 1;
    
    ll ret = 0;
    for (int bit = 0; bit < (1 << N); bit++) {
      if (__builtin_popcount(bit) != o_cnt) continue;
      memset(dp, -1, sizeof(dp));
      ret += rec(0, 0, bit);
    }      
    
    return ret;
  }
};