ABC 199 E - Permutation

• 問題

$\operatorname{dp}[S] :=$集合$S$に含まれる整数を数列の先頭$|S|$箇所に（制約を満たすように）配置する場合の数、としてDPできる。$S$に整数$t$を追加して$S \cup \{t\}$に遷移する時、制約は$X_i=|S|+1$であるようなものだけ調べればよい。

また、状態を入れ換えて$\operatorname{dp}[S] :=$集合$S$に含まれる位置に整数$1, 2, ..., |S|$を配置する場合の数、としてもDPできる。この場合は$|S|$に位置$t$を追加して$S \cup \{t\}$に遷移する時、制約は$Y_i = |S|+1$であるようなものだけ調べればよい。

前者と後者は同じ形の遷移になっていて、一方を書いて入力の$X$と$Y$の順番を「間違える」ともう一方になって同じ答えがでる。これらの数えているものは、数列を置換とみなしたときに逆置換で一対一対応している。