题目大意：

题目链接：https://jzoj.net/senior/#main/show/5230
现在有$n$个人要排成一列，编号为$1\sim n$ 。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有$m$条矛盾关系$(u,v)$,表示编号为$u$的人想要排在编号为$v$的人前面。要使得队伍和谐，最多不能违背$k$条矛盾关系（即不能有超过$k$条矛盾关系$(u,v)$,满足最后$v$排在了$u$前面）。问有多少合法的排列。答案对$10^9+7取$模。

---

思路：

$n\le 20$，考虑状压$dp$。
很明显除了状态那一维还需要一维记录违背了多少关系。
于是就设$f[S][i]$表示状态为$S$，违反了$i$条关系的方案数。
那么就有
$$f[S][j]=(f[S][j]+f[lastS][j-sum])\%MOD$$

其中$lastS$表示上一个状态，可以通过枚举最后是那个人进入来求。
时间复杂度$O(2^{n}n(n+k))$

---

代码：

#include <cstdio>
using namespace std;const int N=21;
const int MAXN=1048600;
const int MOD=1e9+7;
int n,m,k,x,y,ans,f[MAXN][N],hate[N];int main()
{freopen("count.in","r",stdin);freopen("count.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for (int i=1;i<=m;i++){scanf("%d%d",&x,&y);hate[y]|=(1<<(x-1));}f[0][0]=1;for (int S=1;S<(1<<n);S++)for (int i=1;i<=n;i++)if ((S&(1<<(i-1)))==(1<<(i-1))){int lastS=S-(1<<(i-1)),sum=0;for (int j=1;j<=n;j++)if ((hate[i]&(1<<(j-1)))==(1<<(j-1))&&(lastS&(1<<(j-1)))==(1<<(j-1)))sum++;for (int j=sum;j<=k;j++)f[S][j]=(f[S][j]+f[lastS][j-sum])%MOD;}for (int i=0;i<=k;i++)ans=(ans+f[(1<<n)-1][i])%MOD;printf("%d\n",ans);return 0;
}