問題概要
将棋での、飛車と桂馬をあわせた駒を$N×N$の盤面に$N$個置く。 ある駒から他の駒を取れないように置くとして、何通り置くことができるか。$mod 10^9+7$で出力せよ。
$N\leqq10^3$
解法
重要な点として愚直に状態を管理すると$2^{N}$だけメモリが必要。
またコマを一箇所に置くとその縦横には置けない、置いたコマの2つ上のマスの段では3つだけ場所が制限される。
このままでは厳しいので問題を次のように読み替える。
コマを置いたy座標を数字と見ると、禁止条件は$|yi-yj|=2$なので、
隣接する数字の差が2でないように1~Nの数字を並び替えたときの組み合わせ数を求めろ。という問題になる。
これは挿入DP?と呼ばれるもので解くことができて、条件をみたしていないものを状態に含めるとかなり計算量が落ちる。(例：AOJ 箱根)
$dp(i,j,x,y):=1$から$i$まで入れて、$j$個条件を満たさないものがあり、かつその中に$[x:i-2,i-4],[y:i-1,i-3]$が隣接しているか否か
として解くことができる。
挿入DPよりもここに帰着するほうが難しい気がする。
計算量:$O(N^2)$
ソース
https://yukicoder.me/submissions/252978 (oがいまから置く駒)