【GDOI2020模拟4.11】赢家(winner) （计数dp+容斥）

标签：efi   space   c++   break   方案   定向   href   inline   lin   

题目描述：

PinkRabbit 是一位人赢。
福州市可以抽象成一个n个点m条边的，不包含重边与自环的无向图，PinkRabbit 住在1号
点，而他的妹子住在2号点。
某一天，PinkKitten 施放了一个大魔法，让这个无向图上所有的边都变成了单向边。现在
PinkRabbit 关心的是他是否能够和他的妹子见面。
具体地，PinkRabbit 能和他的妹子见面，当且仅当存在一个点 u，满足新图上从1号点出发能够
到达u，从2号点出发也能到达 。
现在你需要计算出，在把所有 m条边进行定向的所有2^m 种方案中，有多少种方案能让
PinkRabbit 和他的妹子见面。你只需输出其对10^9+7 取模后的结果。
\(n\le 15\)
https://gmoj.net/senior/#main/show/6554

失智了，居然写了个完完全全的dp，还过了样例，然后WA0.

考虑用总方案-不合法方案。

对于不合法方案，枚举1能走到的点集是\(S\),2能走到的点集是\(T\)，\(S∩T=?\)。

设\(Z=总集-S-T\)

那么\(Z\)和\(S、T\)之间的边方向确定，\(S\)和\(T\)之间不能有边。

现在就是求\(S\)的方案数（\(T\)同理）。

设\(f[S]\)表示\(S\)的方案数，同样用总-不合法。
不合法就是是\(S\)的一个子集\(S‘\),\(f[S]-=f[S‘]*(S‘和S-S‘中间的边定向)\)

预处理\(cnt[S]\)表示S内的边数就都可以快速计算了。

Code：

#include
#define fo(i, x, y) for(int i = x, _b = y; i = _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int mo = 1e9 + 7;

const int N = 16;

int n, m, id, x, y;
int b[N][N];
int cnt[1 > i & 1) {
			cnt[s] = cnt[s ^ (1 > j & 1)
				cnt[s] += b[i + 1][j + 1];
			break;
		}
	}
	ff(s, 1, 1  0; t = (t - 1) & s)
				f[s] = (f[s] - f[t] * a2[cnt[s ^ t]]) % mo;
		}
		if(s & 2) {
			g[s] = a2[cnt[s]];
			for(int t = (s - 1) & s; t > 0; t = (t - 1) & s)
				g[s] = (g[s] - g[t] * a2[cnt[s ^ t]]) % mo;
		} 
	}
	ll ans = a2[m];
	ff(s, 0, 1 

【GDOI2020模拟4.11】赢家(winner) （计数dp+容斥）

标签：efi   space   c++   break   方案   定向   href   inline   lin   

原文地址：https://www.cnblogs.com/coldchair/p/12680071.html