BitDP. 順列を決めていくが，次を決めるときに， 今まで選んだ元の集合が分かっていれば，選んだ順番は無関係．
実装
\(M\) 個の条件を調べる． 数え上げるとき，常に条件を満たしている様にとっている． つまり，\(s \in 2^{N}\) を調べ終わっていて， \(i in N\) s.t. \(i \not\in s\) に対して \(t := s \cup \{i\}\) のケースを調べるとき， \(s\) は条件を満たしている．
先頭\(x\) 個を見たとき，\(y\) 以下の個数が \(z\) 以下であるかを判定したい． \(\vert t \vert > x \) であれば，\(i\) の値に依らず条件を満たす． なぜなら，\(s\) の時点で条件を満たしているから．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n >> m;
vll x(m), y(m), z(m);
rep(i,m){
cin >> x[i] >> y[i] >> z[i];
y[i]--;
}
dp[0] = 1;
rep(s,1LL<<n) rep(c,n) if(!(s >> c & 1)){
ll t = s | (1LL << c);
vll v(n);
rep(i,n) if(t >> i & 1){ v[i]++; }
rep(i,n-1) v[i+1] += v[i];
bool any = true;
rep(i,m) {
if(pcntll(t) > x[i]) continue;
if(v[y[i]] > z[i]) any = false;
}
if(any){
dp[t] += dp[s];
}
}
cout << dp[(1LL<<n)-1] << endl;
return 0;
}
