AtCoder Beginner Contest 309 G - Ban Permutation
メモ
制約的に箱根駅伝dpを考える
from(1~N)からto(1~N)の全単射について、fromからtoへ辺を貼っていく問題だと考えると
箱根dpの性質から、まだ行き先が決まってないfromと元が決まっていないtoの数が一致する。この決まってない数をnとする
i個目について考えている際に、必要な情報は直前X-1個のfrom, toが決まっているかだけであるまる
これらをfx, txとして
dp[i][n][fx][tx] := iまで見た時、n個決まっていなくて 直近のfromの空きをfx, toの空きをtxとしたときの場合の数
とすると、遷移できる
fxをマスクで表現する際に、下位のbitに行くほど左の点であるようにすると
一つずれるときに>>1をするだけで済むのでわかりやすい
012...x-2, i
