第一题:
ZJOI小星星
题目链接:https://www.luogu.org/problem/P3349
题目大意:给定n个点m条边的无向图,和一个n个点的树,求出有多少个从树到图的映射。n<=17,m<=n*(n-1)/2
方法:先不考虑重复映射的情况。定义f[u][i]为把树上的节点u映射到图中的节点i的方案数。转移方程如下:
然后答案为
然而题目要求必须一一映射,不能重复映射。考虑用容斥。
最终答案为能够映射到所有节点的答案,减去能够映射到某(n-1)个节点的方案,加上能够映射到某(n-2)个节点的方案,以此类推。复杂度
代码:
#include <iostream>
#include <bitset>
#include <vector>
#include <cstring>
using namespace std;
#define DEBUG 0
#define MAXN 18
typedef long long LL;
struct GRAPH {
int> > s;
vector<vector<void ClearEdges() {
for (auto& i : s)
0);
i.resize(
}void Init(int n) {
ClearEdges();1);
s.resize(n+
}void AddUndi(int u, int v) {
s[u].push_back(v);
s[v].push_back(u);
}
};
GRAPH g, G;
bitset<MAXN> ban;int n;
LL f[MAXN][MAXN];bool vis[MAXN];
void dfs(int u) {
true;
vis[u] = for (int i = 0; i < n; ++i) {
0 : 1;
f[u][i] = ban[i] ?
}for (int v : g.s[u]) {
if (vis[v]) continue;
dfs(v);for (int i = 0; i < n; ++i) {
if (ban[i]) continue;
0;
LL res = for (int j : G.s[i]) {
if (ban[j]) continue;
res += f[v][j];
}
f[u][i] *= res;
}
}
}int main() {
int m;
cin >> n >> m;
g.Init(n);
G.Init(n);
while (m--) {
int u, v;
cin >> u >> v;
--u;
--v;
G.AddUndi(u, v);
}1;
m = n-while (m--) {
int u, v;
cin >> u >> v;
--u;
--v;
g.AddUndi(u, v);
}0;
LL ans = for (int s = 0, maxs = 1 << n; s < maxs; ++s) {
0, n * sizeof(bool));
memset(vis,
ban = s;0);
dfs(0;
LL now = for (int j = 0; j < n; ++j) {
0][j];
now += f[
}if (ban.count() & 1)
ans -= now;else
ans += now;#if DEBUG
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
' ';
cout << f[i][j] <<
}
cout << endl;
}
cout << endl;#endif
}
cout << ans << endl;
return 0;
}
第二题:
luogu 4336 SHOI2016黑暗前的幻想乡
题意:有n个点(n <= 17),(n-1)家公司,第i家公司能建造
思路:首先考虑所有公司都能参与,然后使图连通的方案数。这些方案里包含了一些某些公司没有参与的方案。所以减去有一家公司没有参与的方案数。然后加上有两家公司没有参与的方案数。以此类推,最后得到的就是每家公司都参与了的方案数。复杂度
代码:
#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 21
typedef long long LL;
const int p = 1000000007;
template <typename T>
int p) {
T Sub(T x, return x < 0 ? x + p : x;
}
template <typename T>
void SubMod(T& x, int p) {
if (x < 0)
x += p;
}
template <typename T>
void AddMod(T& x, int p) {
if (x >= p)
x -= p;
}
//x < p
//p must be prime
template <typename T>
int p) {
T Inv(T x, return 1 == x ? 1 : (LL)(p - p / x) * Inv(p % x, p) % p;
}
//simple
struct MATRIX {
const static int maxr = MAXN, maxc = MAXN;
int row, col;
int s[maxr][maxc];
void clear() {
for (int i = 0; i < row; ++i)
for (int j = 0; j < col; ++j)
0;
s[i][j] =
}
//O(n^3)
int det_laplacian() {
int ans = 1;
for (int i = 0; i < row && ans; ++i) {
if (0 == s[i][i]) return 0;
int invi = Inv(s[i][i], p);
for (int k = i + 1; k < row; ++k) {
if (0 == s[k][i]) continue;
int d = (LL)s[k][i] * invi % p;
for (int j = i; j < col; ++j) {
s[k][j] = (s[k][j] - (LL)s[i][j] * d) % p;
}
}
ans = (LL)ans * s[i][i] % p;
}return Sub(ans, p);
}
};
int main() {
int n;
static vector<pair<int, int> > es[MAXN];
static MATRIX ma;
"%d", &n);
scanf(
--n;
ma.row = ma.col = n;for (int i = 0; i < n; ++i) {
int m;
"%d", &m);
scanf(while (m--) {
int u, v;
"%d%d", &u, &v);
scanf(
--u;
--v;
es[i].emplace_back(u, v);
}
}int ans = 0;
for (int s = 0, maxs = 1 << n; s < maxs; ++s) {
ma.clear();for (int i = 0; i < n; ++i) {
if (0 == (s & (1 << i))) {
for (auto e : es[i]) {
--ma.s[e.first][e.second];
--ma.s[e.second][e.first];
++ma.s[e.first][e.first];
++ma.s[e.second][e.second];
}
}
}int t = ma.det_laplacian();
if (__builtin_popcount(s) & 1) {
SubMod(ans -= t, p);else {
}
AddMod(ans += t, p);
}
}"%d\n", ans);
printf(
return 0;
}