做題筆記10

傻逼濱蘭實驗學校

7.14

P5354 [Ynoi Easy Round 2017] 由乃的 OJ

這不是我們 I_PC_02_杭_站嗎

把每一個操作看成一個映射，這些映射構成一個幺半群，直接樹剖線段樹可以輕松做到 \(\mathcal{O}(n\log ^2 \log V)\)

這個映射復合大概就是 h(x)=(f(x)&g(1))|(~f(x)&g(0))，發現我們可以把所有位壓在一起處理，這樣復雜度就是 \(\mathcal{O}(n\log^2 n)\)，可以用一些靜態/動態樹上數據結構做到 \(\mathcal{O}(n\log n)\)

P7897 [Ynoi2006] spxmcq

首先把所有詢問按 \(x\) 排序，這樣就變成了每次加的權非負，考慮直接 dp，會有轉移 \(f_u=\sum\limits_{v}\max(f_v,0)\)，我們把能夠轉移到的邊在樹上連一條實邊，其他的連一條虛邊，發現當加權變大時，只會使得若干條虛邊變成實邊，那我們可以用一個小根堆維護出來每條邊什么時候變成實邊

具體的，若 \(u\) 向 \(u\) 的父親合并，則需要滿足 \(sum_u+siz_u\times x\ge 0\)，其中 \(sum_u\) 是 \(u\) 所在連通塊的權值和，也就是說，當 \(x\ge \left\lceil\frac{-sum_u}{siz_u}\right\rceil\) 的時候，會將 \(u\) 合并上去，由于我們查詢的時候不一定是連通塊的根，所以要開一個數據結構記錄子樹的權值，而每次合并會使一段鏈的權值加上某個數，所以要做的就是鏈加單點查詢，直接樹狀數組維護即可

總復雜度 \(\mathcal{O}(n\log n)\)

P6779 [Ynoi2009] rla1rmdq

分塊。

對于每一塊分別做，把一塊中的關鍵點取出來，當這個塊中的所有點都向上跳的時候，如果某一個點跳到了之前跳到的位置，那么這個點在之后的全局修改都是沒用的，而我們只需要維護那些有用的點，直接暴力跳即可，這樣最多會遍歷整棵樹一遍

修改散塊，可能會使得一些之前別扔掉的點復活，我們遍歷 \([l,r]\) 中的所有點，假如現在要跳 \(k\) 步，如果這個點的 \(k\) 級祖先沒被遍歷過，那么他可以變成一個有用的點，直接維護即可

查詢的話，整塊直接維護一個全局答案，散塊暴力查詢即可

容易做到 \(\mathcal{O}(n^{1.5})\)

CF1172E Nauuo and ODT/P5526 [Ynoi2012] 驚惶的 SCOI2016

我操，這題太壞了

對每個顏色分別考慮，發現所有不經過這個顏色的點的路徑都沒有這個點的貢獻，那么如果我們把當前顏色標成黑色，其余的標稱白色，那就只需要求出來所有白色點的連通塊大小平方的和了

考慮添加一個黑色點，我們需要知道其原來所在連通快的大小，其所有兒子的連通塊大小的平方和，考慮重剖，只需要維護所有輕兒子的連通塊大小的平方和即可，因為我們每次只會做一些鏈加查單點，那我們只需要用樹狀數組維護出來每個點所在連通塊的大小 \(s\) 即可

容易做到 \(\mathcal{O}(n\log^2n)\)，可以用一些別的手法做到單 \(\log\)，比如用 std::set<int> 維護所有重鏈，并用一個數組維護所有重鏈上深度最小的黑點，這樣只需要查一次前驅后繼

7.15

模擬賽

T1

考慮拓撲序，不經過每個點的路徑肯定是拓撲序前面的一個點后拓撲序后面的一個點連邊，直接做就完了

T2

暴力重構。

T3

發現 sg 值只有 \(\mathcal{O}(\log n)\)，同時容易說明 \(\max sg=k\) 的點的數量級是 \(\frac{n}{2^k}\) 的，直接做就是 \(\mathcal{O}(n\log^2n)\)

7.17

模擬賽

放 T1T2 這種毫無意義的題，全家四萬了

T1

線段樹分治。

T2

wqs 二分。

T3

有點有點

首先考慮計數一個路徑組，每次可以選擇兩個點走一步，從 \(a_i\) 走到 \(b_i\)，但是可以存在兩個位置的值相同的方案數，記這個東西為 \(P(a_1\rightarrow b_1,a_2\rightarrow b_2,a_3\rightarrow b_3)\)，我們先令 \(d_i=b_i-a_i,t=\frac{\sum\limits \left(b_i-a_i\right)}{2}\)，這樣我們一共會選擇 \(t\) 對 \((i,j)\) 并使 \(a_i\leftarrow a_i+1,a_j\leftarrow a_j+1\)，那么問題就是，現在有 \(t\) 個大小為 \(2\) 的盒子，有 \(n\) 種數，每次可以選擇兩個不同的數放進去，這樣的方案數再除以 \(2^t\)，就是最后的答案，于是考慮容斥，我們枚舉 \(x_i\) 表示第 \(i\) 種數放在同一個盒子的方案數，可以得到方案數就是

\[ \sum\limits_{x_i\le \frac{d_i}{2}} (-1) \binom{t}{x_1,x_2,x_3,...}\binom{2(t-s)}{d_1-2x_1,d_2-2x_2,d_3-2x_3,...} \]

其中 \(s=\sum\limits x_i\)

發現這個方案只和每一個 \(x\) 的貢獻，以及他們的和 \(s\)，的貢獻有關，那我們可以直接構造多項式 \(F_w0obha2h00(x)=\sum\limits_{i=0}(-1)^{i}\frac{1}{i!(d-2i)!}x^i\)，那么答案就是 \(\prod\limits F_{b_i-a_i}\) 的每一項上系數的一個線性組合

而對于原問題，要求不交路徑，這里有結論，不交路徑組的方案等于

\[ \sum\limits_{\sigma}\text{sgn}(\sigma) P(a_1\rightarrow \sigma_1,a_2\rightarrow \sigma_2,...) \]

其中 \(\sigma\) 是 \(1\sim n\) 的一個排列，證明的話，考慮 LGV 的證明過程，即我們可以選擇兩個相交的路徑交換其編號，這樣可以構造一個雙射，使得所有的相交路徑的貢獻之和為 \(0\)

展開上面的式子，就是

\[ \sum\limits_{\sigma}\text{sgn}(\sigma) \prod F_{b_{\sigma_i}-a_i} \]

處理出 \(\hat F_d=DFT(F_d)\)，那答案多項式就是 \(Ans=IDFT\left(\sum\limits_i\left|[x^i]\hat F_{b_k-a_j} \right| \right)\)，最終復雜度為 \(\mathcal{O}(n^4V+nV^2\log\left( nV\right))\)

P4115 Qtree4

靜態toptree直接維護，只卡到了第二優解

7.18

P13273 [NOI2025] 數字樹

有一個很顯然的 \(n^2\)，我們可以給每一個節點維護一個 \(01\) 變量 \(x_i\)，表示 dfs 到 \(i\) 這個節點后是往左子樹還是右子樹走，那么我們考慮每兩個加入的葉子對 \(a_i,b_i\) 和 \(a_j,b_j\)，我們只需要滿足 dfs 序對于每一對 \((i,j)\) 都不違反限制就是合法的，對于一對 \((i,j)\)，我們不難發現其限制只需要拉出其對應的虛樹，假如這個虛樹上的 \(lca\) 中 \(dep\) 比較小的兩個點分別為 \(u,v\)，那么限制條件就形如 \(x_u=A\Leftrightarrow x_v=B\)，那么我們只需要知道每次操作完剩下的自由元的個數即可

接著考慮上述限制，我們定義 \(S(u)\) 為 \(u\) 子樹內出現且僅出現了一次的葉子節點的顏色數，我們認為 \(S\) 相同的節點是等價的，因為你會發現，同一個等價類中只有最下面的兩個或一個點是起到了約束作用的，因為只有這些點的兒子會分叉，也就是說只有這些點可能會最后在每一對虛樹上，作為 \(lca\) 出現，那也就可以說，每一個等價類中，有且僅有一個點是不自由的，那每一個等價類的貢獻就是 \(2^{size-1}\)，如果等價類的數量為 \(cnt\)，那么插入了 \(i\) 對葉子的總答案就是 \(2^{2n-cnt+i}\)（這個證明太不嚴謹了，官方題解據說是每個等價類只會翻轉偶數個位置，這里的翻轉指的是把子樹內所有節點的左右兒子交換，還是可以考慮每個等價類中最深的那幾個點，其左右子樹是分叉的，那么如果翻轉了奇數個兒子，肯定會使得方案不合法，于是就是 \(\sum\limits_{i=0}^n[2|i]\binom{n}{i}=2^{n-1}\)）

于是現在只需要維護出插入每對葉子后 \(cnt\) 的值，考慮如何解決這個數據結構問題，而每對葉子會對兩條鏈造成貢獻，那每個點的集合實際上可以從兒子或者父親繼承過來，只需要用可持久化線段樹/可持久化線段樹合并就能在 \(\mathcal{O}(n\log n)\) 的時間復雜度內得到所有 \(S(u)\) 的信息，如何刻畫 \(S(u)\) 呢？由于我們需要查詢保留每一個集合中小于等于某個值的元素的結果，那么不妨把每一個集合刻畫成一個 \(01\) 字符串，這樣每次查詢就是保留所有字符串的前綴做詢問

如果已經得到了所有的 \(01\) 字符串，這時候我們需要知道保留前 \(i\) 個位置的字符的本質不同的字符串個數，那么只需要對所有字符串按字典序排序，考慮相鄰的兩個字符串在何時不會有貢獻即可，這個位置就是其 \(lcp\)，把他們的 \(lcp\) 快速找出來就行了

那么現在要做的是什么？維護一些 \(01\) 字符串，每次比較兩個字符串的字典序，求兩個字符串的 \(lcp\)，這是個經典問題，可以直接用線段樹維護區間的哈希值，這里可以直接異或哈希，比較和求 \(lcp\) 的時候在線段樹上二分即可，這樣總復雜度可以做到 \(\mathcal{O}(n\log^2 n)\)，需要略微卡卡常

后面的東西可以做到 \(\mathcal{O}(n\log n)\)

7.19

P13272 [NOI2025] 序列變換

這么這么這么這么這么這么這么這么

首先發現當操作了 \((i,i+1)\) 后就不會再操作一遍 \((i-1,i)\)，那么操作一次之后不會再回頭，也就是說方向相反的操作之間可以看成是獨立的，把一次操作當成一個 > 或者 <，那最終的序列就是形如 >>>>▲<<<<>>>▲>>><<<，只有 ▲ 的位置是有值的，其他位置都是 \(0\)，于是我們可以把一個 >>>▲<<< 看成一個基本結構，最后的序列就是一些這樣的串拼起來，那 \(\mathcal{O}(n^3)\) 的 dp 就呼之欲出了，我們記 \(f_i\) 為考慮了前 \(i\) 個位置的答案，那么每次枚舉 \(j\) 并轉移 \(f_i+w(i+1,j)\rightarrow f_j\)，計算 \(w(l,r)\)，可以直接暴力枚舉中間的 ▲ 的位置轉移即可，但是計數直接這樣做會記重

我們再去分析這個題目的性質，當拼上一段時，有些段是不合法的，其肯定是 >>>▲▲▲<<<，就是說左右端點可以消掉的位置不夠多，于是考慮記 \(L_i\) 為以 \(i\) 為起點，向左最遠能到的位置，\(R_i\) 為以 \(i\) 為起點，向右最遠能到的位置，那么一個段合法當且僅當 \(L_r\le R_l\)，為了方便計數，我們可以考慮讓這個 \(L\) 和 \(R\) 的定義更嚴一點，考慮在計數的時刻 >>>> 一整段都消掉的情況可以和其他段拼在一起導致計數計重，那么我們只需要讓其在求 \(L_i\) 的過程中，遇到把 \(a_i\) 消成 \(0\) 的情況就停止，這樣所有的段都不會被拆成更小的段，計數重復的問題也就解決了，這樣 \(\mathcal{O}(n^3)\) 的 dp 就是對的了

我們觀察一下一段中每個數的貢獻，發現是 \(...-+-+-+-+...\) 的形式，最后剩下的位置為 \(+\)，那可以發現，一段中能貢獻的位置肯定在 \([\max(l,L_r),\min(r,R_l)]\) 中，而且其中貢獻不同只和位置的奇偶性有關！于是記 \(s_k=\sum\limits_{i=1}^k (-1)^{i+1} a_i\)，我們處理每一段的時候，記 \(k=s_{\min(r,R_l)}-s_{\max(l,L_r)-1}\)，只需要對 \(k\) 分類討論即可

\(k>0\) 時，這一段的能貢獻到的區間中，所有下標為奇數的位置都是合法的
\(k<0\) 時，所有下標為偶數的位置都是合法的
\(k=0\) 時，這時候這一段無論如何都會被消成 >>><<<，那所有的位置都會有貢獻

那么在轉移的時候，只需要維護 \(\sum\limits [2 \mid i]\frac{1}{c_i}\)、\(\min\limits_{2 \not\mid i}\left\{ b_i \right\}\)、\(\sum\limits [2 \not\mid i]\frac{1}{c_i}\)、\(\min\limits_{2 \mid i}\left\{ b_i \right\}\) 即可，復雜度 \(\mathcal{O}(n^2)\)

P6790 [SNOI2020] 生成樹

廣義串并聯圖方法。

記 \(f_e\) 為 \(e\) 在生成樹上的方案數，\(g_e\) 為 \(e\) 不在生成樹上的方案數

縮一度點：\(ans\leftarrow ans\times f_e\)
縮二度點：\(f_{e}\leftarrow f_{u}\times f_{v}\)，\(g_e\leftarrow f_u\times g_v + f_v\times g_u\)
疊合重邊：\(f_e\leftarrow f_u\times g_v +f_v\times g_u\)，\(g_e\leftarrow g_u\times g_v\)

用堆維護度數 \(\le2\) 的點，復雜度 \(\mathcal{O}(m\log m)\)

P8426 [JOI Open 2022] 放學路 / School Road

廣義串并聯圖練習題。

可以很自然地聯想到用廣義串并聯圖的方法去維護題目所求，因為我們發現一條路徑如果出現了形如 “分叉——兩條鏈——分叉” 的結構，而上下兩條鏈長度相等時是等價的

縮一度點：直接刪掉即可
縮二度點：將新邊的權值設為另外兩邊權值之和（當有邊權值為 \(-1\) 時，新邊的權值也為 \(-1\)）
疊合重邊：如果這兩條邊權值不一，那么一定至少存在兩條從 \(u\) 到 \(v\) 的路徑，這時候這條邊是無敵的，給他的權值設為 \(-1\)；如果這兩條邊權值相同，那么直接不管就行了

那這時候一直進行這個過程，我們可以斷言，最后如果只剩下 \((1,n,w)\) 的邊，且 \(w\ne -1\)，那原圖的答案就是 \(0\)？

但是可以構造 \(1\) 和 \(n\) 不在一個點雙中來 hack 這個結論，然而，整個圖都在同一個點雙中的時候，該結論是成立的，證明如下：

直接縮掉所有的二度點，這時候整張圖滿足每個點度數都 \(\ge 3\) 且點雙連通，而且其點數肯定滿足 \(\ge 4\)，因為每個點的度數都 \(\ge 3\)，我們考慮以 \(1\) 為源點，\(n\) 為匯點給這張圖定向，每條邊方向 \((u,v)\) 滿足 \(\text{dis}(1,u)+w= \text{dis}(1,v)\)，如果存在 \(\text{dis}(1,u)+w\ne \text{dis}(1,v)\) 肯定就寄了，這時候令入度 \(>\) 出度的點為藍色點，反之則為紅色點，由于每個點度數 \(>3\)，那么 \(1\) 肯定是紅色點，\(n\) 肯定是藍色點，那么考慮 \(1\rightarrow n\) 最長的一條鏈 \(1\rightarrow a_1\rightarrow a_2\rightarrow...\rightarrow n\)，這條鏈上肯定存在一個位置 \((u,v)\)，滿足 \(u\) 為紅色點且 \(v\) 為藍色點，我們再考慮 \(1\rightarrow u\rightarrow v\rightarrow n\) 這條鏈，這時肯定存在一個 \(u\rightarrow x,x\ne v\) 和 \(y\rightarrow v,y\ne u\)，那接著考慮 \(1\rightarrow y\rightarrow v\rightarrow u\rightarrow x\rightarrow n\)，如果其是簡單路徑，那么這時候這張圖已經廢了，那如果不是簡單路徑，肯定會在 \(1\rightarrow y\rightarrow v\) 和 \(x\rightarrow n\) 的部分有重合，我們找到這個點 \(z\)，那么可以直接構造一條簡單路徑 \(1\rightarrow u\rightarrow x\rightarrow z\rightarrow y\rightarrow v\rightarrow n\)，這時候便不是最長的一條鏈，結論得證

于是我們再添加一條 \((1,n,dis(1,n))\) 的邊即可，最終復雜度 \(\mathcal{O}(m\log m)\)

7.20

P13274 [NOI2025] 三目運算符

幽默感這一塊

手玩一下，找到第一個 \(110\) 的位置，如果沒有 \(110\) 那就看是否存在 \(101\)，線段樹維護

P13275 [NOI2025] 集合

太難了

求

\[ \sum_s[x^sy^s]\left(\prod_{i=0}^{2^n-1} a_ix^i+a_iy^i+1\right) \]

這里集合冪級數的乘法是 \(AND\) 卷積

我們把二進制數取反，那么原來的集合冪級數的 \(AND\) 卷積就變成了 \(OR\) 卷積

考慮每一個 \(i\) 對應的集合冪級數 \(F_i=a_ix^i+a_iy^i+1\)，對其 \(FMT\) 得到

\[[x^uy^v]FMT(F_i)=(a_i[i\subseteq u]+a_i[i\subseteq v]+1) \]

再把所有的 \(FMT(F_i)\) 點積起來就可以得到

\[[x^uy^v]FMT\left(\prod F_i\right)=\prod\limits_{i=0}^{2^n-1}\left(a_i[i\subseteq u]+a_i[i\subseteq v]+1\right) \]

于是考慮令 \(f_s=\prod\limits_{i\subseteq s}\left(a_i+1\right),g_s=\prod\limits_{i\subseteq s}\left(2a_i+1\right)\)，那么就有

\[[x^uy^v]FMT\left(\prod\limits F_i\right)=f_uf_v\frac{g_{u\cap v}}{f_{u\cap v}^2} \]

把這個式子 \(IFMT\) 回去，可以得到

\[[x^sy^s]\prod\limits_{F_i}=\sum\limits_{u\subseteq s}(-1)^{|s|-|u|}\sum\limits_{v\subseteq s}(-1)^{|s|-|v|}f_uf_v\frac{g_{u\cap v}}{f_{u\cap v}^2}=\sum\limits_{u\subseteq s}\sum\limits_{v\subseteq s}(-1)^{2|s|-|u|-|v|}(-1)f_uf_v\frac{g_{u\cap v}}{f_{u\cap v}^2} \]

又有 \((-1)^{2|s|-|u|-|v|}=(-1)^{|u|+|v|}\)，那答案就是

\[ \sum_{s=0}^{2^n-1} \sum_{u\subseteq s}\sum_{v\subseteq s}(-1)^{|u|}(-1)^{|v|}f_uf_v\frac{g_{u\cap v}}{f^2_{u\cap v}} \]

發現沒必要枚舉 \(s\) 了，那就可以化成

\[ \sum_{u}\sum_v(-1)^{|u|}(-1)^{|v|}f_uf_v\frac{g_{u\cap v}}{f^2_{u\cap v}}\times 2^{n-|u\cup v|} \]

有 \(u\cap v\) 又有 \(u \cup v\)，考慮一手 \(|u|+|v|=|u\cap v|+|u\cup v|\)，那么把 \(|u\cup v|\) 消掉可以得到

\[ 2^n\sum_{u}\sum_v(-2)^{-|u|}(-2)^{-|v|}f_uf_v\frac{g_{u\cap v}}{f^2_{u\cap v}}\times 2^{|u\cap v|} \]

這樣 \(u\)、\(v\) 以及 \(|u\cap v|\) 的貢獻就獨立開來了，\(f\) 和 \(g\) 可以直接高維前綴和算，把 \((-2)^{-|u|}f_u\) 直接自己卷自己計算出來最后統計貢獻就行了

嗎？實際上在 \(\frac{1}{f_{u\cap v}^2}\) 的時候可能會發生除以 \(MOD\) 的情況，考慮擴域，把每個數用 \(A\times 0^{B}\) 的形式表示出來，然而加減法是沒有良定義的，但是我們只需要保留 \(0^0\) 的系數，所以加減時保留次數最低的項即可，復雜度 \(\mathcal{O}(n2^n)\)

P13276 [NOI2025] 絕對防御

wmh純神

記 \(a_i,b_i\) 分別為第 \(i\) 輪對戰攻擊牌/防御牌摸到了幾張，假如前 \(k\) 張中有 \(h\) 張防御牌，那現在就是要判定是否存在一個序列 \(c\) 表示每輪對戰是否發動技能，則需要滿足以下約束：

\(\forall 0<x\le n,c_x\in \left\{0,1\right\}\)
\(\forall 0<x\le n,h+\sum\limits_{i=1}^{x}(b_i-1+c_i)\ge 0\)
\(\forall 0<x\le n,h-k+\sum\limits_{i=1}^{x}(a_i-1-c_i)\ge 0\)
\(\forall 0< x<y\le n,y-x< z,\sum_{i=x}^y c_i\le 1\)

考慮記 \(s_i\) 表示 \(c_i\) 的前綴和，\(l_i=1-b_i,r_i=a_i-1\)，\(L_i,R_i\) 分別為 \(l_i,r_i\) 的前綴和

不想寫了，簡單說一下

這樣可以建模差分約束，最后可以把限制表示出來，都是形如最大子段和/最大前綴和/最大后綴和，可以直接線段樹上二分求，復雜度 \(\mathcal{O}(n+q\log n)\)

7.21

P7670 [JOI 2018 Final] 毒蛇越獄 / Snake Escaping

由于每個串 \(0\)、\(1\)、\(?\) 三種字符的數量和 \(\le 20\)，那么其中出現次數最少字符的數量肯定滿足 \(\le 6\)

如果 \(0\) 的數量最少，那我們可以直接容斥，枚舉每一個零變成 \(0\) 還是 \(?\)，記錄一下超集權值和就行了，\(1\) 的數量最少的時候同理，記錄子集和，而 \(?\) 直接枚舉計算貢獻就行了

高維前綴和預處理，復雜度 \(\mathcal{O}(n2^n+q2^{\frac{n}{3}})\)

AT_agc035_f [AGC035F] Two Histograms

何時會計重？

發現若存在 \(l_i=j-1,k_j=i\) 或者 \(l_i=j,l_j=i-1\)，這樣的序列會計重，下面證明這是充要條件：

現在有兩個操作序列滿足不存在 \(l_i=j-1,k_j=i\)，而且他們所形成的網格圖相同，另一種情況同理，這兩個操作序列分別為記作 \((l,k),(l',k')\)，考慮最小的 \(i\) 滿足 \(l_i\ne l'_{i}\)，不妨設 \(l_i<l_i'\)，記 \(r=l_i'\)，此時必定有 \(k_r\ge i\) 且 \(k_r'<i\)，否則 \((r,i)\) 處兩張網格圖會不同（注意重合算 \(2\)），那考慮 \((r,i-1)\) 這個位置，因為此時有 \(l_{i}'\ne l_{i-1}\)，所以這個位置在兩張網格圖上肯定不同，由此推出矛盾

那現在我們只需要數不存在 \(l_i=j-1,k_j=i\) 的網格的數量就行了，考慮容斥，記 \(f_i\) 為欽定存在 \(i\) 個這種結構的網格的方案數，則有

\[ f_i=\binom{n}{i}\binom{m}{i}i!(n+1)^{m-i}(m+1)^{n-i} \]

那么答案就是 \(\sum\limits_{i\ge 0}(-1)^if_i\)，線性計算即可

AT_agc036_f [AGC036F] Square Constraints

其實限制就是 \(l_i\le p_i\le r_i\) 的排列個數，我們考慮如果沒有 \(l_i\) 的限制，可以把所有的 \(r_i\) 排序，答案就是 \(\prod\limits_{i=1}^{n}\left( r_i-i+1 \right)\)，考慮容斥，那我們要做的就變成了一些數的上界為 \(l_i\)，一些數的上界為 \(r_i\) 的問題，我們先把 \([0,n]\) 和 \([n+1,2n-1]\) 分開來考慮，因為后者是沒有下界限制的，從后往前枚舉 \([0,n]\) 中的數，考慮記 \(f_{i,j}\) 為當前進行到了 \(i\)，容斥了 \(j\) 個的貢獻，為了方便，我們可以把滿足 \(l_i\ge r_j>l_{i-1}\) 的 \(j\in [n+1,2n-1]\) 放到 \(i\) 這里統計貢獻，這些數的排名是容易計算的

現在決策 \(i\) 該如何放，如果選擇放到 \(l\)，排名可以直接算出來，而放到 \(r\) 卻不好計算排名，因為這時候我們需要知道一共容斥了幾個，對這個的處理也是簡單的，直接在最外層枚舉一共容斥了幾個就行，最終復雜度為 \(\mathcal{O}(n^3)\)

AT_arc093_d [ARC093F] Dark Horse

可以強制令 \(p_1=1\)，最后給答案乘上 \(2^n\) 就行了，題目要求數每個子樹中的最小值都不在集合 \(A\) 中，那考慮容斥，枚舉子樹最小值在集合 \(A\) 的集合為 \(S\)，假如集合 \(S\) 的貢獻為 \(f(S)\)，最后答案就是 \(\sum\limits_{S}(-1)^{|S|}f(S)\)，現在考慮如何計算 \(f(S)\)

為了方便，我們可以把 \(A\) 從大到小排序，然后從大到小插入 \(A\) 中的元素，記 \(g(i,S)\) 表示考慮了前 \(i\) 個，\(n\) 個子樹中，最小值在 \(A\) 中的子樹集合為 \(S\)，那么 \(g(i,S)\) 的轉移只有兩種

什么都不干
塞一個 \(S\) 中的數到第 \(k\) 個子樹中，同時拉上 \(2^k-1\) 個比他小的點

復雜度 \(\mathcal{O}(nm2^n)\)

AT_agc038_c [AGC038C] LCMs

幽默

可以 gcd 卷積

記 \(\hat F(n)\) 為 \(F(n)\) 做迪利克雷后綴和的結果，即 \(\hat F(d)=\sum\limits_{d|n} F_{n}\)，那 \(h(n)=\sum\limits_{\gcd(x,y)=n}f(x)g(y)\)，也就有 \(\hat h(d)=\sum\limits_{d|\gcd(x,y)}f(x)g(y)=\sum\limits_{d|x,d|y}f(x)f(y)=\hat f(d)\hat g(d)\)，再做一遍迪利克雷后綴差分就能得到 \(h\) 的值了

每個值開一個桶 \(c_i\)，記值域為 \(N\)，這樣就變成了計算

\[\frac{ \sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}c_ic_j\text{lcm}(i,j)-\sum\limits_{i=1}^{n}ic_i}{2} \]

莫反。

\[ \begin{align} & \sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}c_ic_j\text{lcm}(i,j)\\ & =\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}c_ic_j\frac{ij}{\gcd(i,j)}\\ & =\sum\limits_{d=1}^{N}\sum\limits_{i=1}^{\left\lfloor \frac{N}w0obha2h00\right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{N}w0obha2h00\right\rfloor}c_{id}c_{jd}\frac{d^2ij}w0obha2h00[\gcd(i,j)=1]\\ & =\sum\limits_{d=1}^{N}\sum\limits_{i=1}^{\left\lfloor \frac{N}w0obha2h00\right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{N}w0obha2h00\right\rfloor}c_{id}c_{jd}dij\sum\limits_{k|i,k|j}\mu(k)\\ & =\sum\limits_{d=1}^{N}\sum\limits_{k=1}^{\left\lfloor \frac{N}w0obha2h00\right\rfloor}\sum\limits_{i=1}^{\left\lfloor \frac{N}{kd}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{N}{kd}\right\rfloor}\mu(k)c_{ikd}c_{jkd}dk^2ij\\ \end{align} \]

令 \(T=kd\)，則原式

\[ \begin{align} & =\sum\limits_{T=1}^{N}T\sum\limits_{k|T}\mu(k)k\sum\limits_{i=1}^{\left\lfloor \frac{N}{T}\right\rfloor}ic_{iT}\sum\limits_{j=1}^{\left\lfloor \frac{N}{T}\right\rfloor}jc_{jT}\\ & =\sum\limits_{T=1}^{N}T\left(\sum\limits_{k|T}\mu(k)k\right)\left(\sum\limits_{i=1}^{\left\lfloor \frac{N}{T}\right\rfloor}ic_{iT}\right)^2\\ \end{align} \]

第二部分可以迪利克雷前綴和，剩下的部分直接枚舉，總復雜度 \(\mathcal{O}(n\log n)\)

qoj2209

奇異搞笑。

令每個點 \(x_i\leftarrow x_i+i\)，這樣時時刻刻滿足 \(x_i\le x_{i+1}\) 就變成了 \(x_i<x_{i+1}\)，直接容斥，記 \(f_i\) 為從 \(i\) 號點走到終點的答案，則每一個 \(i\) 能到達的 \(j\) 會對 \(i\) 有負一的貢獻，也就是 \(f_i\leftarrow f_i-f_j\times w(i,j)\)，其中 \(w(i,j)\) 為從 \(i\) 走到 \(j\) 的方案數，直接構造行列式計算即可，最后復雜度為 \(\mathcal{O}(n^5)\)

7.22

P5643 [PKUWC2018] 隨機游走

Min-Max 容斥+樹上高消

要求算所有關鍵點都出現的期望，有 \(E(max(S))=\sum\limits_{T\subseteq S}E(min(T))\)，那改成計算第一次碰到關鍵點的期望即可，記 \(f_u\) 為從 \(u\) 開始第一次碰到一個關鍵點期望走多少步，則有轉移

\[ f_u=\frac{1}{deg_u}\left(\sum\limits_{v\in son(u)}f_v+f_{fa_u}\right)+1 \]

設 \(f_u=k_uf_{fa_u}+b_u\)，我們可以輕松解出來 \(k_u\) 和 \(b_u\) 的值，最后需要的就是 \(b_{root}\) 的值，而關鍵點只需要把 \(k_u\) 和 \(b_u\) 都設成 \(0\) 就行了，最后高維前綴和以下就行了，復雜度 \(\mathcal{O}(n(2^n+q))\)

AT_agc038_e [AGC038E] Gachapon

Min-Max 容斥，我們需要計算一個集合 \(T\) 中第一次存在一個 \(i\) 出現了 \(B_i\) 次的期望，記 \(i\) 的出現次數為 \(c_i\)，考慮計算任意時刻 \(c_i<B_i\) 的期望，最后給答案加 \(1\) 就行了，集合 \(T\) 之外的數怎么辦？考慮期望多少步可以選到一個 \(T\) 中的元素，記這個步數為 \(P\)，則有 \(P=\frac{\sum\limits A_i}{\sum\limits_{i\in T}A_i}\)，最后給答案乘上 \(P\) 即可

考慮枚舉每個數的出現次數 \(c_i\)，那答案就是

\[ \sum\limits_{i\in T}\left(\frac{A_i}{\sum\limits_{i\in T}A_i}\right)^{c_i}\binom{k}{c_1,c_2,...,c_{|T|}} \]

其中 \(k=\sum\limits_{i\in T}c_i\)

于是 dp 的時候記錄 \(\sum c_i\)、\(\sum a_i\)，把容斥系數直接乘進去就行了，復雜度 \(\mathcal{O}(n^3)\)

qoj2568

神題

對于一組權值 \(a\)，如何判斷其是否合法呢？考慮一個 dp \(f_{i,j}=\max(f_{i-1,j},f_{i,j-1})+a_{i,j}\)，可以發現，一個 \(f\) 唯一確定一組 \(a\)，而且滿足 \(f_{i,j}\ge f_{i-1,j}\) 且 \(f_{i,j}\ge f_{i,j-1}\)，那么把 \((i,j,f_{i,j})\) 視作一個三維網格中的柱形，那么我們要數的就是高度 \(\le k\) 的網格的角落的方案，把每個等高線搞出來，發現他們構成\(k\) 個 \((1,1)\) 到 \((n,m)\) 的路徑！！！這時候把 \(i\) 的起點和終點都 \(+i\)，那么就變成了不交路徑計數！LGV 計算即可，復雜度 \(\mathcal{O}(n^3)\)

P8333 [ZJOI2022] 計算幾何/P8114 [Cnoi2021] 六邊形戰士

和上面那道神題差不多

六邊形戰士這題，就是讓數把六邊形平面用平行四邊形密鋪的方案，幸虧我看過這個，可以構造一個四邊形密鋪到立方體計數的雙射，這樣就和上面那道神題一樣了，但是我們有 \(O(n)\) 計算的方法

考慮一個值域為 \([1,n]\) 的半對稱楊表 \(\lambda\) 的勾長公式

\[ |\text{SSYT}(\lambda)|=\prod_{(i,j)\in \lambda}\frac{n-i+j}{\text{hook}(i,j)} \]

把第 \(i\) 行的每個數加上 \(a-i+1\)，就把原問題轉化為計算一個值域為 \([1,a+c]\) 的半標準楊表的方案，帶入 \(a=b+c-a,b=a+c-b,c=a+b-c\) 之后拆開式子可以算出來最后答案為

\[ \frac{f(a+b+c-1)f(a-1)f(b-1)f(c-1)}{f(a+b-1)f(b+c-1)f(a+c-1)} \]

其中 \(f(i)=\prod\limits_{i=1}^{n}i!\)

計算幾何需要再轉化一步，把圖畫出來，會有一些小三角形，給頂點相鄰的小三角連邊，問題就變成了六邊形戰士，不過需要注意 \(a\le b+c\) 或者輪換對稱的情況，這時候六邊形會退化

P5693 EI 的第六分塊

嗑特特

普通的動態最大子段和，需要維護這幾個信息

\(ml\)：最大前綴和
\(mr\)：最大后綴和
\(mx\)：最大子段和
\(s\)：區間和

考慮對一個節點做加法時，把這些信息刻畫成一個一次函數 \(kx+b\)，\(k\) 就是其包含的元素個數，而兩個區間的信息合并就是兩個一次函數直接相加，去和另一個一次函數作比較，考慮維護出來一個一次函數被另一個一次函數擊敗的最小的 \(x\)，記為 \(p\)，那么當 \(x\ge p\) 時，這個區間的信息會發生改變，于是我們做區間修改的時候，暴力遞歸每一個發生改變的節點即可，復雜度是 \(\mathcal{O}(n\log^3n)\) 的

實際實現時，并不需要再額外維護一個 \(x\)，只需要令 \(p\leftarrow p-x\) 即可，一次函數去維護 \(k\) 和當前的 \(y\)，也就是說我們可以直接把坐標系向左平移

posted @ 2025-09-25 15:34 fqmzwmhx 閱讀(4) 評論(0) 收藏舉報

刷新頁面返回頂部

oaigoaigilowoaigiy