AOJ 2025 - Eight Princes

AOJ

現実逃避

問題

n個の椅子がある円卓がある。
ここに8人の王子が座る。
ただし、王子が隣り合ったり、ちょうど向かい合ったりしてはいけない。
このとき、何通りの座り方があるか。
回転したり反転したりして同じになるものも区別して数える。

制約

答えは10^14以下

解法

奇数のときは向かい合うことは無いので、ありきたりのDPで出来る。
偶数のときは、向かい合う椅子をセットで考えることがポイント。
各セットに対し、座らない、前半分のほうに座る、後半分の方に座る、という3パターンに分けることが出来る。
こう考えると、各セットに対して順番に座らせていくDPが可能になる。
状態の持ち方や更新の仕方は色々やり方があると思う。

ソース

// dp[何人座ったか][何番目の椅子まで見たか][最初の椅子に座ってない／座ってた][直前の椅子に座ってない／座った]
ll dp[10][101][2][2];

void odd_init() {
  dp[0][1][0][0] = dp[1][1][1][1] = 1;
  REP(i,9) {
    for (int j=1; j<100; ++j) {
      REP(k,2) {
        dp[i][j+1][k][0] += dp[i][j][k][0] + dp[i][j][k][1];
        dp[i+1][j+1][k][1] += dp[i][j][k][0];
      }
    }
  }
}

// dp2[何人座ったか][何番目の椅子まで見たか][最初の椅子に座ってない／前半に座った／後半に座った][直前の椅子に座ってない／前半に座った／後半に座った]
ll dp2[10][101][3][3];

void even_init() {
  dp2[0][1][0][0] = dp2[1][1][1][1] = dp2[1][1][2][2] = 1;
  REP(i,9) {
    for (int j=1; j<100; ++j) {
      REP(k,3) {  
        dp2[i][j+1][k][0] += dp2[i][j][k][0] + dp2[i][j][k][1] + dp2[i][j][k][2];
        dp2[i+1][j+1][k][1] += dp2[i][j][k][0] + dp2[i][j][k][2];
        dp2[i+1][j+1][k][2] += dp2[i][j][k][0] + dp2[i][j][k][1];
      }
    }
  }
}

// 最初の椅子と最後の椅子に同時に座ることが内容に足し合わせる。
// 40320は8!
ll solve_odd(int n) {
  return (dp[8][n][0][0] + dp[8][n][0][1] + dp[8][n][1][0]) * 40320;
}

// 最初のセットと最後のセットの座り方に注意して足し合わせる。
ll solve_even(int n) {
  ll ans = 0;
  REP(i,3) REP(j,3) {
    if (i==1&&j==2 || i==2&&j==1) continue;
    ans += dp2[8][n/2][i][j];
  }
  return ans * 40320;
}

int main() {
  odd_init();
  even_init();
  int n;
  while(cin>>n,n) {
    if (n&1) {
      cout << solve_odd(n) << endl;
    } else {
      cout << solve_even(n) << endl;
    }
  }
}