专栏文章

P11714 [清华集训 2014] 主旋律

GGenius_Star影
P11714题解参与者 10已保存评论 10

文章操作

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

当前评论
10 条
当前快照
1 份
快照标识符
@miq2g05g
此快照首次捕获于
2025/12/03 21:51
3 个月前
此快照最后确认于
2025/12/03 21:51
3 个月前
查看原文
发现现有的一些题解讲的不太详细，不会的还是不会，于是这里写了一篇较为详细的题解。
或许更好的阅读体验。

思路：

不同于 DAG 计数的是，强联通不好刻画，且几乎无法转化为求解为子问题，于是我们考虑用总的方案数减去不合法的方案数。
考虑动态规划，定义 dpSdp_S 表示使得 SS 点集为强联通的子图数量，那么考虑求出不是强连通的子图数量，那么必然可以划分为若干个 SCC，且这些 SCC 缩点后必然是一个 DAG。
注意到上述性质后，按照 DAG 计数的 trick，我们枚举一个子集 TT 表示缩点后入度为 00 的点在原图上的点的并集，即这些点构成了若干组两两无边的 SCC；然后设 fSf_S 表示将 SS 划分为若干组两两无边的 SCC 的方案数。
然后考虑对于一个缩点后的 DAG，设其有 cntcnt 个入度为 00 的点 a1,⋯ ,acnta_1, \cdots, a_{cnt}，那么肯定会算重，令集合 AiA_i 表示使得 aia_i 入度为 00 的方案数，我们要算 ∣A1∪⋯∪Acnt∣|A_1 \cup \cdots \cup A_{cnt}|，直接容斥即可，对于钦定某 ii 个是 SCC 的容斥系数为 (−1)i+1(-1)^{i + 1}。
上面的推导，我们算出来的容斥系数是和我们划分出来的 SCC 的个数有关，例如对于点集 ∣T∣|T| 来说，若划分为了 ii 个 SCC，则其容斥系数是 (−1)i+1(-1)^{i + 1} 而不是和 TT 相关的；所以不能直接使用 fTf_T 来更新转移。
考虑重新修改定义，令 gTg_T 表示划分为奇数个 SCC 的方案数减去划分为偶数个 SCC 的方案数，那么 gTg_T 就已经包含了容斥系数了。
然后考虑求若钦定了 TT 这个点集为这些入度为 00 的 SCC 的并集后，符合上述钦定的子图数有多少个；首先对于 S−TS - T 内的边，随意删，没有影响，然后对于 u∈T,v∈(S−T)u \in T, v \in (S - T) 的有向边 u→vu \to v，也是随意删的。
其它的边都是有限制条件的，例如 u∈(S−T),v∈Tu \in (S - T), v \in T 的边 u→vu \to v 必须删掉（不然入度不可能为 00），对于 u,v∈Tu, v \in T 内部的边，有内部必须构成若干个两两无边的 SCC 的限制。
然后我们这里定义 ESE_S 表示 SS 的导出子图的边数，E(S,T)E(S, T) 表示 u∈S,v∈Tu \in S, v \in T 的有向边 u→vu \to v 的条数，那么我们有状态转移方程：
dpS=2ES−∑T⊂SgT2ES−T+E(T,S−T)dp_S = 2^{E_S} - \sum_{T \subset S} g_T 2^{E_{S - T} + E(T, S - T)}
但是这里面我们还少了一点，即钦定 SS 这个点集划分为 >1>1 个 SCC 的方案数，可以看下面 gSg_S 的转移部分，这里的方案数就是后面的那一坨。
然后来考虑 gSg_S 的转移，首先有 SS 整个划分为一个 SCC，方案数是 dpSdp_S，然后我们枚举一个子集 TT，将 TT 作为一个新加入的 SCC 进行转移：
gS=dpS−∑T⊂SdpTgS−Tg_S = dp_S - \sum_{T \subset S} dp_T g_{S - T}
因为多了 TT 这一个 SCC，所以是负号。
看起来很对，但是这样会算重，因为我们考虑若有一个合法的 cntcnt 个 SCC，那么 TT 肯定遍历了这 cntcnt 个中的任意一个，然后 gS−Tg_{S - T} 肯定也包含这个方案，故算重了 cntcnt 次。
于是考虑钦定我们新加入的 SCC 是包含了 xx 的，即 x∈S,x∈Tx \in S, x\in T，此时对于上面那个合法的方案，包含 xx 的 SCC 肯定只有一个，只能被 TT 所枚举到一次，故不会算重活算漏。
这里可以令 x=lowbit⁡(S)x = \operatorname{lowbit}(S)，然后我们修改状态转移方程：
gS=dpS−∑T⊂S&lowbit⁡(S)=lowbit⁡(T)dpTgS−Tg_S = dp_S - \sum_{T \subset S \& \operatorname{lowbit}(S) = \operatorname{lowbit}(T)} dp_T g_{S - T}
此时我们按照上面的转移就是 O(3nn2)O(3^nn^2) 的，显然是过不去的，瓶颈在于计算 E(T,S−T)E(T, S - T)。
考虑令 FS=E(S,U−S)F_S = E(S, U - S)，其中 UU 为全集，那么我们有：
FT=E(T,U−T)=E(T,S−T)+E(T,U−S)F_T = E(T, U - T) = E(T, S - T) + E(T, U - S)
FS=E(S,U−S)=E(S−T,U−S)+E(T,U−S)F_S = E(S, U - S) = E(S - T, U - S) + E(T, U - S)
两式子作差，我们有：
E(T,S−T)=FT−FS+E(S−T,U−S)E(T, S - T) = F_T - F_S + E(S - T, U - S)
我们令 cntS,icnt_{S, i} 表示 E({i},U−S)E(\{i\}, U - S)，那么：
E(T,S−T)=FT−FS+∑i∈(S−T)cntS,iE(T, S - T) = F_T - F_S + \sum_{i \in (S - T)} cnt_{S, i}
注意到 FS,cntS,iF_S, cnt_{S, i} 可以 O(m2n)O(m2^n) 预处理，故我们就得到了 O(3nn)O(3^nn) 的做法，可以通过。
link

完整代码：

CPP
#include<bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 16, M = 1 << N, MN = 205, mod = 1e9 + 7; 
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
int n, m, u, v;
int dp[M], g[M], poww[MN], F[M], G[M], cnt[M][N];
vector<int> E[N];
inline void add(int u, int v){
	E[u].push_back(v);
}
inline int calc(int T, int S){
	int sum = F[T] - F[S];
	for(int i = 1; i <= n; ++i)
	  if(((S - T) >> (i - 1)) & 1)
	    sum += cnt[S][i];
	return sum;
}
bool End;
int main(){
	poww[0] = 1;
	n = read(), m = read();
	for(int i = 1; i <= m; ++i){
		poww[i] = 2ll * poww[i - 1] % mod;
		u = read(), v = read();
		add(u, v);
	}
	for(int S = 1; S < (1 << n); ++ S){
		for(int u = 1; u <= n; ++u){
			if((S >> (u - 1)) & 1){
				for(auto v : E[u]){
					if((S >> (v - 1)) & 1){
						++G[S];
						continue;
					}
					++cnt[S][u];
				}
				F[S] += cnt[S][u];
			}
		}
		for(int T = (S - 1) & S; T; T = (T - 1) & S){
			if(lowbit(S) != lowbit(T))
			  continue;
			g[S] = (g[S] - 1ll * dp[T] * g[S - T] % mod + mod) % mod;
		}
		dp[S] = poww[G[S]];
		for(int T = S; T; T = (T - 1) & S)
		  dp[S] = (dp[S] - 1ll * g[T] * poww[G[S - T] + calc(T, S)] % mod + mod) % mod;
		g[S] = (g[S] + dp[S]) % mod;
	}
	write(dp[(1 << n) - 1]);
	cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
	return 0;
}

评论

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

正在加载评论...