No.93 ペガサス
- 1,2,...,n の順列のうち特定の条件を満たすものを求める問題。
- 1,2,...,n の順番で挿入しながら順列を作ると考えることで、状態に遷移(方向性)をもたせることができるのかー。
- 最初 (n,n-2) の隣接フラグをなんで持たせるのかがわからなかった。次のループで必要になるからか。現在のループで次の (n,n-2) フラグが更新できることまで見抜けないと DP の設計ができないなぁ..。
class Pegasus { public: void solve(void) { // // 縦横にはおけないのと N*N 盤面であることから // // +-+-+-+-+ // | |o| | | // +-+-+-+-+ // |o| | | | // +-+-+-+-+ // | | | |o| // +-+-+-+-+ // | | |o| | // +-------+ // [2,1,4,3] // // のように 1...n の順列のうち隣り合う数字との差の絶対値が // 2 にならないようなものの総数を求めれば良い。 // 以下隣接する数字の差の絶対値が 2 になる条件を cond と表す。 // // 挿入 DP でやる。 // 1,2,3,..,N の順に挿入して順列をつくると考える。 // // 1,2,..,n の順列にたいして n+1 を挿入する時 // * n-1 の隣に挿入してしまうと cond をみたすものが 1 つできる。 // (1,2,... の順で挿入するので片側だけ考えれば良い。) // * ただし n-3,n-1 が隣接するとき間に cond を満たすものの総数は変わらない ((-1) + (+1) = 0) // * それ以外の cond をみたす隣接2数の間に挿入すれば cond を満たすものの総数を減らせる。 // // n+1 の挿入時に n-3,n-1 が隣接しているかの情報が必要になる。 // つまり次の更新時のために n,n-2 が隣り合うかの情報更新が必要。 // // 以上を踏まえると dp は // dp[n][k][a][b] := n 番目まで挿入したときに、 cond をみたす場所が k 個あるときの挿入結果の総数 // ただし a==1 のとき (n-3,n-1) が隣接 // ただし b==1 のとき (n-2,n) が隣接 // // となる。 int N; cin>>N; vector<vector<vector<vector<ModInt>>>> dp; mdv::resize(dp, N+1, N+1, 2, 2, 0); dp[1][0][0][0] = 1; // O(N^2) FOR(n,1,N) REP(k,N) REP(a,2) REP(b,2) { if (n == 1) { // 1 枚しかないときはどこに挿入しても cond を満たさない dp[n+1][k][0][0] += (n+1)*dp[n][k][a][b]; continue; } // (n-2,n) -> (n-3,n-1) // (n-1,n+1) -> (n-2,n) if (a==1) // (n-3,n-1) が隣接 { // n-1 のとなりに挿入するケース // (n-3,n-1) の間に挿入 dp[n+1][k][b][1] += dp[n][k][a][b]; // (n-3,n-1)じゃないほうの n-1 のとなり dp[n+1][k+1][b][1] += dp[n][k][a][b]; // cond 総数を減らすような挿入。 k-1 なのは上の (n-3,n-1) のケースを省くから if (k >= 1) { if (b==1) // (n-2,n) が隣接するケース { // (n-2,n) の間に挿入 dp[n+1][k-1][0][0] += dp[n][k][a][b]; // それ以外 dp[n+1][k-1][1][0] += ((k-1)-1)*dp[n][k][a][b]; } else dp[n+1][k-1][b][0] += (k-1)*dp[n][k][a][b]; } // のこり (n+1) なのは 1,...,n の両側を含めるから dp[n+1][k][b][0] += ((n+1)-k-1)*dp[n][k][a][b]; } else { // n-1 のとなりに挿入(左右二通り) dp[n+1][k+1][b][1] += 2*dp[n][k][a][b]; // k を減らすような挿入 if (k >= 1) { if (b==1) { // (n-2,n) の間に挿入 dp[n+1][k-1][0][0] += dp[n][k][a][b]; // それ以外 dp[n+1][k-1][1][0] += (k-1)*dp[n][k][a][b]; } else dp[n+1][k-1][b][0] += k*dp[n][k][a][b]; } // のこり dp[n+1][k][b][0] += ((n+1)-k-2)*dp[n][k][a][b]; } } cout<<dp[N][0][0][0]<<endl; } };
