Question 1. [省選聯(lián)考 2025] 追憶

給定一張 \(n\) 個點 \(m\) 條邊的 DAG，保證 \([1,2,\cdots, n]\) 為其的一個拓?fù)湫颍约皟蓚€長度為 \(n\) 的全排列 \(A,B\)，執(zhí)行如下操作共 \(q\) 次：

• 1 x y，表示交換 \(A_x,A_y\)。
• 2 x y，表示交換 \(B_x,B_y\)。
• 3 x l r，表示詢問 \(x\) 的所有可達(dá)點 \(y\) 中，滿足 \(A_y\in [l,r]\) 的 \(B_y\) 的最大值。

多測。

\(T\leq 3, n,q\leq 10^5, m\leq 2\times 10^5\)，時限 \(\text{8s}\)。

首先，DAG 上可達(dá)點對就不是什么好做的東西，直接啟發(fā)我們采用 bitset 及平方優(yōu)化。

在 \(\mathcal{O}(\dfrac{nm}{\omega})\) 的復(fù)雜度內(nèi)，求解 DAG 上的可達(dá)點對，接下來按照值域分塊，假設(shè)塊長為 \(B\)，維護(hù) \(A,B\) 在每一個塊中的位置集合的 bitset。

此時 \(1,2\) 操作可以 \(\mathcal{O}(1)\) 解決，重點是解決詢問。

將 \(U\) 初始化為 \(x\) 的可達(dá)點集合，接下來計算 \(A_y\in [l,r]\) 的 \(y\) 的 bitset，記為 \(V_A\)，將 \(A\) 中值域在 \([l,r]\) 內(nèi)散塊暴力改，整塊直接按位或。

隨后，按照從大到小的順序，判斷 \(B\) 的每一塊是否有存在的位置，具體的，設(shè)當(dāng)前 \(B\) 的值域塊的位置集合的 bitset 為 \(V_B\)，求 \(U\cap V_A\cap V_B\) 是否非空即可，確定了大塊之后再暴力確定答案是多少。

在上面的步驟中，單次詢問的時間復(fù)雜度為 \(\mathcal{O}(\dfrac{n^2}{B\omega} + B)\)，平衡塊長取 \(B = \dfrac{n}{\sqrt{\omega}}\)。

最終時間復(fù)雜度為 \(\mathcal{O}(\dfrac{nq}{\sqrt{\omega}})\)，其中 \(\omega = 64\)。

Question 2. [CEOI 2019] Amusement Park

給定一張有向圖 \(G = (V,E)\)，共計 \(n\) 個點 \(m\) 條邊，沒有自環(huán)與重邊（方向相反的也沒有）。

設(shè)一個邊集的子集 \(F\subseteq E\)，翻轉(zhuǎn)邊集 \(F\) 內(nèi)的邊的方向，若操作過后 \(G\) 變?yōu)?DAG 則權(quán)值為 \(|F|\)，否則權(quán)值為 \(0\)。

求權(quán)值的總和，答案對 \(P = 998244353\) 取余。

\(n\leq 18\)

首先，一張 DAG 反向后得到一張 DAG，一張非 DAG 反向后一定不是 DAG，設(shè)給這些邊重定向成 DAG 的方案數(shù)是 \(C\)，則答案為 \(C\times \dfrac{m}{2}\)，根據(jù)前結(jié)論構(gòu)造對應(yīng)易得。

設(shè) \(f_S\) 表示 \(S\) 內(nèi)的點定向成 DAG 的方案數(shù)，那么怎么構(gòu)建轉(zhuǎn)移？在 DAG 上我們經(jīng)常會考慮拓?fù)渑判颍诒?DP 中我們依舊考慮拓?fù)渑判虻乃枷搿D(zhuǎn)移零入度點。

假設(shè)枚舉的零入度點集 \(T\)，那么有 \(T\) 向所有 \(S\setminus T\) 連邊，且 \(S\setminus T\) 為 DAG，同時 \(T\) 是一個獨立集（否則 \(T\) 之間一定存在邊，那么怎么可能全部都是零入度點？），那么有 \(f_S = \underset{T\subset S}{\sum} w(T)f_{S-T}\)，其中 \(w(T)\) 僅當(dāng) \(T\) 為獨立集時取 \(1\)。

但是這樣會算重，具體的，\(T\) 作為最終的零入度點集，其所有子集都會被當(dāng)作零入度點集計算，為了得到正確答案，我們采用容斥：在 \(|T|\) 為奇數(shù)時帶 \(+1\) 的貢獻(xiàn)，偶數(shù)時帶 \(-1\) 的貢獻(xiàn)，可以根據(jù) Venn 圖感性理解其正確性。

取最終 \(f_U\) 為方案數(shù)，根據(jù)結(jié)論乘上對應(yīng)系數(shù)得到最終答案，其中 \(U\) 為點集的全集。

Question 3. [清華集訓(xùn) 2014] 主旋律

給定一張有向圖 \(G = (V,E)\)，無重邊無自環(huán)，共計 \(n\) 個點 \(m\) 條邊，求有多少個邊的子集 \(F\subseteq E\) 滿足 \(G' = (V,F)\) 是強連通的。

答案對 \(P = 10^9 + 7\) 取余。

\(n\leq 15\)

記 \(\text{trans}(A,B)\) 表示起點在 \(A\) 中，終點在 \(B\) 中的邊的數(shù)量，以下使用這個函數(shù)時，（應(yīng)該是）保證了 \(A,B\) 不交。

設(shè) \(f_S\) 表示讓點集 \(S\) 成為強連通圖的方案數(shù)，考慮如何轉(zhuǎn)移 \(f\)。

根據(jù)強連通圖的性質(zhì)，其縮完點后只能得到一個點，枚舉其的一個子集 \(T\)，使得 \(T\) 構(gòu)成了一個強連通分量，且在縮點之后的圖上 \(T\) 的入度為 \(0\)，不對 \(S\setminus T\) 有任何限制。

這樣子會算重，借用前一個問題的容斥方法，我們將 \(T\) 劃分成若干個強連通分量，若有奇數(shù)個則貢獻(xiàn)為 \(+1\)，反之為 \(-1\)，記權(quán)值總和為 \(g_T\)。

那么有 \(f_S = h_S - \underset{T\subseteq S}{\sum} 2^{\text{trans}(T,S\setminus T)} g_T h_{S\setminus T}\)，其中 \(h_S\) 表示點集 \(S\) 能夠?qū)С龅膱D的總數(shù)，設(shè)兩端都在 \(S\) 中的邊的數(shù)量為 \(x\)，則 \(h_S = 2^x\)。

考慮如何計算 \(g_S\)，那么我們欽定其中的一個強連通分量 \(T\)，使得 \(T\) 包含 \(S\) 中編號最小的點，這樣子不會算重，則有 \(g_S = f_S + \underset{T\subset S}{\sum} (-1)f_Tg_{S\setminus T}\)，其中這個 \(-1\) 表示多了一個強連通分量帶來的變化，而 \(f_S\) 表示只有一個強連通分量。

注意到當(dāng) \(T = S\) 的時候 \(f,g\) 之間的互相轉(zhuǎn)移看起來很奇怪，要先不管 \(f_S\) 計算 \(g_S\)，然后計算 \(f_S\)，最后再把 \(f_S\) 加到 \(g_S\) 當(dāng)中。

為了計算 \(\text{trans}(A,B)\)，預(yù)處理出每一個點的出邊，然后枚舉 \(A\) 中點，交 \(B\) 集合求 \(\text{popcount}(A\cap B)\) 后求和即可，時間復(fù)雜度為 \(\mathcal{O}(3^n n)\)。