https://kanpurin.hatenablog.com/entry/2021/04/29/190823

別解です．ほぼ一緒なので丁寧には書きません．

問題概要

${(1,2,3,\cdots,N)}$ を並び替えてできる数列 ${A}$ で，以下の条件を満たすものの数を求めよ．

${1\leq i\leq N}$ を満たす全ての数列 ${i}$ について， ${A_1,A_2,A_2,\cdots,A_{X_i}}$ の中に ${Y_i}$ 以下の数は ${Z_i}$ 個以下しか存在しない．

${2\leq N \leq 18\\ 0 \leq M \leq 100\\ 1\leq X_i < N\\ 1\leq Y_i < N\\ 0\leq Z_i < N\\}$

公式解説では数列を左端から決めて，使った数を状態として持つDPをしていましたが，小さい数から位置を決めていくことを考えます．DPでは数列中の既に決まった位置を持っておきます．すると遷移は

となります．条件を満たすかを見るときは ${|S|=Y_i}$ となる条件のみを見ればいいです．この方針だと任意の区間(位置)の条件でも解くことができるはず(たぶん)．

制約がbitDP