2 条题解

  • 0
    @ 2026-5-12 0:29:49

    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 的贡献和，则容斥得到 $\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)。

    代码：

    #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
      @ 2025-10-8 17:01:08

      day2t2题解

      #include <bits/stdc++.h>
using namespace std;

const int _ = 20, __ = 1 << 16 | 1, P = 1e9 + 7, iv2 = (P + 1) / 2;
int pwiv2[__], lg2[__], ppc[__], n, m, T, nxt[_], revnxt[_], scc[__], out[__];

#define pii pair<int, int>
vector<pii> edgepot[__];

int fa[_], val[_][__], bel[_]; vector<int> rts[_];
int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); }

int curbel[_];
struct qcut_calculator {
    int prevu, prevs, ans, prevall, prevtot;
    int qry(int u, int s) {
        // s to u^s
        if (prevu != u) {
            prevu = u; prevs = prevtot = ans = prevall = 0;
            for (int i = 0; i < n; ++i) if (u >> i & 1) prevall |= curbel[i];
        }
        while (prevs != s) {
            int x = lg2[s ^ prevs], cur = curbel[x], flg = prevs >> x & 1 ? 1 : -1;
            while (cur) {
                int t = lg2[cur]; cur ^= 1 << t; prevtot ^= 1 << t;
                ans += (ppc[revnxt[t] & prevtot] - ppc[nxt[t] & (prevall ^ prevtot)]) * flg;
            }
            prevs ^= (1 << x);
        }
        return pwiv2[ans];
    }
    void clear() { prevu = prevs = ans = 0; }
} qcut1, qcut2;

void calcscc(int sz) {
    qcut1.clear(); qcut2.clear();
    static int g[__];
    for (int i = 1; i < 1 << sz; ++i) {
        scc[i] = 1; g[i] = 0; int hb = lg2[i], x = i;
        while ((x = i & (x - 1))) {
            scc[i] = (scc[i] - 1ll * g[x] * qcut1.qry(i, x)) % P;
            if (x >> hb & 1)
                g[i] = (g[i] - 1ll * g[i ^ x] * scc[x] % P * qcut1.qry(i, x) % P * qcut2.qry(i, i ^ x)) % P;
        }
        scc[i] = (scc[i] - g[i]) % P; g[i] = (g[i] + scc[i]) % P;
    }
}
void calcout(int sz) {
    static int f[__]; memset(f, 0, sizeof(int) * (1 << sz)); f[(1 << sz) - 1] = 1;
    for (int i = (1 << sz) - 1; i; --i) {
        int x = i;
        while ((x = (x - 1) & i))
            f[x] = (f[x] - 1ll * f[i] * qcut1.qry(i, x)) % P;
    }
    for (int i = 0; i < sz; ++i)
        for (int j = 0; j < 1 << sz; ++j)
            if (j >> i & 1) f[j ^ (1 << i)] = (f[j ^ (1 << i)] + f[j]) % P;
    for (int j = 1; j < 1 << sz; ++j)
        out[j] = 1ll * f[j] * qcut2.qry((1 << sz) - 1, (1 << sz) - 1 - j) % P;
}

int ans[__], choice[_];
void dfs(vector<int>& rts, vector<pii>& useful_edges, int id, int totbel, int prob) {
    if (id == rts.size()) {
        memset(nxt, 0, sizeof(nxt)); memset(revnxt, 0, sizeof(revnxt));
        for (auto e : useful_edges) {
            if (totbel >> e.first & 1) { nxt[e.second] |= 1 << e.first; revnxt[e.first] |= 1 << e.second; }
            if (totbel >> e.second & 1) { nxt[e.first] |= 1 << e.second; revnxt[e.second] |= 1 << e.first; }
        }
        for (int i = 0; i < rts.size(); ++i) curbel[i] = bel[rts[i]];
        calcscc(rts.size()); calcout(rts.size());
        for (int i = 1; i < 1 << rts.size(); ++i) {
            int res = 0; for (int j = 0; j < rts.size(); ++j) if (i >> j & 1) res |= choice[j];
            ans[res] = (ans[res] + 1ll * prob * scc[i] % P * out[i]) % P;
        }
        return;
    }
    choice[id] = bel[rts[id]];
    while (choice[id]) {
        dfs(rts, useful_edges, id + 1, totbel | choice[id], 1ll * prob * val[rts[id]][choice[id]] % P);
        choice[id] = bel[rts[id]] & (choice[id] - 1);
    }
}

int main() {
    freopen("years.in", "r", stdin);
    freopen("years.out", "w", stdout);
    pwiv2[0] = 1; for (int i = 1; i <= 1000; ++i) pwiv2[i] = 1ll * pwiv2[i - 1] * iv2 % P;
    lg2[0] = -1; for (int i = 1; i < __; ++i) { lg2[i] = lg2[i >> 1] + 1; ppc[i] = ppc[i >> 1] + (i & 1); }
    for (cin >> T >> T; T; --T) {
        cin >> n >> m; for (int i = 1; i <= m; ++i) edgepot[i].clear();
        for (int i = 1; i <= m; ++i) {
            int x, y, w; cin >> x >> y >> w;
            edgepot[w].push_back(pii(x - 1, y - 1));
        }
        memset(val, 0, sizeof(val));
        for (int i = 0; i < n; ++i) { fa[i] = i; rts[i] = {i}; bel[i] = 1 << i; val[i][1 << i] = 1; }
        for (int i = 1; i <= m; ++i) {
            vector<pii> useful_edges;
            for (auto t : edgepot[i])
                if (find(t.first) != find(t.second)) useful_edges.push_back(t);
            for (auto t : edgepot[i])
                if (find(t.first) != find(t.second)) {
                    int x = find(t.first), y = find(t.second);
                    rts[y].insert(rts[y].end(), rts[x].begin(), rts[x].end());
                    fa[x] = y; rts[x] = {x};
                }
            for (int j = 0; j < n; ++j)
                if (rts[j].size() != 1) {
                    int allbel = 0; for (auto t : rts[j]) allbel |= bel[t];
                    memset(ans, 0, sizeof(ans));
                    dfs(rts[j], useful_edges, 0, 0, 1);
                    memcpy(val[j], ans, sizeof(ans));
                    rts[j] = {j}; bel[j] = allbel;
                }
        }
        int sum = 0; for (int i = 1; i < 1 << n; ++i) sum = (sum + val[find(0)][i]) % P;
        cout << (sum + P) % P << endl;
    }
    return 0;
}
      • 1

      [省选联考 2025] 岁月

      信息

      ID
      2349
      时间
      3000ms
      内存
      512MiB
      难度
      10
      标签
      递交数
      1
      已通过
      1
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 6ms
      4. Powered by Hydro v5.0.1 Community