题目描述
现在有n个人要排成一列，编号为1->n 。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐，最多不能违背k条矛盾关系（即不能有超过k条矛盾关系(u,v),满足最后v排在了u前面）。问有多少合法的排列。答案对10^9+7取模。
思路
看到数据范围就应该可以想到可以用状压dp，我们用f[i][j]表示第i终状态违背了j次的排列数量，i这个状态在二进制中表示每一位有没有被选到
我们先考虑转移，我们如果要将一个人加入到一种状态里面，显然当他加进去时总的违背数量不可以超过k，我们可以处理出一个数组a[i],表示和i冲突的人的具体状态(二进制)
对于i这个状态，如果我们要加入一个人x，那么(i&a[x])中1的个数+j一定要<=k
然后我们再可以预处理一个数组tot[i]，表示i这个状态里面一共有多少个1，其他的就没什么好讲的了
#include <stdio.h>
#include <iostream>
#define LL long long
#define p 1000000007
#define maxn 1 << 22
inline int read()
{
int x=0;char ch=getchar();
while (ch<'0'||ch>'9'){ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x;
}
int tot[maxn], a[22], f[maxn][22];
int main()
{
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
int n = read(), m = read(), k = read();
for (int i = 0; i <= (1 << n) - 1; i++)
{
int x = i;
while (x)
{
tot[i]++;
x = x & (x - 1);
}
}
for (int i = 1; i <= m; i++)
{
int x = read(), y = read();
a[x] |= 1 << (y - 1);
}
f[0][0] = 1;
for (int i = 0; i <= (1 << n) - 1; i++)
for (int j = 0; j <= k; j++)
if (f[i][j])
{
for (int x = 1; x <= n; x++)
{
if (~i&(1<<(x-1)))
if (j + tot[i&a[x]] <= k)
f[i|1<<(x-1)][j + tot[i&a[x]]] = (f[i|1<<(x-1)][j + tot[i&a[x]]] + f[i][j]) % p;
}
}
long long ans = 0;
for (int i = 0; i <= k; i++)
ans += f[(1<<n)-1][i]%p;
std::cout << ans % p << std::endl;
}