题意:一长度为\(n\)的序列,有\(m\)个限制条件,问有多少排列方法使得题目所给的\(m\)个限制条件都满足.

题解:\(n\)给的范围很小,我们可以状态压缩,\(v[num][j]\)表示题目所给的限制条件前\(num\)个数最多不大于\(y\)的个数,我们可以枚举所有情况,然后判断每个状态是否和题目所给的条件冲突,如果冲突,我们就不转移.

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
 
int n,m;
int v[25][25];
ll dp[1<<20];
 
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	rep(i,0,20){
		rep(j,0,20){
			v[i][j]=INF;
		}
	}
 
	rep(i,1,m){
		int x,y,z;
		cin>>x>>y>>z;
		v[x][y-1]=min(v[x][y-1],z);
	}
 
	dp[0]=1;
	rep(i,1,(1<<n)-1){
		int num=0;
		rep(j,0,n-1) if(i&(1<<j)) num++;
		int sum=0;
		bool flag=true;
		rep(j,0,n-1){
			if(i&(1<<j)) sum++;
			if(sum>v[num][j]){
				flag=false;
				break;
			}
		}
		if(flag){
			rep(j,0,n-1){
				if(i&(1<<j)){
					dp[i]+=dp[i^(1<<j)];
				}
			}
		}
	}
 
	cout<<dp[(1<<n)-1]<<'\n';
 
    return 0;
}