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 
    
     #define MOD 1000000007int 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;}