BZOJ 3812 主旋律 (状压DP+容斥) + NOIP模拟赛 巨神兵(obelisk)(状压DP)

这道题跟另一道题很像，先看看那道题吧

---

巨神兵(obelisk)

题面

• 欧贝利斯克的巨神兵很喜欢有向图，有一天他找到了一张nnn个点mmm条边的有向图。欧贝利斯克认为一个没有环的有向图是优美的，请问这张图有多少个子图（即选定一个边集）是优美的？答案对 1,000,000,0071,000,000,0071,000,000,007 取模。
• n&lt;=17n&lt;=17n<=17

分析

• 这道题就是枚举拓扑序最后的点集来转移

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int MAXN = 17, MAXS = 1<<17, MAXM = 250, mod = 1e9+7;

int n, m, flag[MAXS], f[MAXS], mul[MAXM+1], sum[MAXS], in[MAXS];

bool g[MAXN][MAXN];

int main ()

{

	scanf("%d%d", &n, &m);

	for(int x, y, i = 1; i <= m; i++)

		scanf("%d%d", &x, &y), g[x-1][y-1] = true; //邻接表存图

	flag[0] = -1;

	for(int s = 1; s < (1<<n); s++) flag[s] = flag[s>>1] * (s & 1 ? -1 : 1); //求容斥系数 奇数个为1 偶数个为-1

	mul[0] = 1;

	for(int i = 1; i <= m; i++) mul[i] = mul[i-1] * 2 % mod; //预处理2^k

	f[0] = 1;

	for(int i = 0; i < (1<<n)-1; i++)

	{

		for(int k = 0; k < n; k++) in[1<<k] = 0; //计算入度 把k点的入度存在 1<<k上

		for(int j = 0; j < n; j++)

			if(i & (1<<j))

				for(int k = 0; k < n; k++)

					in[1<<k] += g[j][k];

		int t = (1<<n)-1-i; //t为当前状态的补集,即剩下的点

		sum[0] = 0;

		for(int s = (t-1)&t; ; s = (s-1)&t) //枚举本次选取的点对于t的补集

		{

			int now = t ^ s, last = now & -now; //now 是本次选取的点

			sum[now] = sum[now-last] + in[last];

			f[i+now] = ((LL)f[i+now] + (LL)flag[now] * mul[sum[now]] * f[i]) % mod;

			if(!s) break;

		}

	}

	printf("%d\n", (f[(1<<n)-1]+mod)%mod);

}

---

BZOJ 3812 主旋律

• 这道题做法差不多，不过是枚举拓扑序最后的强连通分量来进行转移
  
  详见大佬博客 Miskcoo’s Space

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

const int MAXS = 1<<15;

const int MAXN = 15;

int n, m, Out[MAXS], In[MAXS], mul[MAXN*MAXN];

int f[MAXS], g[MAXS], bitcnt[MAXS], h[MAXS], p[MAXS];

int main () {

	scanf("%d%d", &n, &m);

	for(int i = 0, x, y; i < m; ++i) {

		scanf("%d%d", &x, &y);

		x = 1 << (x-1);

		y = 1 << (y-1);

		Out[x] |= y;

		In[y] |= x;

	}

	mul[0] = 1;

	for(int i = 1; i < n*n; ++i)

		mul[i] = 2ll * mul[i-1] % mod;

	bitcnt[0] = 0;

	for(int i = 1; i < (1<<n); ++i)

		bitcnt[i] = bitcnt[i>>1] + (i&1);

	for(int state = 1; state < (1<<n); ++state) {

		int one = state & -state, Outside = state ^ one;

		for(int i = Outside; i; i = (i-1)&Outside)

			g[state] = (g[state] - 1ll * f[state^i] * g[i] % mod) % mod;

		h[state] = h[Outside] + bitcnt[In[one]&Outside] + bitcnt[Out[one]&Outside];

		f[state] = mul[h[state]];

		for(int sub = state; sub; sub = (sub-1)&state) {

			if(sub != state) {

				int del = (sub^state) & -(sub^state);

				p[sub] = p[sub^del] + bitcnt[Out[del]&sub] - bitcnt[In[del]&(sub^state)];

			}

			else p[sub] = 0;

			f[state] = (f[state] - 1ll * mul[h[state^sub]+p[sub]] * g[sub] % mod) % mod;

		}

		g[state] = (g[state] + f[state]) % mod;

	}

	printf("%d\n", (f[(1<<n)-1]+mod)%mod);

}