SRM406 Div2 Hard

1000

DPする。
dp [ i ] [ j ] = i から j までの間で作れるパターン数

意外と難しかった。

vector<int> C;
int N;

const int M = 50 + 1;

lli memo[M][M];

const lli mod = 100000007;

// [... a, b, ...]
bool next(int a, int b)
{
  return (a + 1) % N == b;
}

lli rec(int i, int j)
{
  if (next(i, j)) return 1;
 
  lli &ret = memo[i][j];
  if (ret != -1) return ret;

  lli sum = rec(i + 1, j);
 
  for (int k = i + 2; k < j; ++k) {
    if (C[i] != C[k]) {
      sum += rec(i, k) * rec(k, j) / 2LL;
      sum %= 2LL * mod;
    }
  }

  if (C[i] != C[j] && !next(i, j) && !next(j, i)) {
    sum *= 2LL;
    sum %= 2LL * mod;
  }

  return ret = sum;
}

class PolygonColors {
public:
  int getWays(int N_, vector <int> C_)
  {
    N = N_;
    C = C_;

    for (int i = 0; i < (int)N; ++i) {
      int j = (i + 1) % C.size();
      if (C[i] == C[j]) return 0;
    }

    fill(&memo[0][0], &memo[M - 1][M], -1);
    return rec(0, N - 1) % mod;
  }
};