P4547 [THUWC2017]随机二分图（状压，期望DP）

期望好题。

发现 \(n\) 非常小，应该要想到状压的。

我们可以先只考虑 0 操作。

最难的还是状态：

我们用 \(S\) 表示左部点有哪些点已经有对应点， \(T\) 表示右部点有哪些点已经有对应点，\(f[S][T]\) 表示从一条边没连到此状态的期望方案数

这样就有转移：

\[f[S][T] <- \sum_{s \in S,t \in T}f[S \oplus s][T \oplus t] * p(s, t)
\]

也就是说，从没选的点中选俩点连边。不过这可能会算重（先连 \(e_1\) 后连 \(e_2\) 和先连 \(e_2\) 后连 \(e_1\) 都会计入答案）。因此我们强制要求选择 \(S\) 中编号最小的点连边，这样每种答案就只被计算一次了。

然后考虑 1，2 操作。1，2 操作并没有改变两条边各自出现的概率，只是改变的两条边同时出现的概率。因此我们可以加一些特殊的边 \(e_1, e_2\) ，并要求 \(e_1, e_2\) 必须一起被选，这样就可以调节同时出现的期望。具体来说就是 1 操作加 \(\frac{1}{4}\)，2操作减 \(\frac{1}{4}\)。

然后就没啥难点了。考虑到合法状态数不多，直接记忆化搜索即可。

const int P = 1e9 + 7;

inline ll quickpow(ll x, int k) {

	ll res = 1;

	while (k) {

		if (k & 1)	res = res * x % P;

		x = x * x % P;

		k >>= 1;

	}

	return res;

}

int inv2, inv4;

int n, m;

struct edge {

	int s, t, p;

}e[N];

int ecnt;

map<int, ll> mp[NN];

inline ll dfs(int S, int T) {

	if (S == 0 && T == 0)	return 1;

	if (mp[S].count(T))	return mp[S][T];

	ll res = 0;

	for (register int i = 1; i <= ecnt; ++i) {

		int s = e[i].s, t = e[i].t, p = e[i].p;

		if (((S | s) != S) || ((T | t) != T))	continue;

		if ((s | (lowbit(S))) != s)	continue;

		res = (res + dfs(S ^ s, T ^ t) * p) % P;

	}

	mp[S][T] = res;

	return res;

}

int main() {

	inv2 = quickpow(2, P - 2);

	inv4 = quickpow(4, P - 2);

	read(n), read(m);

	for (register int i = 1; i <= m; ++i) {

		int t, x, y; read(t), read(x), read(y);

		--x, --y;

		e[++ecnt] = (edge){1 << x, 1 << y, inv2};

		if (t) {

			int a, b; read(a), read(b);

			--a, --b;

			e[++ecnt] = (edge){(1 << a), (1 << b), inv2};//Attention!

			if (a == x || b == y)	continue;

			e[++ecnt] = (edge){(1 << x) | (1 << a), (1 << y) | (1 << b), t == 1 ? inv4 : P - inv4};

		}

	}

	ll ans = dfs((1 << n) - 1, (1 << n) - 1) * (1 << n) % P;

	printf("%lld\n", ans);

	return 0;

}

巴特西

P4547 [THUWC2017]随机二分图（状压，期望DP）

最新文章

热门文章