SRM528 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=11634&rd=14553

memo[一方をどこまで作った][もう一方をどこまで作った]

s[x[k]] = s[y[k]] の条件を満たしうる長さN/2の文字列を全て生成して数え上げる。
候補の文字列をtとして、memo[i][j]に注目している時、t[i]かt[j]のどちらかに文字を割り当てる。
割り当てられる文字はs[i + j]。

(2^20)*(20^2)は無理だろうと思ってひたすら別解法を考えたけど、結局はこれだった。
あまり手を抜くとTLEする。

const int M = 40;
lli memo[M][M];
lli rec(int i, int j, const string& s, const string& t)
{
  if (i == t.size() && j == t.size()) return 1;
  if (t.size() < i || t.size() < j) return 0;

  lli& ret = memo[i][j];
  if (ret != -1) return ret;

  lli sum = 0;
  const int k = i + j;
  if (s[k] == t[i]) sum += rec(i + 1, j, s, t);
  if (s[k] == t[j]) sum += rec(i, j + 1, s, t);

  return ret = sum;
}

class SPartition {
public:
  long long getCount(string s)
  {
    if (count(s.begin(), s.end(), 'o') % 2) return 0;
    if (count(s.begin(), s.end(), 'x') % 2) return 0;

    const int x = count(s.begin(), s.end(), 'x');
    vector<string> v;

    const int N = s.size() / 2;
    const int BIT = 1 << N;
    for (int bit = 0; bit < BIT; ++bit) {
      if (__builtin_popcount(bit) != x / 2) continue;
      string t;
      for (int i = 0; i < N; ++i) {
        t += (bit & (1 << i)) ? 'x' : 'o';
      }
      v.push_back(t);
    }

    lli sum = 0;
    for (int i = 0; i < v.size(); ++i) {
      fill(&memo[0][0], &memo[M - 1][M - 1] + 1, -1);
      sum += rec(0, 0, s, v[i]);
    }
    return sum;
  }
};