E - Permutation
考场上因为没时间了没做出来……主要是 C 题脑抽了
（没事，前面几场失误不要紧，反正不可能让你 Rating 一下子冲天。今后吸取教训就好）
状压 dp。
我们设 表示当前选择的数的状态有多少种情况。
- 如果没有题目中的条件约束，
，
（其中
是
的子集且只相差一个元素）。初步转移方程列好。
- 判断条件约束。如果当前已经选择了
个元素，并且状态下
的值
，该状态下
。我们先用一个数组表示一个状态每一位上是否是
，并求个前缀和，判断时会方便很多。
代码：
#include<iostream>
#include<vector>
using namespace std;
#define int long long
int dp[1<<20],n,m,x[110],y[110],z[110],tmp[110];
bool ok[1<<20];
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x[i]>>y[i]>>z[i];
}
dp[0]=1;
for(int i=1;i<(1<<n);i++){
for(int j=0;j<n;j++){
if(i&(1<<j)) tmp[j]=1;
else tmp[j]=0;
}
for(int j=1;j<n;j++){
tmp[j]+=tmp[j-1];
}//求前缀和
bool flag=true;
for(int j=1;j<=m;j++){
if(tmp[n-1]==x[j]&&tmp[y[j]-1]>z[j]){
flag=false;
}//注意 tmp[n-1]==x[j] 不能落下，位数要匹配
}
ok[i]=flag;
} // 判断
dp[0]=1;
for(int i=1;i<(1<<n);i++){
if(!ok[i]) continue;
for(int j=0;j<n;j++){
if((i&(1<<j))==(1<<j))
dp[i]+=dp[i-(1<<j)];
}
}
cout<<dp[(1<<n)-1]<<endl;// 状压 dp
return 0;
}
