现在有n个人要排成一列，编号为1->n 。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐，最多不能违背k条矛盾关系（即不能有超过k条矛盾关系(u,v),满足最后v排在了u前面）。问有多少合法的排列。答案对10^9+7取模。
这道题是我状压dp的第一道题，让我对状压有了无限感觉，今晚要继续做状压dp的题目。
考试时完全没有想到正解的，结果用搜索暴力骗了30分。（这些题让我越来越暴力）
首先，要写出转移方程。f[s][p]表示选了s集合中的这些人，有p条矛盾。
s是集合，是一个二进制数，每一位的1，0，表示选或者不选。状态转移方程就是把s中的某个为0的x位变成1，p变成p+增加的矛盾，而表示的值就是加上不选的。
现在，问题就转移到如何知道增加的矛盾上了。
用fal[x]表示排在x后面的数的集合，每次用s&fal[x]的1的个数就是了。
此处有一个小技巧，用
for(int i=1;i<=(1<<n)-1;i++) cnt[i]=cnt[i-(i&-i)]+1;
来计算1的个数。
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
const int L = 1050000;
const int N = 21;
const int mo = 1e+9+7;
inline int read(){
int data=0,w=1; char ch=0;
while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
return data*w;
}
int n,m,k,u,v;
int g[L][N],f[L][N],fal[N],cnt[L];
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
n=read();m=read();k=read();
for(int i=1;i<=m;i++){
u=read();
v=read();
fal[u]=fal[u]+(1<<(v-1));
f[i|(1<<(x-1))][j+g[i][x]]=(f[i|(1<<(x-1))][j+g[i][x]]%mo+f[i][j]%mo)%mo;
int ans=0;
for(int i=0;i<=k;i++) ans=(ans%mo+f[(1<<n)-1][i]%mo)%mo;
printf("%d\n",ans);
return 0;
}