现在有n个人要排成一列,编号为1->n .但由于一些不明原因的关系,人与人之间可能存在一些矛盾关系,具体有m条矛盾关系(uv)表示编号为u的人想要排在编号为v的人前面.要使得队伍和谐,最多不能违背k条矛盾关系(即不能有超过k条矛盾关系(uv)满足最后v排在了u前面).问有多少合法的排列.答案对10^9+7取模.
我们先考虑转移,我们如果要将一个人加入到一种状态里面,显然当他加进去时总的违背数量不可以超过k,我们可以处理出一个数组a[i]表示和i冲突的人的具体状态(二进制)
对于i这个状态,如果我们要加入一个人x,那么(i&a[x])中1的个数+j一定要<=k