专栏文章

P11834 题解

DDaiRuiChen007
P11834题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mimz361i
此快照首次捕获于
2025/12/01 17:54
3 个月前
此快照最后确认于
2025/12/01 17:54
3 个月前
查看原文
Problem Link
首先 w=1w=1 考虑的部分，要求缩点后的 DAG 只有一个入度为 00 的 SCC。
回顾一下经典的主旋律容斥，我们加入一层入度为 00 的点 TT 系数为 (−1)∣T∣−1wT(-1)^{|T|-1}w_T。
考虑对真实的入度为 00 的点集 SS 做容斥，此时 wTw_T 表示 T⊆ST\subseteq S 的贡献和，则容斥得到 ∑S≠∅∑S⊆T(−1)∣T∣−∣S∣wT=∑(−1)∣T∣−1wT\sum_{S\ne\varnothing}\sum_{S\subseteq T} (-1)^{|T|-|S|} w_T=\sum (-1)^{|T|-1}w_T。
那么我们主旋律容斥算出 SS 形成 SCC 的方案数，SS 中划分出奇数或偶数个 SCC 的方案数，以及 SS 中点连成 DAG 的方案数。
然后计算答案的时候枚举根所在的 SCC，同样用主旋律容斥计算出无入度点集恰好为该 SCC 的 DAG 数量，可以做到 O(3n)\mathcal O(3^n)。
加上 ww 的限制，那么每次我们会把上一层得到的若干连通块之间连上边。
考虑如何记录状态，我们要对同时状压选出哪些连通块，以及连通块内部的一定信息。
首先上一层的每个连通块都要有外向生成树，那么我们在当前层处理时记录考虑到的连通块的集合，以及其中的每个连通块的根集合，这样的状态数依旧是 O(2n)\mathcal O(2^n) 的，转移类似，复杂度可以接受。
注意要特殊处理形态不改变的连通块。
时间复杂度 O(n22n+3n)\mathcal O(n^22^n+3^n)。
代码：
CPP
#include<bits/stdc++.h>
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
const int MOD=1e9+7,i2=(MOD+1)/2;
int n,m,ct[1<<15],dp[1<<15],f[1<<15],g[1<<15][2],h[1<<15],pw[255],ipw[255];
int E(int s,int t) { return ct[s|t]-ct[s-(s&t)]-ct[t]+2*ct[s&t]; }
vector <array<int,2>> G[255];
int dsu[15],bl[15],st[1<<15],in[1<<15],pr[1<<15],sum[1<<15];
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
void solve() {
	cin>>n>>m,clr(h);
	for(int i=1;i<=m;++i) G[i].clear();
	for(int i=1,u,v,w;i<=m;++i) cin>>u>>v>>w,G[w].push_back({u-1,v-1});
	for(int i=0;i<n;++i) dsu[i]=i,h[1<<i]=1;
	for(int w=1;w<=m;++w) {
		clr(st),clr(ct);
		for(int i=0;i<n;++i) bl[i]=find(i),st[1<<bl[i]]|=1<<i;
		for(int s=0;s<(1<<n);++s) st[s]=st[s&-s]|st[s&(s-1)];
		for(auto e:G[w]) {
			for(int s=0;s<(1<<n);++s) if((s>>e[0]&1)&&(s>>e[1]&1)) ++ct[s];
			if(find(e[0])!=find(e[1])) dsu[find(e[0])]=find(e[1]);
		}
		for(int rt=0;rt<n;++rt) if(dsu[rt]==rt) {
			int U=0;
			for(int i=0;i<n;++i) if(bl[i]==i&&find(i)==rt) U|=st[1<<i];
			if(U==st[1<<rt]) {
				for(int s=1;s<(1<<n);++s) if((s&U)==s) h[s]=1ll*h[s]*pw[E(U,U)]%MOD;
				continue;
			}
			clr(dp),clr(f),clr(g),clr(in),clr(pr),clr(sum);
			for(int s=0;s<(1<<n);++s) if((s&U)==s) {
				for(int i=0;i<n;++i) if(s>>i&1) in[s]|=1<<bl[i];
			}
			dp[0]=f[0]=g[0][0]=1;
			for(int s=1;s<(1<<n);++s) if((s&U)==s) {
				int S=in[s];
				for(int T=S,t;T;T=(T-1)&S) if(T&(S&-S)) {
					t=s&st[in[T]];
					g[s][0]=(g[s][0]+1ll*f[t]*g[s^t][1])%MOD;
					g[s][1]=(g[s][1]+1ll*f[t]*g[s^t][0])%MOD;
				}
				f[s]=pw[E(st[S],s)];
				for(int T=S,t;T;T=(T-1)&S) {
					t=s&st[T];
					f[s]=(f[s]+1ll*(g[t][0]+MOD-g[t][1])*pw[E(st[S],s^t)])%MOD;
				}
				g[s][1]=(g[s][1]+f[s])%MOD;
				for(int T=S,t;T;T=(T-1)&S) {
					t=s&st[T];
					dp[s]=(dp[s]+1ll*(g[t][1]+MOD-g[t][0])*pw[E(st[T],s^t)]%MOD*dp[s^t])%MOD;
				}
		 	}
		 	for(int s=0,S;s<(1<<n);++s) if((s&U)==s) {
		 		S=in[s],pr[s]=1;
		 		for(int i=0;i<n;++i) if(S>>i&1) pr[s]=1ll*pr[s]*h[s&st[1<<i]]%MOD;
		 		sum[S]=(sum[S]+1ll*pr[s]*dp[s]%MOD*pw[E(U^st[S],s)+E(U,st[S]^s)])%MOD;
			}
		 	for(int s=1;s<(1<<n);++s) if((s&U)==s) {
		 		h[s]=0;
		  		for(int o=U^st[in[s]],t=o;;t=(t-1)&o) {
		 			h[s]=(h[s]+1ll*pr[s|t]*(g[t][0]+MOD-g[t][1])%MOD*sum[in[U]^in[s|t]]%MOD*pw[E(U,st[in[s|t]]^s^t)])%MOD;
		 			if(!t) break;
				}
				h[s]=1ll*h[s]*f[s]%MOD;
			}
		}
	}
	int ans=0;
	for(int s=1;s<(1<<n);++s) ans=(ans+h[s])%MOD;
	cout<<1ll*ans*ipw[2*m]%MOD<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	for(int i=pw[0]=ipw[0]=1;i<255;++i) pw[i]=pw[i-1]*2%MOD,ipw[i]=1ll*ipw[i-1]*i2%MOD;
	int ty,_; cin>>ty>>_;
	while(_--) solve();
	return 0;
}

评论

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

正在加载评论...