Description

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

n,k<=20,m<=n*(n-1)，保证矛盾关系不重复。

Solution

状压DP，f[S][K]表示当前队伍状态为S，违背K条矛盾关系的方案数。

易得转移方程f[S|2^{(i-1)][k+sum(i&p[i])]=f[S|2}(i-1)][k+sum(i&p[i])]+F[S][K]

其中i表示某个不在队伍的人，num(i)表示i在二进制下1的个数，p[i]表示排在i后面的人的情况

Code

#include <cstdio>

#define MOD 1000000007

int n, m, k, f[1 << 21][21], p[21], tot[1 << 21];

int main()

{

scanf("%d%d%d", &n, &m, &k);

for (int i = 0; i <= (1 << n) - 1; ++i)

{

	int x = i;

	while (x)

	{

		tot[i]++;

		x &= (x - 1);

	}

}

while (m--)

{

	int u, v;

	scanf("%d%d", &u, &v);

	p[u] |= (1 << (v - 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 g = 1; g <= n; ++g)

				if (!(i & (1 << (g - 1))))

					if (j + tot[i & p[g]] <= k)

						f[i | (1 << (g - 1))][j + tot[i & p[g]]] = (f[i | (1 << (g - 1))][j + tot[i & p[g]]] + f[i][j]) % MOD;

int Ans = 0;

for (int i = 0; i <= k; ++i)

	Ans = (Ans + f[(1 << n) - 1][i]) % MOD;

printf("%d\n", Ans);

return 0;

}