HDU 4917 Permutation(拓扑排序 + 状压DP + 组合数)

题目链接 Permutation

题目大意:给出n,和m个关系,每个关系为ai必须排在bi的前面,求符合要求的n的全排列的个数。

数据规模为n <= 40,m <= 20。 直接状压DP空间肯定是不够的。

考虑到m <= 20,说明每个连通块的大小不超过21。

那么我们分别对每个连通块求方案数,并且把不同的连通块的方案数组合起来即可。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const LL mod = 1e9 + 7; const int N = 105; int n, m, s, cnt;
int mp[N][N], a[N][N], b[N], col[N], pre[N];
LL c[N][N], f[1 << 22], ans;
vector <int> v[N]; void init(){
c[0][0] = 1;
rep(i, 1, N - 2){
c[i][0] = 1;
rep(j, 1, i - 1){
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
c[i][j] %= mod; }
c[i][i] = 1;
}
} void dfs(int x){
col[x] = cnt;
for (auto u : v[x]){
if (col[u]) continue;
dfs(u);
}
} int main(){ init(); while (~scanf("%d%d", &n, &m)){ rep(i, 0, n + 1) v[i].clear();
memset(mp, 0, sizeof mp);
memset(col, 0, sizeof col);
rep(i, 1, m){
int x, y;
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
mp[x][y] = 1;
mp[y][x] = -1;
} cnt = 0;
rep(i, 1, n) if (!col[i]) ++cnt, dfs(i); memset(b, 0, sizeof b);
rep(i, 1, n) a[col[i]][b[col[i]]++] = i; s = n;
ans = 1; rep(i, 1, cnt){
int maxS = (1 << b[i]) - 1;
rep(j, 0, maxS + 2) f[j] = 0;
f[0] = 1LL;
memset(pre, 0, sizeof pre);
rep(j, 0, b[i] - 1){
rep(k, 0, b[i] - 1) if (j ^ k){
if (mp[a[i][j]][a[i][k]] == 1) pre[k] |= (1 << j);
}
} rep(S, 0, maxS) if (f[S] > 0){
rep(j, 0, b[i] - 1){
if (((S & pre[j]) == pre[j]) && !(S & (1 << j))){
f[S | (1 << j)] += f[S];
f[S | (1 << j)] %= mod;
}
}
} ans = ans * f[(1 << b[i]) - 1] % mod * c[s][b[i]] % mod;
s -= b[i];
} printf("%lld\n", ans);
}
return 0;
}
上一篇:HDU 1074:Doing Homework(状压DP)


下一篇:【代码笔记】Web-CSS-CSS 链接(link)