E - Permutation

考场上因为没时间了没做出来……主要是 C 题脑抽了
（没事，前面几场失误不要紧，反正不可能让你 Rating 一下子冲天。今后吸取教训就好）

状压 dp。
我们设 表示当前选择的数的状态有多少种情况。

1. 如果没有题目中的条件约束，， （其中 是 的子集且只相差一个元素）。初步转移方程列好。
2. 判断条件约束。如果当前已经选择了 个元素，并且状态下 的值 ，该状态下 。我们先用一个数组表示一个状态每一位上是否是 ，并求个前缀和，判断时会方便很多。

代码：

#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;
}