做題筆記13

8.9

P9527 [JOISC 2022] 灑水器

直接打標記，記 \(f_{u,d}\) 為給 \(u\) 子樹內距離為 \(d\) 的乘上 \(f_{u,d}\)，查詢時直接跳父親就完了，修改時對于 \(u\) 的 \(40\) 個祖先打標記，\(k\) 級父親 \(p\) 在 \(f_{p,d-k}\) 和 \(f_{p,d-k-1}\) 打標記就能覆蓋 \(2d-1\) 層鄰域了

如果存在一個點，所有的情況下路徑交都包含這個點，那么我們可以直接把原問題轉成判定性問題，而兩個樹有交的充要條件是兩個樹的距離小于等于 \(d\)，直接選擇深度最大的 LCA \(p\)，找到其 \(d\) 級祖先 \(v\)，\(v\) 子樹外的路徑肯定和 \(p\) 所在路徑無交，\(v\) 子樹內的路徑和 \(p\) 所在路徑的最近的點肯定是其 LCA，我們只需要維護 \(v\) 子樹內的直徑就行了，復雜度 \(\mathcal{O}(n\log n)\)

確實不會證明

#8717. 骰子

太唐了，完全沒看懂官方題解在干什么

直接分治，記 \(f_{i,j}\) 為保留 \([mid+1,i]\) 這一段區間，和為 \(j\) 的概率，或者保留 \([i,mid]\)，和為 \(j\) 的概率，直接合并肯定報了，考慮左區間的和為 \(i\)，右區間只要滿足和 \(\le m-i\) 就能合并了，具體來說，記 \(dp_{i,j,k}\) 表示右半邊考慮完了 \([mid+1,i]\)，先不考慮左半邊，讓左邊和為 \(j\)，右邊和為 \(k\) 的權值，做一個類似貢獻提前計算的東西，讓 \(f_{i,j}\times b_{j+k}\) 貢獻給 \(dp_{i,j,k}\)，把 \(dp\) 做一遍前綴和，最后再算總的貢獻就行了，復雜度 \(\mathcal{O}(nm^2+n^2m)\)

P4619 [SDOI2018] 舊試題

模擬賽題

求

\[\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C d(ijk) \]

有結論

\[d(ijk)=\sum_{x|i}\sum_{y|j}\sum_{z|k}[x\perp y][y\perp z][x\perp z] \]

如何證明？考慮 \(ijk\) 都是某個質數的自然數冪次的形式，結論顯然成立，由于 \(d\) 是積性函數，后續的證明也是平凡的

莫反

\[\begin{aligned} & \sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)\\ & = \sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{x|i}\sum_{y|j}\sum_{z|k}[x\perp y][x\perp z][y\perp z]\\ & = \sum_{x=1}^A\left\lfloor\frac{A}{x}\right\rfloor\sum_{y=1}^B\left\lfloor\frac{B}{y}\right\rfloor\sum_{z=1}^C\left\lfloor\frac{C}{z}\right\rfloor[x\perp y][x\perp z][y\perp z]\\ & = \sum_{x=1}^A\left\lfloor\frac{A}{x}\right\rfloor\sum_{y=1}^B\left\lfloor\frac{B}{y}\right\rfloor\sum_{z=1}^C\left\lfloor\frac{C}{z}\right\rfloor\sum_{a|x,a|y}\sum_{b|x,b|z}\sum_{c|y,c|z}\mu(a)\mu(b)\mu(c)\\ & = \sum_{a=1}^{\min(A,B)}\mu(a)\sum_{b=1}^{\min(A,C)}\mu(b)\sum_{c=1}^{\min(B,C)}\mu(c)\sum_{\text{lcm}(a,b)|x}\left\lfloor\frac{A}{x}\right\rfloor\sum_{\text{lcm}(a,c)|x}\left\lfloor\frac{B}{x}\right\rfloor\sum_{\text{lcm}(b,c)|x}\left\lfloor\frac{C}{x}\right\rfloor\\ \end{aligned} \]

記 \(F(n,x)=\sum_{x|k}\left\lfloor\frac{n}{k}\right\rfloor\)，只需要對于 \(A,B,C\) 分別算出來 \(F\) 的值就行了，顯然可以 \(\mathcal{O}(n\log n)\) 預處理，最后做三元環計數就行了，復雜度 \(m\sqrt m\)

8.10

模擬賽

T1

我操，原

T2

奇偶獨立，面積并，拉插

T3

不會

誒星

T1

唐

T2

唐

T3

唐

T4

唐

T5

不會。

T6

唐

T7

唐

T8

唐

8.11

P12371 【模板】最大團/最大獨立集

找度數最大的點，如果這個點的度數 \(\le 2\) 說明只有鏈和環，是容易處理的，否則枚舉度數最大的點是否加入獨立集直接搜索，復雜度 \(T(n)=T(n-1)+T(n-4)=\mathcal{O}(1.3803^n)\)

P5906 【模板】回滾莫隊&不刪除莫隊

每個塊中按右端點排序，掃左端點的時候，先把左端點移到這個塊的右側再往左掃，復雜度顯然是對的，即 \(\mathcal{O}(n\sqrt m)\)

P11829 [TOIP2024] 棲息地分配

考慮直接讓其中兩個集合大小為 \(1\)，那么現在我們只需要要求這兩個點的鄰域的交集小于 \(2\)，考慮找出來度數最小的點 \(u\)

如果 \(u\) 的度數為 \(0/1\)，再隨便找一個點就是合法的
如果 \(u\) 的度數為 \(2\)，相連的兩個點中有一個是合法的，其肯定與另一個沒有連邊，那不合法的時候這三個點一定全都互相有連邊，考慮其他的點，若不存在合法構造，這些點肯定都要與 \(u\) 相連的兩個點都有邊，那此時邊數至少為 \(3+2(n-3)=2n-3\)
如果 \(u\) 的度數為 \(3\)，如果不合法則 \(u\) 與其鄰域構成一張完全圖，其他的點不也不合法也要與 \(u\) 鄰域的兩個點有邊，那此時邊數至少為 \(5+2(n-4)=2n-3\)
\(u\) 的度數 \(\ge 4\)，邊數至少為 \(2n\)

那我們直接證明了這樣構造至少會存在一組解，復雜度容易做到線性

#6011. Map Reduce

我操

首先判斷出來是否能構造出來一個 \(D\)，肯定要滿足 \(D\) 與初始的最短路奇偶性相同，且 \(D\) 小于等于初始的最短路且大于等于兩點間的最短距離，發現這樣的 \(D\) 都是可以被構造出來的，我們給每一個障礙欽定一個刪除順序，使得每一個障礙刪除之后，每兩個點之間的最短路的變化兩不超過 \(2\)，可以刪除的障礙有這兩種：

...    ???
.#.    ?##
???    ?##

那么用隊列維護出來這個刪除的順序，最后在這個隊列上二分即可，復雜度 \(\mathcal{O}(nm\log nm)\)

8.12

朱鵬睿純神

P3350 [ZJOI2016] 旅行者

KDT 分治

CF1710D Recover the Tree

？

從小到大考慮每個區間，如果當前考慮到了 \([l,r]\)，\(l\) 所在連通塊為 \([l',x_1]\)，\(r\) 所在連通塊為 \([x_k+1,r']\)，他們中間有若干個聯通塊 \([x_i+1,x_i]\)，滿足 \(l'\le l\le x_1<x_2<\cdots<x_k<r\le r'\)，且 \(k\ge 1\)，如果 \(k=2\)，顯然無解，否則直接在 \(l,r\)、\(l,x_k\) 以及 \(r,x_i(2\le i<k)\) 之間連邊

CF1707E Replace

結論：如果 \([l_u,r_u]\cap[l_v,r_v]\ne \emptyset\)，則有 \(f([l_u,r_u]\cup[l_v,r_v])=f([l_u,r_u])\cup f([l_v,r_v])\)，因此我們可以預處理出來 \(z_{i,j,k}\) 表示 \([i,i+2^j]\) 跳 \(2^k\) 步的結果，直接詢問即可，復雜度 \(\mathcal{O}(n\log^2n+q\log n)\)

#750. 【UNR #6】小火車

牛逼

原問題等價為找出兩個不相同的子集，使得這兩個子集的子集和相同，\(2^n>p\) 有什么用呢？他保證了一定有解！因為一共有 \(2^n\) 種子集，而子集和只有 \(p\) 種，根據鴿巢原理可以判斷出肯定有解。

我們接著考慮鴿巢原理，在值域上二分，如果當前在區間 \([l,r]\)，我們令 \(s_{l,r}\) 為子集和在 \([l,r]\) 這段區間內的子集個數，如果 \(s_{l,r}>r-l+1\)，那 \([l,r]\) 中必定有解，而且 \([l,mid]\) 和 \([mid+1,r]\) 兩個區間中一定存在一個區間有解，這樣二分就可以了

如何求 \(s_{l,r}\)？我們可以 meet in the middle 完了雙指針，這樣總復雜度 \(\mathcal{O}(2^{\frac{n}{2}}\log p)\)

AT_arc199_d [ARC199D] Limestone

不妨令 \(n<m\)

首先一個矩陣需要滿足每一個位置要么上面的全是 \(1\) 要么左邊的全是 \(1\)，于是可以從最后一行往前轉移，考慮他的狀態，肯定是一段極長的 \(1\) 和一些斷續的 \(1\)，那些斷續的 \(1\) 上面必須都是 \(1\)，發現可以直接把那些列扣掉，那么直接記狀態 \(f_{i,j}\) 表示表示大小 \(i\times j\) 的矩陣的方案，\(g_{i,j}\) 為其權值和，直接枚舉極長的段以及斷續的 \(1\) 的個數即可，則有轉移：

\[f_{i,j}=f_{i-1,j}+\sum_{k=0}^{j-1}\sum_{l=0}^{j-k-1}\binom{j-k-1}{l}f_{i-1,j-l} \]

\[g_{i,j}=g_{i-1,j}+f_{i-1,j}\times j+\sum_{k=0}^{j-1}\sum_{l=0}^{j-k-1}\binom{j-k-1}{l}\left(g_{i-1,j-l}+f_{i-1,j-l}\times (k+i\times l)\right) \]

交換求和符號，后面的系數是一個上指標求和的形式，容易做到 \(\mathcal{O}(n^2m)\)

P12705 呃呃

我操

如果給每條邊 \((u,v)\) 開一個數組 \(b_{u,v}\) 表示和 \(u,v\) 都有連邊的點的個數，那么存在四元環當且僅當存在 \(b_{u,v}\ge 2\)，修改一條邊時是容易維護出 \(b\) 的變化的，這一部分容易做到 \(\mathcal{O}(nq)\)

現在問題在于如何維護出最開始的 \(b\) 數組，直接維護復雜度是 \(\mathcal{O}(n^3)\) 的，即 \(\sum\binom{deg_u}{2}\)，但是發有當 \(\sum\binom{deg_u}{2}>\binom{n}{2}\) 的時候，必定存在四元環，可以直接鴿巢原理證明：把每條邊的 \(b\) 看成一個桶，一共 \(\sum\binom{deg_u}{2}\) 個東西要塞到這些桶里面去，所以必定存在 \(b_{u,v}\ge 2\)

那當 \(\sum\binom{deg_u}{2}\le \binom{n}{2}\) 的時候，我們再去維護 \(b\)，這樣復雜度是 \(\mathcal{O}(n^2+nq)\)

#11108. Nocturne without a Moon / 無月夜色

wow

移項得 \(\frac{p_i}{p_j}=\frac{p_l}{p_k}\)，可以考慮這個比值 \(\frac{x}{y}\) 滿足 \([x\perp y]\)，那么 \(p_i,p_j,p_k,p_l\) 可以分別表示成 \(ax,ay,by,bx\) 的形式，那現在要數的就是 \(\sum\limits_{a=1}^{n}\sum\limits_{b=1}^n\sum\limits_{x=1}^n\sum\limits_{y=1}^n[x\perp y][id_{ax}<id_{ay}<id_{by}<id_{bx}]\)，直接莫反變成 \(\sum\limits_{d=1}^n\mu(d)\sum\limits_{d|x}\sum\limits_{d|y}\sum\limits_{a=1}^n\sum\limits_{b=1}^n[id_{ax}<id_{ay}<id_{by}<id_{bx}]\)，我們發現一組合法的 \((a,b,x,y)\) 要么滿足 \(x,y\le \sqrt n\)，要么滿足 \(a,b\le \sqrt n\)，直接閾值分治

當 \(x,y\le \sqrt n\) 時，枚舉一組 \(x,y,a\)，這時候要數的就是滿足前后關系的 \(x,y,a,b\)，直接枚舉完了做就行，復雜度 \(\mathcal{O}(n\sqrt n)\)
當 \(a,b\le \sqrt n\) 時，枚舉一組 \(a,b,x\)，這時候要數的就是互相包含的 \(x,y,a,b\)，離線二維數點即可，復雜度 \(\mathcal{O}(n\sqrt n\log n)\)

那么總復雜度就是 \(\sum_{d=1}^n \frac{n}w0obha2h00\sqrt\frac{n}w0obha2h00\log\frac{n}w0obha2h00=\mathcal{O}(n\sqrt n\log n)\)，但其實我們的閾值分治是當 \(x,y\ge B\) 時，\(a,b\le \frac{n}{B}\)，可以平衡到 \(\mathcal{O}(n\sqrt{n\log n})\)

P11947 [KTSC 2025] 可愛區間 / maxsum

wow

考慮一個 \([l,r]\) 合法的充要條件是什么，不難發現應該有以下幾條：

\(\forall i<l,\sum\limits_{i\le k<l}c_k\le 0\)
\(\forall i>r,\sum\limits_{r>k\ge i}c_k\le 0\)
\(\forall i\in [l,r],\sum\limits_{l\le k\le i}c_k\ge 0\)
\(\forall i\in [l,r],\sum\limits_{i\le k\le r}c_k\ge 0\)
\(\sum\limits_{l\le i\le r}c_i\) 大于等于 \([1,l-1]\) 和 \([r+1,n]\) 的最大子段和

那最優情況肯定是 \([l,r]\) 中的 \(c_i=b_i\)，不在 \([l,r]\) 中的 \(c_i=a_i\)，記 \(sa_i=\sum\limits_{j\le i}a_j\)，\(sb_i=\sum_{j\le i}b_j\)，則要滿足的是

\(\forall i< l,sa_{l-1}-sa_{i-1}\le 0\)
\(\forall i>r,sa_{i}-sa_{r}\le 0\)
\(\forall i\in[l,r],sb_i-sb_{l-1}\ge 0,sb_{r}-sb_{i-1}\ge 0\)
\(sb_r-sb_{l-1}\) 大于等于 \([1,l-1]\) 和 \([r+1,n]\) 的最大子段和

前兩條限制就是讓 \(sa_i\) 是前綴/后綴 \(\min\)，可以單調棧出來所有滿足限制的位置，第三條就是讓 \(r\) 是區間 \(\max\)，\(l\) 是區間 \(\min\)，掃 \(r\)，可以用單調棧維護出來所有 \(l\) 的位置，為了滿足 \(r\) 是區間 \(\max\)，能取的 \(l\) 肯定是單調棧上的一段后綴，為了滿足第三條限制，\(l\) 肯定是越小越好，所以 \(l\) 肯定在一段區間內，我們可以直接二分出來這個區間，那現在要維護的就是這幾種操作：點亮/熄滅一個區間的關鍵位置，區間所有亮著的關鍵位置 \(+1\)，容易用線段樹維護，復雜度 \(\mathcal{O}((n+q)\log n)\)

AT_agc022_e [AGC022E] Median Replace

如何 check？

維護一個棧，從左往右掃，考慮當前加入的字符 \(c\)：

\(c=0\)，若棧頂有兩個 \(0\) 則變為一個，否則直接入棧
\(c=1\)，若棧頂為 \(0\)，可以直接抵消掉，若棧頂為 \(1\) 且已經有了兩個 \(1\)，不進行任何操作，否則入棧

這樣棧的狀態不會有太多，建出來自動機在上面 dp 就行了

8.13

模擬賽

T1

\(\binom{n}{m}\equiv [m\subseteq n] \bmod 2\)，隨便做

T2

左樹右鏈右樹左鏈，隨便維護

T3

不會

8.14

P13714 淘汰（Hard ver.）

直接 dij，一共 \(\mathcal{O}(3^k)\) 條邊，算貢獻可以高維前綴和預處理以下，總復雜度 \(\mathcal{O}(k3^k+3^k\log \left(3^k\right))\)，能過。

有做法復雜度是 \(\mathcal{O}(3^k)\) 的，不懂

8.15

模擬賽

T1

666

T2

完全圖 mst，考慮 Boruvka，考慮如何對于一個 \(s_i,t_i\) 找到其起立最大的串，發現可以雙指針，具體的，掃描其 lcp 在 \(s_i\) 上的長度，用另一個指針掃在 \(t_i\) 上的 lcp，然后判斷是否有解即可，把串放到字典樹上，問題就變成了是否存在 \(j\) 滿足 \(t_j\) 在 \(x\) 子樹中，且 \(s_j\) 在 \(y\) 子樹中，對于 \(t_j\) 在 \(x\) 子樹中的限制，我們用 dfn 序去刻畫，對于 \(s_j\) 在 \(y\) 子樹中的限制，考慮線段樹合并，維護線段樹每一個區間中的最小值和最大值，如果有一個和 \(s_i,t_i\) 不同則有解，這樣 Boruvka 做 \(\mathcal{O}(\log n)\) 輪，記 \(S=\sum |S_i|\)，總復雜度 \(\mathcal{O}(S\log S\log n)\)

T3

哦真的牛批

\(a_i\ge 0\) 咋做？維護兩個指針 \(i,j\)，初始 \(i\) 在 \(1\)，\(j\) 在 \(n\)，再維護一個變量 \(b\) 表示當前數可以放的位置的個數。如果 \(a_i\times a_j\le w\)，發現這時候 \(a_i\) 放到哪里都對之后能不能放沒有影響，于是給答案乘上 \(b\)，再令 \(b\) 加一，\(i\) 加一；如果 \(a_i\times a_j>w\)，發現這時候 \(a_j\) 放了之后，他相鄰的位置不能再放別的數，于是給答案乘上 \(b\)，再令 \(b\) 減一，\(j\) 減一。這樣我們就能得到 \(a_i\ge 0\) 時的答案

當存在負數的時候，由于 \(w\ge 0\)，所以負數和正數肯定可以放在一起，那我們的限制只剩下負數與負數之間以及正數與正數之間了，也就是說我們最后的序列肯定是一些正數的段和一些負數的段交替，直接做不好處理多個段的情況，我們不妨直接設最后出現了 \(x\) 段，發現令初始的 \(b=x\)，得到的就是欽定至多 \(x\) 段的答案！可以多項式多點求值快速算出 \(x\) 段的答案，由于我們求的是至多，二項式反演回去即可，最后分討一下兩個段分別取了幾個加起來就行了，復雜度 \(\mathcal{O}(n\log^2 n)\)，瓶頸在于多點求值

8.16

補了補之前的代碼。

P13536 [IOI 2025] 神話三峰（triples）（Part 1）

如果 \(\max(h_i,h_j,h_k)\) 在 \(h_i\) 和 \(h_k\) 中，直接分討

否則，我們要滿足的限制形如 \(h_i=k-j,h_j=k-i,h_k=j-i\) 或者 \(h_i=j-i,h_j=k-i,h_k=k-j\)，后一種是好處理的，前一種變換以下就是 \(h_i+i=-h_k+k,h_i-i=h_j-j,h_k+k=h_j+j\)，我們把 \(h_i+i\) 和 \(h_i-i\) 連一條邊，然后做一個三元環計數就行了，復雜度 \(\mathcal{O}(n\sqrt n)\)

AT_agc031_e [AGC031E] Snuke the Phantom Thief

flow。

太遺憾了，費用流流并不能直接建模形如 \(\sum x_i\le b_j\) 的限制，單純形也不能帶費用，咋辦？正難則反！考慮一條序列的情況，枚舉最后選了 \(k\) 個點，\(\le a_i\) 的點最多選 \(b_i\) 個的限制，相當于把這 \(k\) 個點從小到大排序之后，后 \(k-b_i\) 的點必須 \(>a_i\)，\(\ge a_i\) 的點最多選 \(b_i\) 個的限制，相當于把這 \(k\) 個點從小到大排序之后，前 \(k-b_i\) 個點必須 \(<a_i\)，容易擴展到二維的情況

那這樣就好建模了，我們令 \(x_i,y_i\) 表示按 \(x/y\) 排序后第 \(i\) 個點，令 \(in_i,out_i\) 為第 \(i\) 個可選的點的入點/出點，那么直接連邊：

\(S\rightarrow x_i\) 流量為 \(1\)，費用為 \(0\)
\(y_i\rightarrow T\) 流量為 \(1\)，費用為 \(0\)
\(in_i\rightarrow out_i\)，流量為 \(1\)，費用為 \(v_i\)
\(x_i\rightarrow in_j\)，流量為 \(1\)，費用為 \(0\)，滿足 \(j\) 在 \(i\) 的限制中
\(out_j\rightarrow y_i\)，流量為 \(1\)，費用為 \(0\)，滿足 \(j\) 在 \(i\) 的限制中

直接流就完了！邊數 \(\mathcal{O}(n^2)\)，點數 \(\mathcal{O}(n)\)，一共要流 \(n\) 次

8.17

P11993 [JOIST 2025] 遷移計劃 / Migration Plan

每個深度開一顆線段樹，維護 \(dfn\) 序區間和，每次線段樹合并完了查詢區間和就完了！

還有一種做法是，建一棵重構樹，對于每一個深度建一個點，第一種操作的時候，分別新開兩個點 \(dx,dy\)，\(dy\) 的兩個兒子存所有原來在深度 \(x,y\) 的節點，\(dx\) 是葉子；第二種操作，給 \(dep_u\) 新開一個點，然后在上面掛一個 \((u,w)\)；第三種操作，詢問重構樹中一個子樹內在一個 \(dfn\) 區間的權值和，離線二維數點即可

P12059 [THUPC 2025 決賽] I'm Here

把問題轉化成計數滿足以下條件的序列個數：

若 \(u\) 是 \(v\) 的祖先，則 \(u\) 不能在 \(v\) 之前出現
\(u\) 的位置小于等于 \(n-u+1\)

如果只有第一種限制，可以直接樹上背包，記 \(g_{u,i}\) 表示 \(u\) 被選且 \(u\) 子樹內選了 \(i\) 個的方案數

對于第二種限制，顯然是后綴最大值的限制更嚴格，所以我們不妨從大往小填數，于是記 \(f_{i,j,k}\) 表示填完了 \(\ge i\) 的數，選了 \(j\) 個，當前的后綴最大值在序列 \(k\) 的位置上，那么有下面幾種轉移：

不選 \(i\)，從 \(i+1\) 轉移過來，即 \(f_{i,j,k}\leftarrow f_{i+1,j,k}\)
選 \(i\)，讓 \(i\) 成為一個后綴最大值，枚舉他填的位置 \(k<x\le n-i+1\)，則有轉移 \(f_{i,j+1,x}\leftarrow f_{i+1,j,k}\)
選 \(i\)，\(i\) 不是后綴最大值，枚舉他子樹中填了 \(x\) 個數，則有轉移 \(f_{i,j+x,k}\leftarrow f_{i+siz_i,j,k}\times \binom{k-j}{x}\times g_{i,x}\)

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

CF1326F2 Wise Men (Hard Version)

QAQ

先容斥一手，記考慮計算滿足每個排列 \(p\) 所對應的集合 \(\left\{i|p_i=p_{i+1}\right\}\) 是我們要計算的集合 \(S\) 的超集的方案數 \(g(S)\)，則有最后的方案數 \(f(S)=\sum\limits_{S\subseteq T} (-1)^{|S|-|T|}g(T)\)，我們求出來 \(g\) 之后一個高維前綴和就可以了，現在考慮如何求 \(g\)

容易發現一個排列對應的集合 \(S\) 的方案數只和排列中的連續段的段長集合有關，比如 \(S=\left\{1,4,5,7\right\},n=8\) 時，其連續段集合為 \(\left\{1,2,2,3\right\}\)，顯然這個集合中所有元素的和恰好是 \(n\)，\(n\) 很小，我們可以考慮枚舉 \(n\) 的劃分，而題目中保證了 \(i\) 如果認識 \(j\) 則有 \(j\) 認識 \(i\)，于是可以建一張圖，每個長度為 \(i\) 連續段相當于圖上包含了 \(i\) 個點的鏈，于是我們現在要計數的，就是每一條鏈互相無交，圖上每個點都屬于一條鏈，且鏈長集合和給定集合相同的方案數，形式化一下，就是要求計數：

\[\sum_{p_1,p_2,\cdots,p_k}\left[|p_i|=a_i\right]\left[\forall i\ne j,p_i\cap p_j=\emptyset\right]\left[\bigcup_{i=1}^kp_i=U\right]\prod_{j=1}^kh(p_j) \]

其中 \(h(p)\) 為路徑集合為 \(p\) 對應的路徑條數，容易計算，三個艾弗森括號，因為有第一個的限制，后面兩個留著哪個都是等價的，所以我們可以把第二個去掉，即計數

\[\sum\limits_{p_1,p_2,\cdots,p_k}[|p_i|=a_i]\left[\bigcup_{i=1}^kp_i=U\right]\prod_{j=1}^kh(p_j) \]

如何把第一個限制去掉？我們采用經典方法，直接記錄一個 \(h'_{i,S}\) 表示 \(|S|=i\) 的 \(h(S)\)，即 \(h(S)\times[|S|=i]\)，那么原式就直接變成了

\[\sum\limits_{p_1,p_2,\cdots,p_k}\left[\bigcup_{i=1}^kp_i=U\right]\prod_{j=1}^kh'_{a_j,p_j} \]

這就是一個無交并卷積，把 \(h'\) 全都 \(FWT\) 了，直接點積起來就行了，由于我們要算的只有全集的答案，最后不需要再 \(IFWT\) 回來了，直接枚舉計算系數就可以了，最后總復雜度 \(\mathcal{O}(P(n)2^n+n^22^n)\)，其中 \(P(n)\) 為 \(n\) 的劃分數

P5206 [WC2019] 數樹

問題相當于給定/不給定兩個邊集 \(E_1,E_2\)，求 \(y^{n-|E_1\cap E_2|}\) 的和

op=0

用個哈希表存邊即可

op=1

容斥一下，有 \(f(S)=\sum\limits_{T\subseteq S}g(T)\)，可以子集反演得到 \(f(S)=\sum\limits_{T\subseteq S}\sum\limits_{P\subseteq T}(-1)^{|T|-|P|} f(P)\)，那我們要求的是

\[\sum_{E_2}\sum_{S}[E_1\cap E_2=S]y^{n-|S|} \]

推式子

\[\begin{aligned} & \sum_{E_2}\sum_{S}[E_1\cap E_2=S]y^{n-|S|}\\ &=\sum_{E_2}\sum_{T\subseteq E_1\cap E_2}\sum_{P\subseteq T}(-1)^{|T|-|P|}y^{n-|P|} \\ & =\sum_{T\subseteq E_1}g(T)\sum_{P\subseteq T}(-1)^{|T|-|P|}y^{n-|P|}\\ & =\sum_{T\subseteq E_1}g(T)y^{|T|-n}\sum_{P\subseteq T}(-y)^{|T|-|P|}\\ & =\sum_{T\subseteq E_1}g(T)y^{|T|-n}\sum_{k=0}^{|T|}\binom{|T|}{k}(-y)^{|T|-k}\\ & =\sum_{T\subseteq E_1}g(T)y^{|T|-n}(1-y)^{|T|}\\ \end{aligned} \]

\(g(T)\) 為包含邊集 \(T\) 的樹的個數，用一下經典結論就是 \(n^{k-2}\prod\limits_{i=1}^k a_i\)，原來的式子就是

\[\begin{aligned} &\sum_{T\subseteq E_1}n^{k-2}y^{k}(1-y)^{n-k}\prod_{i=1}^ka_i\\ &=\frac{(1-y)^n}{n^2}\sum_{T\subseteq E_1}\prod_{i=1}^k\frac{ny}{1-y} a_i \\ \end{aligned} \]

考慮 \(a_i\) 的組合意義，看成在連通塊內選擇一個點即可，于是直接設狀態 \(f,g\) 分別表示當前連通塊選了/沒選的貢獻，直接 dp 即可

op=3

推式子

\[\begin{aligned} & \sum_{E_1}\sum_{E_2}\sum_{T\subseteq E_1\cap E_2}\sum_{P\subseteq T} (-1)^{|T|-|P|}y^{n-|P|}\\ &= \sum_{T}g(T)^2y^{|T|-n}(1-y)^{|T|}\\ &=\frac{(1-y)^n}{n^4}\sum_{T} \prod_{i=1}^k\frac{n^2y}{1-y}a_i^2\\ \end{aligned} \]

考慮每個連通塊，直接 \(exp\) 就完了

P4002 [清華集訓 2017] 生成樹計數

純 maho 啊

考慮 Prüfer 序列，貢獻是

\[(n-2)!\prod a_i\sum_{j}\frac{1}{\prod d_i!}\prod a_i^{d_i}\prod_{i\ne j}(d_i+1)^m(d_j+1)^{2m} \]

考慮后面一個關于 \(\sum d_i\) 的生成函數，則構造

\[A(x)=\sum_{k}\frac{1}{k!}(k+1)^mx^k \]

\[B(x)=\sum_{k}\frac{1}{k!}(k+1)^{2m}x^k \]

則有

\[F(x)=\sum_{i}\frac{B(a_ix)}{A(A_ix)}\prod A(a_ix) \]

\[=\sum_{i}\frac{B(a_ix)}{A(a_ix)}\exp\left(\sum\ln A(a_ix)\right) \]

怎么算形如 \(\sum\limits_i F(a_ix)\)？展開一下：

\[\begin{aligned} & \sum_{i=1}^{n}F(a_{i}x)\\ &= \sum_{i=1}^{n}\sum_{j\ge 0}f_j(a_ix)^j\\ &= \sum_{j\ge 0}f_jx^j\sum_{i=1}^{n}a_i^j\\ \end{aligned} \]

就是要給 \(x^t\) 處的系數乘上 \(\sum\limits_{i=1}^n a_{i}^j\)，考慮

\[\sum_{k\ge 0} a_i^kx^k=\frac{1}{1-a_ix} \]

計算

\[P(x)=\sum\limits_{i=1}^n\frac{1}{1-a_ix} \]

的系數即可，設

\[Q(x)=\prod_{i=1}^{n}(1-a_ix) \]

\[P(x)=\sum\limits_{i=1}^n\prod\limits_{j\ne i}(1-a_jx) \]

\(Q(x)\) 可以分治乘，發現 \(P(x)=\frac{\textw0obha2h00}{\textw0obha2h00x}Q(x)\)，直接算就完了，復雜度 \(\mathcal{O}(n\log^2n)\)

8.18

模擬賽

T1

首先注意到如果 \(p\) 確定，答案就是 \(\sum(1-p_i)p_{i+1}\)，然后可以說明 \(p\) 單調不降，這個可以用排序不等式，最后答案肯定是一段前綴和一段后綴，這個可以歸納證明

又可以證明當 \(p_{i-1}+p_{i+1}< 1\) 的時候 \(p_i\) 要盡可能小，否則 \(p_i\) 要盡可能大，這樣我們的策略就出來了，直接做就是 \(\mathcal{O}(Tn\log n)\)

T2

枚舉 \(x\) 軸切的位置，然后就變成序列上的問題了，假如 \(y\) 坐標更大的那一刀切在 \(c\) 處，那另一刀可以選的位置肯定是一段區間，答案就是 \(\sum\limits_{c=0}^m R_c-L_c+1\)，插入一個區間 \([l,r]\) 的時候，其會限制 \(c\ge l\)，且對于 \(>r\) 的 \(c\) 的 \([L,R]\) 會對 \([l,r]\) 求交，如何維護？

首先在合法區間內有 \(L\) 單調不降，\(R\) 單調不增，于是可以二分

再套線段樹分治，可能和缺一分治差不多，復雜度 \(\mathcal{O}(n\log^2n)\)

T3

令根為 \(1\)，\(dep_u\) 為 \(dis(1,u)\)

首先注意到 \(lca(u,v)=dep_u\oplus dep_v\oplus dis(u,v)\)，這樣就有了一個 \(\mathcal{O}(n^2)\) 的做法，考慮一下 loj6669 那題的方法，我們也考慮去重剖增量，假設我們現在要加入 \(u\)，并且確定了 \(u\) 在 \(r\) 的子樹中，當我們插入 \(u\) 了再重剖一遍，接下來就是一些分類討論和構造：

詢問鏈尾與 \(u\) 的 \(dis\)，這樣可以得到 \(u\) 在那條重鏈上的 \(lca\)，如果這個 \(lca\) 沒出現過，可以二分出來這個 \(lca\) 的位置，插入并把 \(u\) 掛在這個 \(lca\) 的下面；否則 \(u\) 肯定在某個輕子樹內或者鏈底的子樹中，鏈底直接判掉，現在考慮如何找到他在哪個輕子樹中

首先強制讓 \(r\) 的輕兒子集合大小為偶數，如果為奇數我們可以加入重兒子，構造 \(v\) 為詢問 \(u\) 與 \(r\) 的輕兒子集合的答案，\(s=\bigoplus_{v\in son(r)} dep_{u}\oplus dep_{v}\)，這樣我們可以得到 \(v'=v\oplus s\)

若 \(v'=0\)，\(u\) 是 \(r\) 的輕兒子，直接掛在 \(r\) 下面即可
若 \(v'\in son(r)\)，\(u\) 在 \(v'\) 的子樹中，遞歸子問題即可
否則 \(v'=t\oplus r\)，\(t\) 是 \(r\) 的一個輕兒子， \(t\) 的子樹中含有 \(u\) 和 \(son(r)\) 中的一個，可以通過二分找到 \(t\) 包含 \(son(r)\) 的哪一個點

沒了，詢問次數 \(\mathcal{O}(n\log n)\)，時間復雜度 \(\mathcal{O}(n^2\log n)\)

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

刷新頁面返回頂部

oaigoaigilowoaigiy

8.9