總結
容斥
P6846
首先發現將一張 DAG 的邊全部反向，仍然是一張 DAG。並且這兩種改邊總和是 \(m\)。所以答案就是 \(m\)
考慮一個 DAG 的特徵，考慮剖成若干層入度為 \(0\)。這啓發我們考慮一種計數，設 \(f_{S}\) 表示 \(S\)
\[f_S=\sum_{T\subset S,T\ne \varnothing}f_{S\setminus T}2^{E_{T\to S\setminus T}}[T\text{ is an IS}] \]
發現這樣顯然會算重，因為可能 \(S\setminus T\) 還有 \(0\) 入度點，所以設 \(F(A)\) 表示欽定 \(A\) 是獨立集的算出來的係數即 \(f_{S\setminus A}2^{E_{A\to S\setminus A}}\)，\(G(A)\) 表示獨立集恰好是 \(A\)
\[\begin{aligned} F(A)&=\sum_{A\subset B}G(B)\\ G(A)&=\sum_{A\subset B}(-1)^{|B|-|A|}F(B)\\ f_S&=\sum_{T\subset S,T\ne\varnothing}G(T)\\ &=\sum_{T\subset S,T\ne \varnothing}\sum_{T\subset A\subset S}(-1)^{|A|-|T|}F(A)\\ &=\sum_{A\subset S}F(A)(-1)^{|A|}\sum_{T\subset A,T\ne \varnothing}(-1)^{|T|}\\ &=\sum_{A\subset S}F(A)(-1)^{|A|+1} \end{aligned} \]
相當於只需在原本的式子上乘上一個 \((-1)^{|T|+1}\) 的係數。或者直觀理解就是容斥原理。\(A\cup B=A+B-A\cap B\)。所以時間複雜度 \(O(3^n)\)。
A
首先如果原圖不是一個 SCC，那麼縮點之後就是一個 DAG。所以這個題跟上一題有很大的相似之處。
設 \(f_{S}\) 表示 \(S\) 不是強聯通的方案數，相當於就是縮點後是 DAG。那麼跟上題一樣，枚舉一個集合，由於你不知道它縮點後有幾個獨立集，所以再設 \(g_{S,i}\) 表示 \(S\) 縮點後是 \(i\)
\[f_S=\sum_{T\subset S,T\ne \varnothing}\sum_{i=1}^{|T|}g_{T,i}2^{E_{S\setminus T}+E_{T\to S\setminus T}}(-1)^{i+1} \]
其中 \(2^{E\setminus T}\) 是因為這個集合裏的邊是可以亂連不用保證是一個 DAG 的，因為 \(S\)
然後這個轉移是有點問題的，當 \(T=S\) 時會多算 \(g_{T,1}\)，而這個相當於 \(S\) 是一個 SCC 了，所以不能算上。並且 \(g_{S,1}=2^{E_S}-f_S\)，需要算出 \(f_S\) 才能求出，所以避免了自轉移的情況。\(g_{S,i\ge 2}\)
然後時間複雜度就是 \(O(3^nn)\) 了，但是注意到可以直接將 \((-1)^{i+1}\) 係數記進 \(g_{T}\)，於是就做完了。
\[f_S=\sum_{T\subset S,T\ne \varnothing}g_{T}2^{E_{S\setminus T}+E_{T\to S\setminus T}}\\ g_S=2^{E_S}-f_S\ {\color{red}-}\sum_{T\subset S,\text{lowbit}(T)=\text{lowbit}(S),T\ne S}(2^{E_T}-f_T)g_{S\setminus T} \]
\(\color{red}-\) 是 \(-1\)
E
答案顯然不會超過 \(n\)。考慮怎麼用操作二節省次數。容易發現一定是若干集合 \(S\) 使用 \(|S|-1\) 次操作二變成全 \(0\)，因為如果 \(\ge |S|\) 不如全用操作 \(1\)，\(<|S|-1\) 一定可以繼續拆。然後剩下的數使用操作一變成 \(0\)。
為了讓答案最小，即讓這樣的 \(S\) 最多。考慮將操作二的兩個數連邊以刻畫操作，那麼根據上面的結論一定是 \(S\) 是樹時最優。先考慮怎樣的 \(S\)
先考慮弱化問題，每次選兩個數 \(-x\)，隨便欽定一個點作為樹的根，那麼考慮剝葉子，只需要最終根的權值為 \(0\) 即可。發現奇數層的對根的貢獻為 \(+\)，偶數層的貢獻為 \(-\)，於是奇數層的權值和與偶數層的權值和相等是 \(S\) 合法的充要條件。進一步，這個等價於找到一個子集 \(T\)，使得 \(T\) 的權值和等於 \(S\setminus T\)
現在變成一個 \(-x\) 一個 \(-x-1\)。相當於在剛剛基礎上，再執行 \(|S-1|\) 次操作，每次讓奇數層或者偶數層的權值 \(+1\)，然後最終權值和相等。形式化的就是找到子集 \(T\) 使得 \(|s(T)-s(S\setminus T)|\le |S|-1\) 並且 \(|s(T)-s(S\setminus T)|\equiv |S|-1\pmod 2\)，因為更改一次操作差就會變化 \(2\)。也即 \(s(S)\equiv |S|-1\pmod 2\)。
那麼判合法時間複雜度就是 \(2^{|S|}\)，對於所有 \(S\) 判就是 \(3^n\)，常數有點大考慮優化。比較經典的就是折半，將兩邊排序後就可以雙指針掃一遍了，問題在於排序，是 \(O(\sqrt 2^{|S|}|S|)\) 的，然後發現考慮每次往集合加入一個數，是可以歸併排序的，所以就去掉了 \(|S|\)，總時間複雜度就是 \(\displaystyle\sum_{i=0}^{n}\binom{n}{i}\sqrt 2^i=(\sqrt 2+1)^n\)。
然後就基本上做完了，直接做一遍 \((\max,+)\) 子集卷積就可以算出最多 \(S\) 的數量，是一個常數小的 \(3^n\)，所以就能通過了。當然也可以倍增+子集卷積做到 \(O(2^nn^2\log n)\)，意義不大。
技巧：
- 子集折半。
- 二元組考慮建圖。
- 奇偶分層。
C
首先答案顯然是不會超過值域的。然後分析一下，如果確定了迴應觀眾的集合，那麼最優策略肯定是，選擇當前 \(B\) 中 \(\le a_i\) 的最大數替換成 \(a_i\)，如果不存在就新加一個元素。或者也可以將原問題用 Dilworth 變成劃分最少的不降子序列。
發現 \(B\) 中元素一定是互不相同的。於是便能設計出一個 dp，\(f_{S,i}\) 表示當前 \(B\) 元素組成集合為 \(S\)，考慮前 \(i\) 個並欽定第 \(i\) 個觀眾迴應是否可行，於是便能做到 \(O(2^Vn)\)。
\(f_{S,i}\) 值域只有 \(0,1\)，所以考慮交換狀態和值域，事實上最終答案只關心有哪些 \(f_{S,n/n-1}=1\)，所以只需要關注 \(S\) 能到最遠的 \(i\)。即設 \(g_{S}=\max\limits_{f_{S,i}=1}i\)。
然後發現轉移有自環，即如果當前 \(g_S=p\)，如果 \(a_{p+1}\in S\)，那麼可以繼續拓展；否則如果 \(a_{p+2}\in S\)，也是可以繼續拓展的。因為新到的 \(S'\) 是等於 \(S\) 的。所以只需找到最小的 \(a_i,a_{i+1}\not \in S\) 的 \(i\)，可以通過一些方法做到 \(O(2^VV^2+nV)\)，但這不是重點。
F
考慮對於一個選取的集合 \(S\)，假設能讓只選 \(S\) 合法的最大長度是 \(f_S\)，那麼顯然其合法的長度就是 \(\left[\sum_{i\in S}a_i,f_S\right]\) 這個區間，可以通過調整得到。於是只要求出 \(f_S\)，便能求出答案。
相當於有一個集合 \(T\) 不能選，如果我們直接設狀態 \(f_S\) 表示選取的數是 \(S\)，不能選的是 \(\complement_U S\)，發現假設當前要選 \(i\in S\)，相當於 \(S\) 就被分成了兩個部分，即放 \(i\) 左邊的 \(S_1\) 和右邊的 \(S_2\)。發現 \(S_1\) 在選的過程中只是要求不能選 \(\complement_U S\) 而非 \(\complement_U S_1\)，所以這個做法就有問題。
所以就要記 \(f_{i,S,T}\) 表示要選 \(S\) 裏的數，不能選 \(T\) 裏的數所佔據的最長長度，當前考慮的數是 \(a_i\)，分情況考慮一下
- \(i\in T\)，那麼 \(f_{i,S,T}=\min(a_i-\epsilon,f_{i+1,S,T})\)，這是因為 \(i\) 要先放，如果長度 \(\ge a_i\)
- \(i\in S\)，那麼 \(f_{i,S,T}=a_i+\displaystyle\max_{S_1\cup S_2=S\setminus \{i\}}\left\{f_{i+1,S_1,T}+f_{i+1,S_2,T}\right\}\)。
- 否則不用管，\(f_{i,S,T}=f_{i+1,S,T}\)。
考慮 \(\epsilon\) 的問題，注意到最後答案一定是一個左閉右開區間，所以不需要管，最後讓 \(f_S>m\)
