题目描述
现在有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#include #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<
]]>
Comments NOTHING