做題筆記12

7.30

模擬賽

T1

CF878E

\(\mathcal{O}(nq)\) 的做法，可以從后往前掃一遍，如果當前的后綴和 \(>0\)，那么可以直接和前面的連起來，否則就把這個前綴和扔掉，那么掃描右端點，這時候每一段連起來之后就不會斷開，而且每次影響的段是一個后綴，用并查集維護就能 \(\mathcal{O}(n\alpha(n))\) 了

T2

閾值分治

首先把 \(A\) 和 \(B\) 都除以其最大公約數

當 \(B\) 比較小時，直接狀壓即可復雜度 \(\mathcal{O}(n2^B)\)

當 \(B\) 比較大時，考慮膜 \(B\) 分類，對于 \(1\sim B\)，讓 \(x\) 和 \((x+A-1)\bmod B+1\) 連邊，這樣最后會連出來一個環，然后從任意位置斷環成鏈，并把 \(i>B\) 的接在 \(i-B\) 后面，這樣就有了一個矩陣狀物，每一列之間差 \(B\)，所以最多有 \(\left\lceil\frac{n}{B}\right\rceil\) 列，列與列之間的轉移可以高維后綴和，每一列之間相鄰元素的轉移也可以高維前綴和狀物，首列和尾列不好轉移，直接最外層枚舉其狀態即可，這樣可以做到 \(\mathcal{O}(n4^{\left\lceil\frac{n}{B}\right\rceil})\)

可以平衡到 \(\mathcal{O}(n2^{\sqrt{2n}})\)

T3

agc049f zak加強版

8.1

CF1178G The Awesomest Vertex

是我喜歡的區間加 \(x\) 區間一次函數 \(max\)，直接 KTT。

絕對值直接拆開用兩個線段樹維護就行了，復雜度 \(\mathcal{O}(n\log ^3 n)\)

P8987 [北大集訓 2021] 簡單數據結構

如果 \(a_i\) 全都一樣，我們可以輕松維護區間推平和區間加法，因為每次操作之后肯定不改變序列的單調性，我們又發現，被取過 \(min\) 的在以后都有單調性，這個結論可以隨便分討得到，那我們現在要做的就是每次找到被取 \(min\) 的元素，并將其刪除，發現這就是一個一次函數全局最大值的問題，直接使用 KTT 維護，因為是全局操作，所以這里 KTT 的復雜度是 \(\mathcal{O}(n\log^2n)\)，總復雜度 \(\mathcal{O}n\log^2 n\)

8.2

#8229. 棧

2025scz聯考5.2T2

#971. Binary Search Tree

先換維，把 \(1\) 操作變成在 \(l\sim r\) 時刻會出現一個 \(w\)，\(2\) 操作就是 \(x\) 時刻保留前 \(i\) 項 \(a\) 的答案

現在去考慮那棵二叉搜索樹，如果我們加入數的順序是 \(a_1,a_2,a_3,...\)，發現有祖孫關系的點，祖先出現的時刻必定更靠前，那我們把其出現的時刻和權值再換維，就變成了一顆小根笛卡爾樹，我們要求的就是某個點到根鏈的權值之和

笛卡爾樹上，若 \(u\) 是 \(v\) 的祖先，則滿足 \(a_u=\min\limits_{i=u}^v a_i\)，所以我們詢問的時候，只需要找出來某個位置左邊所有的后綴 \(\min\) 和其右邊所有的前綴 \(\min\)，可以直接用單側遞歸線段樹維護

CF1303G Sum of Prefix Sums

淀粉質，發現每個路徑對于其他的路徑的貢獻是一個一次函數，李超樹即可，復雜度 \(\mathcal{O}(n\log^2n)\)

#228. 基礎數據結構練習題

因為加法和開根不能同時做，于是考慮一些均攤復雜度的東西，當區間 \(\max-\min\le 1\) 且 \(\sqrt\max-\sqrt\min \le 1\)的時候，開根號變成了區間加，這時候直接打標記即可，否則暴力遞歸，其他的操作正常做，可以說明這個復雜度是 \(\mathcal{O}(n\log\log V+q\log \log V\log n)\) 的

我們定義一個節點的勢能 \(\varphi(k)=\log\log(\max-\min)\)，這里的對數都是以 \(2\) 為底，如果我們對一個區間暴力遞歸開根號，若新的狀態為 \(\varphi'(k)\)，則肯定有 \(\varphi'(k)\le \varphi(k)-1\)，首先有 \(\forall x,y\in \mathbb{N}, x>y\ge 1,(\sqrt x-\sqrt y)^2\le(\sqrt x-\sqrt y)(\sqrt x+\sqrt y) =x-y\) 也就有 \(\sqrt x-\sqrt y\le \sqrt{x-y}\)，所以有 \(\varphi'(k)=\log\log(\sqrt x-\sqrt y)\le\log\log\sqrt{x-y}=\log\frac{\log (x-y)}{2}=\varphi(k)-1\)，所以每遞歸一個區間都會至少使得一個區間的勢能減一，而每次開根操作最多需要暴力遞歸線段樹上的 \(\mathcal{O}(\log n)\) 個區間，初始的勢能總和為 \(\mathcal{O}(n\log\log V)\)，區間加的時候會花費 \(\mathcal{O}(\log n)\) 的時間使最多 \(\mathcal{O}(\log n)\) 個區間的勢能增加 \(\log\log V\)，那么總的復雜度就是 \(\mathcal{O}(n\log\log V+q\log\log V\log n)\)

#6029. 「雅禮集訓 2017 Day1」市場

記 \(f(x)=x-\left\lfloor\frac{x}w0obha2h00\right\rfloor\)，如果一個區間滿足 \(f(\max)=f(\min)\)，那么對這個區間進行修改的差值是一樣的，因為 \(\forall x<y,y-x\ge\left\lfloor \frac{y}w0obha2h00\right\rfloor-\left\lfloor\frac{x}w0obha2h00\right\rfloor\Leftrightarrow y-\left\lfloor \frac{y}w0obha2h00\right\rfloor\ge x-\left\lfloor\frac{x}w0obha2h00\right\rfloor\)，就有 \(f\) 滿足單調性

和上面那個題類似，定義勢能函數 \(\varphi(k)=\log(\max-\min)\)，則有 \(\varphi'(k)\le\log \frac{\max-\min}{2}=\varphi(k)-1\)，其他的部分幾乎一樣

8.3

模擬賽

T1

\(\varphi(x)=x\prod\limits_{i=1}^{k}\frac{p_k-1}{p_k}\)，其中 \(p_1\sim p_k\) 是 \(x\) 的 \(k\) 個不同的質因子

那直接枚舉每一個質數，二位數點就做完了，復雜度是 \(\mathcal{O}(n\frac{\log^2n}{\log\log n})\)

T2

發現每一個環都包含一個二元環，直接模擬費用流就完了

T3

直接割。

P10016 [集訓隊互測 2023] 虹

看看避看看特看看賽看看特

首先注意到 \(19901991^2\equiv1\bmod 20242024\)，于是 \(w\) 和 \(z\) 都只需要計算其膜 \(2\) 的值就行了，給每個詢問開一個 std::bitset 保存 \(w\) 的值，那在線和離線就沒區別了

現在考慮怎么取出來 \([l,r]\) 這個區間的 bitset，考慮分塊，若 \(l,r\) 不在同一塊，我們可以對于塊兩側的點，讓他往左/右掃，同時維護一個 bitset，表示當前掃過的點的到根鏈的并，到最后只需要把他們的 lca 的父親到根鏈上的點都異或掉，然后詢問 \(l,r\) 變成詢問 \([l,b],[b+1,r]\)，這樣做就是均攤 \(\mathcal{O}(n\sqrt n)\) 的，如果 \(l,r\) 在同一塊，由于數據隨機，這種情況大概有 \(\mathcal{O}(\sqrt n)\) 個，暴力掃就行了，也是 \(\mathcal{O}(\sqrt n)\) 的

\(z\) 的貢獻怎么算？直接爆搜所有的質因子，當 \(p^c\) 變成 \(p^{c+1}\) 的時候，所有滿足 \(p^{c+1}|x\) 的 \(x\) 與當前數的 \(\gcd\) 都會乘上 \(p\)，搜完了差不多只有 \(4\times 10^7\) 次

最后復雜度 \(\mathcal{O}(n\sqrt n+\frac{nq}{w})\)

P11369 [Ynoi2024] 彌留之國的愛麗絲

哎呦我滴媽你別笑

詢問分塊，對于每一塊，把關鍵點和關鍵邊都摘出來，然后縮點，并 dfs 一遍處理出來每一個關鍵點能到達的關鍵點的集合，詢問的時候，使用一個壓位 bfs 的技巧，具體來說，用一個 bitset 存已經走過的點的集合，再用一個 bitset 存走過的點的鄰域，每次 _Find_first() 就行了

復雜度 \(\mathcal{O}(\frac{q}{B}(n+m)+\frac{q}{B}(n+m)\frac{B}{w}+q\frac{B^2}{w})\)，取 \(B=(n+m)^{\frac{1}{3}}w^{\frac{1}{3}}\) 可以平衡到 \(\mathcal{O}(\frac{q(n+m)}{w}+\frac{q(n+m)^{\frac{2}{3}}}{w^{\frac{1}{3}}})\)

8.4

P6789 寒妖王

學習了擬陣。

若令獨立集 \(\mathcal{I}\) 為圖上所有基環樹森林的邊集族，\(E\) 為圖上的一個邊集，那么 \(M=(E,\mathcal{I})\) 是一個擬陣，求解最大權值基環樹森林，我們可以在擬陣上貪心，具體來說就是把所有邊權排序之后一個一個加入并判斷是否合法

從邊權大的往小掃，考慮每一條邊的貢獻，若 \(u\) 所在連通塊為 \(S\)，\(v\) 所在連通塊為 \(T\)，則會有這幾種情況有貢獻：

\(S\) 和 \(T\) 都是一棵樹
\(S\) 是一棵樹，\(T\) 是一棵基環樹
\(S\) 是一棵基環樹，\(T\) 是一棵樹
\(S=T\) 且 \(S\) 是一棵樹

基環樹不太好數，正難則反，考慮數這條邊沒有貢獻的情況，于是記 \(f_S\) 表示保留前若干大的邊，點集 \(S\) 是一個連通塊的方案數，\(g_S\) 則是 \(S\) 是一個樹的方案數，發現答案其實就是

\[f_S-g_S+\sum_{u\in T,v\in S/T} (f_T-g_T)(f_{S/T}+g_{S/T}) \]

算概率的話，若一條邊和 \(S\) 有交集，那么這條邊就會對 \(S\) 產生貢獻，記這樣的邊的個數為 \(c_S\)，最后給方案數除以 \(2^{C_S}\) 就行了

轉移也是簡單的，有

\[ f_S\leftarrow f_{S}+\sum_{u\in T,v\in S/T} f_{T}f_{S/T} \]

\[ g_S\leftarrow \sum_{u\in T,v\in S/T} g_{T}g_{S/T} \]

沒了，復雜度是 \(\mathcal{O}(m3^n)\)

P5247 【模板】動態圖連通性

HdLT，不寫了，下面視 \(n,m\) 同階

給每個邊一個等級，把這個等級限制在 \(\log n\)，令 \(G_i\) 為保留所有 \(\ge i\) 的權值的圖，則有 \(G_{i+1}\subseteq G_i\)，同時讓 \(|G_i|\) 始終小于等于 \(2^{\log n-i}\)，再給每個這樣的圖用一個極大的生成樹 \(F_i\) 來刻畫其連通性，這個生成樹可以用 ETT 維護，也有 \(F_{i+1}\subseteq F_{i}\)，同時也有 \(F_i=G_i\cap F_0\)

link

把這條邊放到 \(G_0\) 里，判斷 \(u,v\) 是否在一個連通塊里并嘗試連接即可

query

在 \(F_0\) 中詢問 \(u,v\) 是否連通

cut

找到 \((u,v)\) 的等級 \(l_{(u,v)}\)，如果是他不是樹邊，直接刪掉就行，如果他是樹邊，則會斷成兩個連通塊 \(T_u\) 和 \(T_v\)，不妨設 \(|T_u|\le|T_v|\)，嘗試在 \(l_{(u,v)}\) 這一層中找到可以連接 \(T_u,T_v\) 的非樹邊，遍歷 \(T_u\)，可以發現這些非樹邊要么連向 \(T_v\) 要么連向 \(T_v\)，否則就不是極大的生成樹，如果找到了一條連向 \(T_u\) 的邊，把他升級，否則就是找到了一條新的樹邊，直接修改即可

復雜度的話，由于 \(F_i\le 2^i\)，則有 \(|T_u|\le 2^{i-1}\)，直接升級就是沒問題的，每條邊最多升級 \(\log n\) 次，ETT 的操作是 \(\mathcal{O}(\log n)\) 的，那復雜度就是 \(\mathcal{O}(n\log^2n)\)

AT_iroha2019_day4_l ...好きです

線段樹分治，把絕對值拆了，維護 \(\frac{1}{v_i}x-\frac{x_i}{v_i}\) 的一次函數，全局排序后可以線性維護凸包，雙指針線性算答案，復雜度 \(\mathcal{O}(q\log q)\)

P4234 最小差值生成樹

掃描線，類似 LCT 維護 MST。

uoj462新年的小黃鴨

首先有 \(\mathcal{O}(n^2)\) 的暴力 dp，每次枚舉鏈尾的葉子，然后貢獻是一個毛毛蟲狀物，直接線性計算即可

發現難算的是 \(\log_2\)，但是每個點的這個值的貢獻只會變化 \(\mathcal{O}(\log n)\) 次，倍增出來會變化的那些祖先，自底向上做，用線段樹維護所有葉子的區間加，區間 \(\min\)，復雜度 \(\mathcal{O}(n\log^2n)\)

P7952 [??OI R1] 天動萬象

這不是我們 P9999 嗎

用平衡樹維護每一條重鏈，再用并查集把重合的點縮起來，每個點看似會跳 \(\mathcal{O}(\log n)\) 次輕邊，但是一個點作為輕兒子貢獻到父親的時候會和其他所有的輕邊合在一起，因此這些兒子我們只需要考慮其中的一個，他的子樹大小一定 \(\le \frac{siz_u}{2}\)，那么一條輕邊想產生貢獻，節點數至少砍半，那復雜度就是 \(\sum\limits_{i=0}^{n} \frac{n}{2^i}=\mathcal{O}(n)\)，再加上 FHQ 的復雜度是 \(\mathcal{O}(n\log n)\)

P7124 [Ynoi2008] stcm

我操

直接按 \(dfn\) 序分治

發現一個重要的性質，如果兩個子樹的 \(dfn\) 區間相交，那么他們一定互相包含！

直接做就完了，操作次數 \(\mathcal{O}(n\log n)\)

P4783 【模板】矩陣求逆

把這個矩陣右邊拼上一個單位矩陣，然后把左半邊的矩陣高斯消元消成單位矩陣，由于這是個線性變換，如果原來的矩陣是 \(A\)，這個線性變換是 \(B\)，相當于求得了 \(AB=\mathcal{I}\)，那么有 \(B=A^{-1}\)，這個線性變換只和行相關，那右邊的單位矩陣就變成了 \(\mathcal{I}B=B\)，右邊這個矩陣就是原矩陣的逆

矩陣沒有逆的充要條件就是不滿秩

8.5

#8547. Whose Land?

掃描線，從左往右掃右端點，維護能覆蓋到每個點的最大的編號，最后查詢全局比某個數大的值的個數，鄰域覆蓋可以在 \(2k\) 個 bfs 序區間上做顏色段均攤，然后再開一個數點用的數據結構，復雜度 \(\mathcal{O}(nk\log n)\)

#6669. Nauuo and Binary Tree

先問出來所有點的深度，然后考慮從上往下問出來深度前 \(i\) 的二叉樹，如果當前要問第 \(i\) 層，考慮一手鏈剖分，從根節點開始，找到他所在重鏈深度最大的第 \(i-1\) 層的點 \(y\)，讓他和第 \(i\) 層的所有點問一下，由于 \(dep_x+dep_y-dep_{lca_{x,y}}=dis(x,y)\)，所以我們可以問出來 \(y\) 和所有第 \(i\) 層的點的 \(lca\) 的深度，而 \(y\) 在重鏈上，這條鏈上不存在深度相同的點，那么 \(lca\) 也就出來了，由于是二叉樹，我們又知道 \(y\) 在這個 \(lca\) 的一側，那另一個點肯定在另一側，令 \(y\) 變成另一側的兒子接著做就完了，這樣每個點最多問 \(\mathcal{O}(\log n)\) 次，總復雜度 \(\mathcal{O}(n\log n)\)

P9382 [THUPC 2023 決賽] Freshman Dream

這個式子顯然可以寫成一些關于 \(b_{i,j}\) 的線性方程組，也就是 \(\sum\limits_{k} a_{i,k}\times b_{k,j}=a_{i,j}\times b_{i,j}\)，發現每一列 \(b\) 的方程組是獨立的，于是可以每一列每一列的考慮

現在考慮第 \(k\) 列，他的系數矩陣形如

\[\left[ \begin{array}{cccc|c} a_{1,1}-a_{1,k} & a_{1,2} &\cdots & a_{1,n}& 0 \\ a_{2,1} & a_{2,2}-a_{2,k} & \cdots &a_{2,n}&0 \\ \vdots & \vdots & \ddots & \vdots&0\\ a_{n,1}& a_{n,2}& \cdots&a_{n,n}-a_{nk} &0\\ \end{array} \right] \]

通過求異或線性基的方式把他消成上三角矩陣，為了方便，我們再把他消成正交矩陣，或者直接高斯-約旦消元

因為數據隨機，所以這個矩陣的自由元不會太多？直接搜出來這些自由元的解，再回代即可，這樣我們可以得到一列的所有解，跑一個背包看是否有解，求方案的時候再倒著掃一遍就行了，復雜度 \(\mathcal{O}(\frac{n^4}{w})\)

注：\((n-1) \times n\) 矩陣秩為 \(n?1?k\) 的概率可以這樣估計，考慮這些向量都在對應的空間中的概率為 \(\frac{1}{2kn}\)，而這樣的空間數量和零空間數量相同，后者可以用零空間的任意張成組來簡單估計上界為 \(\binom{2n}{k}\)，因此是 \(O(\frac{1}{k!})\) 級別的。

CF156D Clues

Prüüüüüüüüüüüüüüüüüüüüüüüüüüüfer序列，Cayley 公式

Prüfer 序列

我們可以構造一個有 \(n\) 個點的有標號樹到一個大小為 \(n-2\) 的序列的雙射，構造這個雙射只需要：找到編號最小的葉子，將其父親的編號加入序列中，把他刪掉，一直重復這個過程直到最后剩下兩個點，最后得到的序列就是 Prüfer 序列

怎么證明這是個雙射？我們可以從一個 Prüfer 序列反推出來一棵樹，也很簡單，具體來說，就是找到第一個沒出現的點，這個點肯定是我們在生成 Prüfer 序列時第一個被刪掉的葉子，那他的父親的編號也就是 Prüfer 序列的第一項，同時把這一項刪掉，遞歸做下去就好了

Cayley 公式

\(k\) 個連通塊，總點數為 \(n\)，則添加 \(k-1\) 條邊使得整個圖連通的方案數為

\[n^{k-2}\prod_{i=1}^{k}s_i \]

其中 \(s_i\) 為第 \(i\) 個連通塊的大小

現在考慮另一個問題，對于 \(k\) 個點的完全圖，每個點的度數為 \(d_i\)，其生成樹個數是什么？考慮其 Prufer 序列，則應該有方案數等于

\[ \binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1} \]

把這個 \(k\) 個點換成 \(k\) 個連通塊，總方案數就變成了

\[ \sum_{d_i\ge 0,\sum_{i=1}^{k}d_i=2k-2}\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\times\prod_{i=1}^{k} s_i^{d_i} \]

考慮多元二項式定理

\[(x_1+x_2+\cdots+x_m)^n=\sum_{c_i\ge 0,\sum_{i=1}^{m}c_i=n}\binom{n}{c_1,c_2,\cdots,c_m}\times \prod_{i=1}^{m}x_i^{c_i} \]

爽換元，令 \(e_i=d_i-1\)，顯然有 \(\sum_{e_i}=k-2\)，原式就是

\[ \sum_{e_i\ge 0,\sum_{i=1}^ke_i=k-2}\binom{k-2}{e_1,e_2,\cdots,e_k}\times\prod_{i=1}^{k} s_i^{e_i+1} \]

等于

\[ \left(s_1+s_2+\cdots+s_k\right)\times \prod_{i=1}^k s_i \]

也就是

\[n^{k-2}\times \prod_{i=1}^{k}s_i \]

CF917D Stranger Trees

矩陣樹定理

如果是樹邊，就把其鄰接矩陣的權值設為 \(x\)，否則設為 \(1\)，這樣直接矩陣樹最后多項式的系數就是答案，直接拉插，最后復雜度 \(\mathcal{O}(n^4)\)

AT_arc145_e [ARC145E] Adjacent XOR

首先把 \(a_i\leftarrow a_i\oplus a_{i-1}\) 看成一個差分操作，那么把操作序列倒過來就相當于 \(b_i\leftarrow \bigoplus_{j=1}^{i}b_j\)，也就是把前綴和轉成差分，最終的判定條件就變成了通過操作若干個 \(\forall i\le k,b_i\leftarrow \bigoplus_{j=1}^i b_j\)，使最終 \(b_i=a_i\)

\(a_i\oplus b_i\) 顯然要滿足是 \([1,i-1]\) 的 \(b_j\) 的一個線性組合，這是一個有解的必要條件，下面通過構造方案來說明他是充分的

\(b\) 數組并不好直接構造，考慮從前往后把他塞到一個線性基里面，把每個 \(b_i\) 表示成一組基底的線性組合，把這個線性組合記作 \(c_i\)，那我們對 \(c_i\) 操作是和 \(b_i\) 沒有區別的，這樣有用的值就沒那么多了，考慮從后往前構造出 \(a_i\)，因為從前往后會使得前面構造出來的 \(a\) 改變，在構造 \(a_i\) 時，我們肯定也不想操作 \([i+1,n]\)，那只有在操作 \(i\) 的時候會使得 \(b_i\) 的值改變，使其成為 \(i-1\) 的前綴和，那我們也就是向通過操作使得 \(\bigoplus_{j=1}^{i-1}b_j=a_i\)

對每一位考慮，記第 \(i\) 位第一次出現的位置為 \(pos_i\)，那么在 \([1,pos_i-1]\) 的位置，第 \(i\) 位都沒出現過，也就是說當我們操作 \(pos_i+1\) 時，只會改變 \(b_{pos_i+1}\) 第 \(i\) 位的值，那在最后的前綴和中也只有這一位會改變，當 \(i\) 變小時，\(pos_i\) 也遞減，從大到小考慮每一位，構造出來的方案就是合法的！

總操作次數 \(\mathcal{O}(n\log V)\)

8.6

模擬賽

T1

【模板】平衡樹

T2

~~不會。~~

注意到相交的區間可以變成包含的，形成一個樹形結構，考慮深度的限制，可以樹形 dp

T3

不會。

P13497 【MX-X14-T7】墓碑密碼

666

首先我們可以只考慮出現了奇數次的 \(S_i\)，因為出現了偶數次異或和就是 \(0\)，再乘上一個組合數就行了，具體來說，答案就是

\[\sum_{i=0}^{|S|} dp_i\binom{\frac{n-i}{2}+|S|}{|S|} \]

現在考慮算 \(dp_i\)，考慮其生成函數 \(F(x,y)\)，\(x\) 那一維的乘法為 \(\text{xor}\) 卷積，\(y\) 那一維的乘法為加法卷積，寫下來 \(F\)

\[F(x,y)=\sum_{u\in T}[x^u]\prod_{b\in S}(1+x^by) \]

把后面的連乘式 FWT 一下得到

\[\begin{aligned} & [x^u]FWT(\prod_{b\in S}(1+x^by))\\ & =[x^u]\prod_{b\in S}FWT\left(1+x^by \right)\\ & =\prod_{b\in S}\left(1+(-1)^{|b\cap u|}y\right)\\ \end{aligned} \]

再 IFWT 回去

\[\begin{aligned} & [x^u]\prod_{b\in S}(1+x^by) =[x^u]IFWT\left(\prod_{b\in S}\left(1+(-1)^{|b\cap u|}y\right)\right)\\ & =\frac{1}{2^m}\sum_{v=0}^{2^m-1}(-1)^{u\cap v}[x^v]\prod_{b\in S}\left(1+(-1)^{|b\cap u|}y\right)\\ & =\frac{1}{2^m}\sum_{v=0}^{2^m-1}(-1)^{|u\cap v|}\prod_{b\in S}\left(1+(-1)^{|b\cap v|}y\right)\\ \end{aligned} \]

那最后得到的式子就形如

\[\frac{1}{2^m}\sum_{v=0}^{2^m-1}\sum_{u\in T}(-1)^{|u\cap v|}\prod_{b\in S}\left(1+(-1)^{|b\cap v|y}\right) \]

后面那個關于 \(y\) 的多項式顯然只有 \(|S|\) 種，只和 \(|b\cap v|\equiv 1\bmod 2\) 的個數有關，這些多項式可以 \(\mathcal{O}(|S|^2)\)，前面的系數也只和 \(|u\cap v|\equiv 1\bmod2\) 的個數有關，形式化的，我們要求

\[ca_u=\sum_{v\in S}\left[|u\cap v|\equiv 1\bmod 2\right] \]

\[cb_u=\sum_{v\in T}\left[|u\cap v|\equiv 1\bmod 2\right] \]

現在只需要快速算出來 \(ca_u\) 和 \(cb_u\)，考慮當 \(u\leftarrow u+1\) 的時候，其影響相當于反轉了一段二進制后綴！而 \(|S|=128\)，可以考慮用倆 ull 存下來每一個 \(a\in S\) 和當前的 \(u\) 的 \(\mod 2\) 的值，用一個 std::bitset 存下來就行，每次反轉一段二進制后綴對于一個 std::bitset 的影響顯然是獨立的，那把這個影響存下來，每次異或一下就可以了，最后再調用 count() 就能算出來 \(ca\) 和 \(cb\) 啦

視 \(|S|,|T|\) 同階，總復雜度 \(\mathcal{O}(\frac{2^m|S|}{w}+|S|^2+q|S|)\)，代碼不寫了

P5073 [Ynoi Easy Round 2015] 世上最幸福的女孩

全局修改，直接把這個修改的權值從小到大排序，所有數都減掉 \(v_1\)，這樣就變成全局加正數，區間最大子段和，是我喜歡的最大子段和，直接 KTT 維護，復雜度 \(\mathcal{O}(n\log^2n+q\log n)\)

P13523 [KOI 2025 #2] 序列與查詢

可以和上面那個一樣做，但是有單 \(\log\) 分治做法

具體來說，就是要求 \(\max\limits_{l,r}\left\{s_{r}-s_{l}+(r-l)\times x\right\}\)，這是一個一次函數的形式，考慮求出來他的凸包

分治，每個分治區間維護三個凸包，\(A=\left\{(s_i,i)\right\},B=\left\{(-s_i,-i)\right\},C=\left\{(s_j-s_i,j-i)\right\}\)，在區間 \((L,R)\) 時，令 \(A_{L,R}=\max\left(A_{L,mid},A_{mid+1,r}\right)\)，\(B_{L,R}=\max\left(B_{L,mid},B_{mid+1,r}\right)\)，\(C_{L,R}=\max\left(C_{L,mid},C_{mid+1,r},B_{L,mid}+A_{mid+1,r}\right)\)，其中加法是閔可夫斯基和，凸包從下往上合并的時候都是有序的，所以閔可夫斯基和還有凸包取 \(\max\) 都可以線性，復雜度 \(\mathcal{O}(n\log n)\)

8.7

開車

8.8

模擬賽

T1

保留三個邊，直接倍增就完了

T2

草泥馬

求

\[ \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n \varphi(ij)\mu(jk)\sigma_0(ik) \]

有 \(\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))},\mu(ij)=\mu(i)\mu(j)[i\perp j],\sigma_0(ij)=\sum_{a|i}\sum_{b|j}[a\perp b]\)

那么原式就是

\[\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\mu(j)\mu(k)[j\perp k]\sum_{a|i}\sum_{b|k}[a\perp b] \]

把這三個 \(\gcd\) 的東西全都莫反掉，我們的目標是最后不出現形如 \(\mu(ij)\) 的東西，先把 \(\gcd(i,j)\) 莫反掉，有

\[\begin{aligned} & \frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\\ & = \varphi(i)\varphi(j)\left(\sum_{x=1}^n[\frac{i}{x}\perp \frac{j}{x}]\frac{x}{\varphi(x)}\right)\\ & = \varphi(i)\varphi(j)\left(\sum_{x=1}^n\sum_{dx|i,dx|j}\mu(d)\frac{x}{\varphi(x)}\right)\\ & = \varphi(i)\varphi(j)\left(\sum_{d=1}^n\sum_{d|x,x|i,x|j}\mu\left(\frac{x}w0obha2h00\right)\fracw0obha2h00{\varphi(d)}\right)\\ \end{aligned} \]

帶回原式

\[\sum_{x=1}^n\sum_{d|x}\mu\left(\frac{x}w0obha2h00\right)\fracw0obha2h00{\varphi(d)}\sum_{x|i}\sum_{x|j}\sum_{k=1}^n\varphi(i)\varphi(j)\mu(j)\mu(k)[j\perp k]\sum_{a|i}\sum_{b|k}[a\perp b] \]

\(\sum_{d|x}\mu\left(\frac{x}w0obha2h00\right)\fracw0obha2h00{\varphi(d)}\) 這個東西只和 \(x\) 有關，記其為 \(F(x)\)，可以 \(\mathcal{O}(n\log n)\) 求，原式就變成了

\[\sum_{x=1}^nF(x)\sum_{x|i}\sum_{x|j}\sum_{k=1}^n\varphi(i)\varphi(j)\mu(j)\mu(k)[j\perp k]\sum_{a|i}\sum_{b|k}[a\perp b] \]

現在莫 \([j\perp k]\)

\[\begin{aligned} & [j\perp k]\\ & = \sum_{y|j,y|k}\mu(y)\\ \end{aligned} \]

帶回原式

\[\sum_{x=1}^nF(x)\sum_{y=1}^n\mu(y)\sum_{x|i}\sum_{\text{lcm}(x,y)|j}\sum_{y|k}\varphi(i)\varphi(j)\mu(j)\mu(k)\sum_{a|i}\sum_{b|k}[a\perp b] \]

接著莫 \([a\perp b]\)

\[\begin{aligned} & \sum_{a|i}\sum_{b|k}[a\perp b]\\ & = \sum_{a|i}\sum_{b|k}\sum_{z|a,z|b}\mu(z)\\ \end{aligned} \]

帶回原式

\[\sum_{x=1}^nF(x)\sum_{y=1}^n\mu(y)\sum_{z=1}^n\mu(z)\sum_{z|a}\sum_{z|b}\sum_{\text{lcm}(a,x)|i}\sum_{\text{lcm}(x,y)|j}\sum_{\text{lcm}(b,y)|k}\varphi(i)\varphi(j)\mu(j)\mu(k) \]

把后面的東西分一下類

\[\sum_{x=1}^nF(x)\sum_{y=1}^n\mu(y)\sum_{z=1}^n\mu(z)\left(\sum_{\text{lcm}(x,y)|j}\varphi(j)\mu(j)\right)\left(\sum_{z|a}\sum_{\text{lcm}(a,x)|i}\varphi(i)\right)\left(\sum_{z|b}\sum_{\text{lcm}(b,y)|k}\mu(k)\right) \]

記 \(A(x)=\sum_{x|k}\varphi(k)\mu(k),B(x)=\sum_{x|k}\phi(k),C(x)=\sum_{x|k}\mu(k)\)，都可以 \(\mathcal{O}(n\log n)\) 求出來，再記 \(B_2(x,y)=\sum_{y|a}B(\text{lcm}(a,x)),C_2(x,y)=\sum_{y|b}C(\text{lcm}(b,x))\)，那原式就是

\[\sum_{x=1}^n\sum_{y=1}^n\sum_{z=1}^nF(x)\mu(y)\mu(z)A\left(\text{lcm}(x,y)\right)B_2\left(x,z\right)C_2\left(y,z\right) \]

發現這里 \(x,y,z\) 三個變量滿足 \(\mu(x)=\mu(y)=\mu(z)\ne 0\)，\(\mu(x)\ne 0\) 是因為前面枚舉 \(x\) 的倍數的 \(\mu\) 不等于 \(0\)，而且也有他們之間的 \(\text{lcm}\le n\)，然后可以套用 P4619 [SDOI2018] 舊試題的做法，具體來說，把 \(\text{lcm}\le n\) 的連邊，有一個粗略的上界可以說這樣的邊是 \(\mathcal{O}(n\log^2 n)\) 的，在 \(n=50000\) 時候差不多是 \(3.4\times 10^5\)，記這個為 \(m\)，然后做三元環計數狀物就行了，復雜度是 \(\mathcal{O}(m\sqrt m)\)，有點卡常

關于邊數的結論，考慮下面這個證明：

\[\begin{aligned} & S=\sum_{i=1}^n\sum_{j=1}^n[\text{lcm}(i,j)\le n]\\ & =\sum_{i=1}^n\sum_{j=1}^n[ij\le n\times\gcd(i,j)]\\ & =\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^n[\gcd(i,j)=d][ij\le nd]\\ & =\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^n[\gcd\left(\frac{i}w0obha2h00,\frac{j}w0obha2h00\right)=1][ij\le nd]\\ & =\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^n\sum_{k=1}^n\mu(k)[kd|i][kd|j][ij\le nd]\\ & =\sum_{k=1}^n\mu(k)\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\frac{n}{kd}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{kd}\right\rfloor}[j\le \frac{n}{ik^2d}]\\ & \le\sum_{k=1}^n\mu(k)\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\frac{n}{kd}\right\rfloor}\frac{n}{ik^2d} \end{aligned} \]

最后面那個系數是一個調和級數狀物，即

\[\sum_{i=1}^{\left\lfloor\frac{n}{kd}\right\rfloor}\frac{n}{ik^2d}=\mathcal{O}\left(\frac{n}{k^2d}\log\frac{n}{kd}\right) \]

那就有

\[S=\sum_{k=1}^n\mu(k)\sum_{d=1}^n\mathcal{O}\left(\frac{n}{k^2d}\log\frac{n}{kd}\right)=\mathcal{O}(n\log n\sum_{k=1}^n\frac{\mu(k)}{k^2}\sum_{d=1}^{n}\frac{1}w0obha2h00)=\mathcal{O}(n\log^2 n) \]

其中用到了一個放縮

\[\sum_{k=1}^n\frac{\mu(k)}{k^2}\le\sum_{k=1}^{n}\frac{1}{k^2}=\mathcal{O}(1) \]

因為 \(\mu(k)\le 1\)，而右邊那個求和是經典的巴塞爾問題，有 \(\sum_{k=1}^{\infty}\frac{1}{k^2}=\frac{\pi^2}{6}\)，這樣我們就得到了一個相當松的上界，loj 上 LCA 有更緊一點的證明，不詳說了

T3

歐耶，類類的歐

\(S_1\) 顯然具有單調性，而且 \(V_1\) 肯定是盡可能的大，所以不妨令 \(v_1\leftarrow a_1+a_n\)，這樣就沒有環了，二分 \(S_1\)，\(S_1\) 合法的條件是什么呢？首先要滿足 \(\sum S_i\le m\)，而且最后一票投 \(S_1\) 之前必須得滿足 \(S_1\) 是最優的，即 \(\frac{V_1}{S_1}\ge \frac{V_i}{S_i+1}\)，這里盡量讓 \(S_i\) 比較小去滿足 \(\le m\) 的限制，所以可以讓 \(S_i\) 取到下界，即 \(S_i=\left\lceil\frac{V_iS_1-V_1}{V_1}\right\rceil=\left\lceil\frac{V_iS_1}{V_1}\right\rceil-1\)

觀察一下 \(\sum S_i=\sum \left\lceil\frac{V_iS_1}{V_1}\right\rceil-1\)，發現除以 \(V_1\) 上取整上面的項的和是定值，也就是

\[\sum V_i=\sum a_i+\sum v_i \]

于是考慮貪心，讓 \(V_iS_1\) 盡量向上接近 \(V_1\) 的倍數，設 \(r_i=V_iS_1\bmod V_1\)，貪心就是讓 \(r_i\) 盡可能的大，特殊的，視 \(0\) 最大

顯然當 \(\sum r_i\) 最大的時候 \(\sum S_i\) 是最小的，直接從前往后做，如果當前的 \(r_i\) 沒有取到最大，那么把他調整到最大，后面的肯定不劣

于是現在要求的就是一個形如

\[\max_{i=0}^{n}\left\{\left(ki+b\right)\bmod p\right\} \]

的問題，我們采用類歐的方法進行計算！經典的，設

\[f(a,b,c,n)=\max_{i=0}^{n}\left\{\left(ai+b\right)\bmod c\right\} \]

\[g(a,b,c,n)=\min_{i=0}^{n}\left\{\left(ai+b\right)\bmod c\right\} \]

終止條件就是當 \(a=0\) 或 \(n=0\)

當 \(a>c\) 或 \(b>c\) 時，有

\[\begin{aligned} & f(a,b,c,n)=\max_{i=0}^n\left\{\left(\left(\left\lfloor\frac{a}{c}\right\rfloor c+a\bmod c\right)i+\left(\left\lfloor\frac{b}{c}\right\rfloor c+b\bmod c\right)\right)\bmod c\right\}\\ & = \max_{i=0}^n\left\{\left(\left(a\bmod c\right)i+\left(b\bmod c\right)\right)\bmod c\right\}\\ & = f(a\bmod c,b\bmod c,c,n)\\ \end{aligned} \]

\(g\) 也同理

當 \(a<c\) 時，考慮怎么交換 \(a\) 和 \(c\)，我們先把模 \(c\) 變成除以 \(c\) 下取整，即

\[\begin{aligned} & f(a,b,c,n)=\max_{i=0}^{n}\left\{\left(ai+b\right)\bmod c\right\}\\ & =\max_{i=0}^n\left\{ai+b-\left\lfloor\frac{ai+b}{c}\right\rfloor c \right\}\\ \end{aligned} \]

然后去枚舉 \(j=\left\lfloor\frac{ai+b}{c} \right\rfloor\)，由于是問的 \(\max\)，用 \(j\) 的下界去反演出 \(i\) 的上界，即

\(j=\left\lfloor\frac{ai+b}{c}\right\rfloor=\left\lceil\frac{ai+b-c+1}{c} \right\rceil\Rightarrow j\ge\left\lceil\frac{ai+b-c+1}{c} \right\rceil\Leftrightarrow j\ge \frac{ai+b-c+1}{c}\Leftrightarrow i\le \frac{cj+c-b-1}{a}\Leftrightarrow i\le\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor\)

經典的，我們記 \(m=\left\lfloor \frac{an+n}{c}\right\rfloor\)，則有

\[\begin{aligned} & \max_{i=0}^n\left\{ai+b-\left\lfloor\frac{ai+b}{c}\right\rfloor c \right\}\\ &= \max_{j=0}^m\left\{a\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor+b-cj\right\}\\ &=c-1- \min_{j=0}^m\left\{cj+c-b-1-a\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor\right\}\\ & = c-1-\min_{j=0}^m\left\{\left(cj+c-b-1\right)\bmod a\right\}\\ \end{aligned} \]

這時候出現了一個問題，就是當 \(j=m\) 的時候，\(i\) 的上界如果取到 \(\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor\) 就爆爆爆了，所以 \(j=m\) 的時候我們特判一下，直接取 \(i=n\) 就好了，那最后的式子就是

\(f(a,b,c,n)=\max\left\{c-1-g(c,c-b-1,a,m-1),\left(an+b\right)\bmod c\right\}\)

同理計算 \(g\)，用 \(j\) 的上界反演出來 \(i\) 的下界，即

\(j=\left\lfloor\frac{ai+b}{c}\right\rfloor\Rightarrow j\le \frac{ai+b}{c}\Leftrightarrow i\ge\frac{cj-b}{a}\Leftrightarrow i\ge\left\lceil\frac{cj-b}{a}\right\rceil=\left\lfloor\frac{cj+a-b-1}{a}\right\rfloor\)

則有

\[\begin{aligned} &\min_{i=0}^n\left\{ai+b-\left\lfloor\frac{ai+b}{c}\right\rfloor c\right\}\\ &=\min_{j=0}^m\left\{a\left\lfloor\frac{cj+a-b-1}{a}\right\rfloor+b-cj\right\}\\ &=a-1-\max_{j=0}^m\left\{cj-b-1-a\left\lfloor\frac{cj-b-1}{a}\right\rfloor\right\}\\ &=a-1-\max_{j=0}^m\left\{\left(cj-b-1\right)\bmod a\right\}\\ \end{aligned} \]

和上面的類似，當 \(j=0\) 的時候，\(i\) 的下屆可能會小于零，同樣特判，那 \(i\) 的范圍會變成 \([1,n]\)，我們還要把他變成 \([0,\lim]\) 的一個形式，具體來說，就是

\[\max_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\left\{\left(cj-b-1\right)\bmod a\right\}=\max_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\{\left(c(j+1)-b-1\right)\bmod a\right\}=\max_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\{\left(cj+c-b-1\right)\bmod a\right\} \]

那么最后的式子就是

\(g(a,b,c,n)=\min\left\{a-1-f(c,c-b-1,a,m-1),b\right\}\)

這樣就做完了，類歐一個 \(\log\) 二分一個 \(\log\)，總復雜度 \(\mathcal{O}(n\log^2m)\)

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

刷新頁面返回頂部

oaigoaigilowoaigiy

7.30

模擬賽

T1

T2

T3

8.1

8.2

8.3

模擬賽

T1

T2

T3

8.4

link

query

cut

8.5

Prüfer 序列

Cayley 公式

8.6

模擬賽

T1

T2

T3

8.7

8.8

模擬賽

T1

T2

T3

公告