BZOJ3812: 主旋律

Sol

考虑容斥

强联通图反过来就是一些缩点后的 \(DAG\)

一个套路就是对出(入)度为 \(0\) 的点进行容斥

设 \(g_S,h_S\) 分别表示选了奇数个 \(0\) 入度和偶数个的，集合为 \(S\) 的方案数

那么通过钦定一个特殊的点 \(u\) 有

\[g_S=\sum_{T\subset S,u \in T}f_Th_{S-T}
\]

\[h_S=\sum_{T\subset S,u \in T}f_Tg_{S-T}
\]

那么考虑容斥求出 \(f\)，由于 \(g_S\) 包含 \(f_S\)，而且 \(f_S\) 合法，所以容斥的时候 \(g_S\) 不能包括 \(f_S\)

那么

\[f_S=2^{|E_{\{S\}}|}+\sum_{T\subset S,T\ne S}(h_T-g_T)2^{E_{\{S-T\}}+E{_{\{T\}->\{S-T\}}}}
\]

这里的 \(g_S\) 不包括 \(f_S\)，\(E\) 表示边集，\(\{S\}->\{T\}\) 即集合 \(S\) 到 \(T\) 的边

可以通过把子集弄出来做优化到 \(\Theta(3^n)\)

不过我没有写QwQ

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod(1e9 + 7);

int n, m, f[1 << 15], g[1 << 15], h[1 << 15], cnt[1 << 15], to[20], e[1 << 15], pw[300];

inline void Inc(int &x, int y) {

	if ((x += y) >= mod) x -= mod;

}

int main() {

	register int i, a, b, t, s, j;

	scanf("%d%d", &n, &m), t = 1 << n;

	for (i = 1; i <= m; ++i) scanf("%d%d", &a, &b), --a, --b, to[a] |= 1 << b;

	for (i = 1; i < t; ++i) cnt[i] = cnt[i >> 1] + (i & 1);

	for (pw[0] = i = 1; i <= m; ++i) {

		pw[i] = pw[i - 1] << 1;

		if (pw[i] >= mod) pw[i] -= mod;

	}

	for (i = 0; i < t; ++i)

		for (j = 0; j < n; ++j) if (i >> j & 1) e[i] += cnt[to[j] & i];

	for (i = 0; i < n; ++i) f[1 << i] = g[1 << i] = 1;

	for (i = 1; i < t; ++i)

		if (cnt[i] > 1) {

			f[i] = pw[e[i]];

			for (a = 0; a < n; ++a) if (i >> a & 1) break;

			for (j = (i - 1) & i; j; j = (j - 1) & i) {

				for (s = b = 0; b < n; ++b) if (i >> b & 1) s += cnt[to[b] & (i ^ j)];

				Inc(f[i], 1LL * (h[j] - g[j] + mod) * pw[s] % mod);

				if (j >> a & 1) {

					Inc(g[i], 1LL * f[j] * h[i ^ j] % mod);

					Inc(h[i], 1LL * f[j] * g[i ^ j] % mod);

				}

			}

			Inc(f[i], (h[i] - g[i] + mod) % mod), Inc(g[i], f[i]);

		}

	printf("%d\n", f[t - 1]);

	return 0;

}

巴特西

BZOJ3812: 主旋律

Sol

最新文章

热门文章