SRM574 Div1 Medium

450

memo[ どの頂点を使った ][ 最後にどこを使った ]

次に使う頂点との両側にすでに訪れた頂点があれば交差する。はず。
0 と N-1 の隣接を忘れるという悲しい出来事があって本番中に通せなかった。

const int V = 18;
const int BIT = (1 << V) + 1;
static lli dp[BIT][V];

int N;
vector<int> ps;

bool adj(int a, int b)
{
  int x = (a + 1) % N;
  int y = (a - 1 + N) % N;
  return x == b || y == b;
}

lli rec(int bit, int curr)
{
  if (bit == (1 << N) - 1) return adj(ps.front(), curr) ^ 1;

  lli& ret = dp[bit][curr];
  if (ret != -1) return ret;

  lli sum = 0;
  for (int next = 0; next < N; ++next) {
    if (bit & (1 << next)) continue;
    if (adj(curr, next)) continue;

    int a = -1;
    int b = -1;
    for (int i = (next + 1) % N; i != curr; i = (i + 1) % N) {
      a = i;
      if (bit & (1 << i)) break;
    }
    for (int i = (next - 1 + N) % N; i != curr; i = (i - 1 + N) % N) {
      b = i;
      if (bit & (1 << i)) break;
    }

    if (a == curr || a == next) continue;
    if (b == curr || b == next) continue;

    if ((a != -1 && b != -1) && (a != b) && (bit & (1 << a)) && (bit & (1 << b))) {
      sum += rec(bit | (1 << next), next);
    }
  }
  return ret = sum;
}

class PolygonTraversal {
public:
  long long count(int N_, vector <int> ps_)
  {
    N = N_;
    ps = ps_;
    fill(&dp[0][0], &dp[BIT - 1][V - 1] + 1, -1);
    int bit = 0;
    for (int i = 0; i < ps.size(); ++i) {
      --ps[i];
    }
    for (int i = 0; i < ps.size(); ++i) {
      bit = bit | (1 << ps[i]);
    }

    return rec(bit, ps.back());
  }
};