专栏文章

题解：P11714 [清华集训 2014] 主旋律

CCatFromMars
P11714题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mioqyppf
此快照首次捕获于
2025/12/02 23:42
3 个月前
此快照最后确认于
2025/12/02 23:42
3 个月前
查看原文
参考了各种题解，太牛了这题，学习 qwq。
首先考虑判定一张强连通图，要缩点。缩点后一个点那么就是一张强连通图，是一个 DAG 就是一个非强连通图。单点条件很严苛，正难则反。如果我们已经知道每个点属于哪个强连通分量，那么做一次 DAG 子图计数就能计算出来不合法的方案数。问题在于我们不知道每个点属于哪个强连通分量。但是实际上我们并不在乎整个 DAG 的具体形态，而是只在乎“它是一个 DAG 而不是一个单点”。为了描述这件事情我们只需要找到一组入度为 00 的强连通分量即可，剩下的不用在乎。
先设 ES,TE_{S, T} 为 SS 到 TT 边数，HSH_S 为 SS 内部边数。
fSf_S 为 SS 内所有点在一个强连通分量的方案数，总方案数 2HS2^{H_{S}}。要减去不合法的方案数。根据上面的我们枚举 T⊂ST\subset S，代表钦定 TT 内的点缩点后形成的强连通分量是 DAG 中入度为 00 的点，其它任意。因为这每次只会考虑到一个子集，通过子集反演可以得到形成 tt 个联通分量那么容斥系数为 (−1)t+1(-1)^{t+1}。我们无法在计算 fSf_S 时通过枚举 TT 的方式直接得到容斥系数。需要在计算 TT 内部连边方法时计算。TT 之外 TT 到 (S−T)(S - T) 的连边任意，(S−T)(S - T) 内部连边也任意，这部分是 2ET,S−T+HS−T2^{E_{T, S - T} + H_{S - T}} 的。
令 gTg_T 为形成奇数个强连通分量的方案数减去形成偶数个强连通分量。那么 fS=2HS−∑T⊂S,T≠∅gT2ET,S−T+HS−Tf_S = 2^{H_{S}} - \sum\limits_{T \subset S, T\not = \empty} g_T2^{E_{T, S - T} + H_{S - T}}。现在对 gg 计算。如果没有容斥系数那么 gS=∑lowbit(S)⁡∈T⊂SfTgS−Tg_S = \sum\limits_{\operatorname{lowbit(S)}\in T\subset S}f_Tg_{S - T}。现在有了容斥系数，奇偶数量变化，这些都要取反，特别的 T=ST = S 时 fTf_T 不用取反。gS=fS−∑lowbit⁡(T)∈T⊊SfTgS−Tg_S = f_S - \sum\limits_{\operatorname{lowbit}(T)\in T \subsetneq S} f_Tg_{S - T}。我们发现很严重的事情在于是不是计算 fSf_S 的时候要用到 gSg_S。但是 gSg_S 中 fSf_S 这部分代表的是 SS 全在一个连通分量中的方案数，在 ff 中是合法的，不应该减去。因此我们先处理 gSg_S，令此时 fSf_S 为 00，然后再处理 fSf_S，最后把 gSg_S 加上 fSf_S 即可。
本来对于 EE 我是用 O(3n)O(3^n) 写的，但是因为我调用了 O(3n)O(3^n) 次 unordered_map 常数爆炸导致跑的还没还有 O(n3n)O(n3^n) 快（悲。
CPP
#include <bits/stdc++.h>
#define il inline
using namespace std;
const int N = 15, Mod = 1e9 + 7;
il int lowbit(int x) {
	return x & (-x);
}
il void upd(int &x, int y) {
	x = (((x + y) >= Mod) ? (x + y - Mod) : (x + y));
}

int n, m, bas2[N * N + 10];
bool gra[N + 3][N + 3];
int H[(1 << N) + 10], out[(1 << N) + 10];
int f[(1 << N) + 10], g[(1 << N) + 10];
int E(int S, int T) {
	int rest = 0;
	while(S) {
		int R = lowbit(S);
		rest += __builtin_popcount(out[R] & T);
		S -= R;
	}
	return rest;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	bas2[0] = 1;
	for(int i = 1, x, y; i <= m; i++) {
		cin >> x >> y;
		x--, y--;
		bas2[i] = bas2[i - 1] * 2 % Mod;
		gra[x][y] = 1;
		for(int S = 0; S < (1 << n); S++)
			if(((S >> x) & 1) && ((S >> y) & 1))
				H[S]++;
		out[(1 << x)] |= (1 << y);
	}

	for(int S = 1; S < (1 << n); S++) {
		if(__builtin_popcount(S) == 1) {
			f[S] = g[S] = 1;
			continue;
		}
		for(int T = S - lowbit(S); ; T = (T - 1) & (S - lowbit(S))) {
			int R = T + lowbit(S);
			upd(g[S], (Mod - 1ll * f[R] * g[S - R] % Mod) % Mod);
			if(!T) break;
		}
		f[S] = bas2[H[S]];
		for(int T = S; T; T = (T - 1) & S)
			upd(f[S], (Mod - 1ll * g[T] * bas2[E(T, S - T) + H[S - T]] % Mod) % Mod);
		upd(g[S], f[S]);
	}
	cout << f[(1 << n) - 1] << endl;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...