2020-2021 Winter Petrozavodsk Camp (Day 2: UPC Contest) A. Adjacent Rooks

問題のリンク

問題概要

$N \times N$ のグリッドにルークを互いに攻撃し合わないように配置する。ただし、斜めに隣接するルークのペアが丁度 $ K $ となる配置の数を $10^{9}+7$ で割った余りを求めよ。

制約

• $1 \leq N \leq 1000$
• $0 \leq K \leq N-1$

解法

$ 1 $ から $ N $ の順列であって、隣り合う項の差の絶対値が 1 となるようなペアが丁度 $K$ 個存在する順列を数え上げれば良い。

dp[i][j][k] := 1からiまでの順列でペアがj個の順列の総数(kはiとi-1がペアになっているかのフラグ)

として、数列に要素を挿入していく動的計画法を考える。

要素を挿入したことによって起こる遷移は、

• 新たにペアが1つ増える場合
• 既存のペアが1つ解消される場合
• ペア数に変化がない場合

この3つに分けられ、上の $i,j,k$ で遷移に必要な情報は揃っている。

実装

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int mod = 1e9+7;

void add(int &x,int y){
    x+=y;
    if(x>=mod)x-=mod;
}

int dp[1010][1010][2];

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q; cin >> q;
    dp[1][0][0] = 1;
    for(int i=1;i<1000;i++){
        for(int j=0;j<=i;j++){
            // i+1とiがペアになる場合
            add(dp[i+1][j+1][1],dp[i][j][0]);
            add(dp[i+1][j+1][1],dp[i][j][0]);
            add(dp[i+1][j+1][1],dp[i][j][1]);
            add(dp[i+1][j][1],dp[i][j][1]);
            // 既存のペアを解消する場合
            if(j)add(dp[i+1][j-1][0],(ll)dp[i][j][0]*(ll)j%mod);
            if(j)add(dp[i+1][j-1][0],(ll)dp[i][j][1]*(ll)(j-1)%mod);
            // その他の場合(変化なし)
            add(dp[i+1][j][0],(ll)dp[i][j][0]*(ll)(i+1-2-j)%mod);
            add(dp[i+1][j][0],(ll)dp[i][j][1]*(ll)(i+1-(j-1)-2)%mod);
        }
    }
    while(q--){
        int n,k; cin >> n >> k;
        cout << (dp[n][k][0]+dp[n][k][1])%mod << "\n";
    }
}