6.2

CF1864H Asterism Stream

好題啊

首先把要求的期望變成 \(\sum_{i=1}^{n-1}f_i\)，其中 \(f_i\) 為經(jīng)過 \(i\) 的概率，那么有顯然的轉(zhuǎn)移

考慮偶數(shù)的情況，如果 \(2|\frac{i}{2}\)，我們把這個式子展開，那么會有 \(f_{i}=\frac{1}{2}f_{i-1}+\frac{1}{4}f_{\frac{i}{2}-1}+\frac{1}{4}f_{\frac{i}{4}}\)，這時候繼續(xù)考慮 \(\frac{i}{4}\) 是偶數(shù)的情況，這樣一直展開，我們最終會得到

發(fā)現(xiàn)對于 \(\text{lowbit}\) 相同的數(shù)，他們的轉(zhuǎn)移也是相同的，那可以直接考慮維護出來 \(\forall j\in [0,\log V],A_{i,j}=f_{\left\lfloor\frac{i}{ 2^j}\right\rfloor }\)，為了方便，記 \(f_1=\frac{1}{2}f_0=1\)，那么就有 \(f_0=2\)，這樣我們每次的轉(zhuǎn)移就是 \(A_i=A_{i-1}\times F_{\text{lowbit}(i)}\)，這樣我們直接預(yù)處理出來 \(F\) 的矩陣然后直接做是 \(\mathcal{O}(T\log^5 n+\log^3n)\) 的，可以進一步預(yù)處理出來 \(G_i=\prod\limits_{j=1}^{2^i}F_{\text{lowbit}(j)},H_i=\prod\limits_{j=1}^{2^{i+1}-1}F_{\text{lowbit}(j)}\)，則有 \(G_0=H_0=F_0\)，那也不難得到轉(zhuǎn)移 \(G_{i}=H_{i-1}\times F_{i},H_{i}=G_{i}\times H_{i-1}\)，這樣最后在對于 \(n\) 二進制位上是 \(1\) 的位置把 \(G\) 乘起來，就能把復(fù)雜度做到 \(\mathcal{O}(T\log^3n+\log^4n)\)

P9563 [SDCPC 2023] Be Careful 2

糙擬嗎

考慮容斥，那么答案就是 \(\sum\limits_{S} (-1)^{|S|}\times f(S)\)，其中 \(S\) 可以是空集，\(f(S)\) 為所有包含 \(S\) 的正方形的面積之和

如果直接枚舉點集，復(fù)雜度是 \(\mathcal{O}(2^n)\) 的，但是如果這個點集中有一個點，加入它和刪除它之后，\(f(S)\) 不變，那這個點集不會造成貢獻，因為我們集合大小加一減一會抵消掉，所以我們真正有效的點集，必須滿足其內(nèi)部沒有多余的點，考慮枚舉 \(x_1\) 和 \(x_2\)，我們的點集大小最多為 \(4\)，包括了 \(x_1,x_2\) 以及 \(x\) 在 \([x_1,x_2]\) 之間，\(y_1,y_2\) 的前驅(qū)后繼，我們可以從后往前掃并用一個鏈表維護出來

對于計算 \(f(x,y,z,w)\) 即必須包含 \((x,z),(y,w)\) 這個矩形的正方形個數(shù)，我們直接去枚舉邊長 \(d\)，發(fā)現(xiàn)是一個關(guān)于 \(d\) 的四次的分段函數(shù)，可以簡單 \(\mathcal{O}(1)\) 維護

這樣就沒了，復(fù)雜度為 \(\mathcal{O}(n^2)\)

AT_arc138_f [ARC138F] KD Tree

好題

首先考慮如何計數(shù)不會算重，我們可以直接 dp 操作序列，看其是否合法，但在這道題中并不好刻畫，于是考慮直接 dp，并去掉重復(fù)的答案，或者我們對于所有答案點列相同的操作序列，強制在某個代表元處統(tǒng)計貢獻

直接 dp，可以記 \(f_{l,r,u,d}\) 為某個矩形區(qū)域內(nèi)的答案。考慮 \(f_{1,n,1,n}\) 的轉(zhuǎn)移，我們轉(zhuǎn)移時肯定是枚舉水平或者豎直切一刀，比如橫著切一刀 \(i\)，那就會把整個矩形分成 \(f_{1,i-1,1,n}\) 和 \(f_{i,n,1,n}\)，然后給答案加上 \(f_{1,i-1,1,n}\times f_{i,n,1,n}\) 的貢獻，但是這樣會記重，如果出現(xiàn)一個 \(j<i\)，他會把矩形分成 \([1,j),[j,i),[i,n]\) 三部分，而答案點列肯定是先 \([1,j)\) 再 \([j,i)\) 再 \([i,n]\)，也就是說先切 \(j\) 再切 \(i\)，或者先切 \(i\) 再切 \(j\)，實際上是同一種方案

還有一種算重的可能，就是如果先橫著切一刀再豎著切一刀，如果他們分出來的四個象限中，第而象限和第四象限有一個象限中沒有點，那么先橫再豎和先豎再橫，也是本質(zhì)相同的方案

上面的算重條件說明，如果令 \(S_i\) 為切掉 \(i\) 后，先走的那部分點集，則 \(i,j\) 算重時，必須有 \(S_i\subseteq S_j\) 或者 \(S_j\subseteq S_i\)，這樣的條件有偏序性，所以我們可以讓 “字典序” 最小的方案被統(tǒng)計到，于是考慮構(gòu)造一個字典序 \((x,1),(y,1),(x,2),(y,2),...,(x,k),(y,k)\)，其中 \((*,i)\) 表示在 \(*\) 方向上的 \(i\) 處切一刀，這個序列滿足 \(\forall S_i\subseteq S_j,rk_i\le rk_j\)，其中 \(rk\) 為其字典序，于是可以 dp 出來字典序最小的方案了

dp 時，我們枚舉 \(i\)，那么所有的 \(rk_j<rk_i\)，都有可能會算重，其會算重的充要條件是 \(S_j\subseteq S_i\)，那這時候 \(f_{1,i-1,1,n}\leftarrow f_{1,i-1,1,n}-f_{1,j-1,1,n}\times f_{j,i-1,1,n}\) 就能把重復(fù)計數(shù)的部分去掉了，最后給答案加上 \(f_{1,i-1,1,n}\times f_{i,n,1,n}\) 的貢獻即可，這樣枚舉矩形是 \(\mathcal{O}(n^4)\) 的，轉(zhuǎn)移需要枚舉 \(i\) 和 \(j\)，總的時間復(fù)雜度就是 \(\mathcal{O}(n^6)\)，直接記搜再狀壓一下會好寫很多

6.3

昨晚失眠了

P10013 [集訓(xùn)隊互測 2023] Tree Topological Order Counting

wow

直接 dp，記 \(f_{u,i}\) 為當前考慮 \(u\) 這個節(jié)點，他之前有 \(i\) 個點的方案，那么有轉(zhuǎn)移

其中 \(C\) 為 \(fa_u\) 子樹中去掉 \(u\) 子樹的拓撲序

計算子樹內(nèi)拓撲序，可以直接 \(g_u=\frac{(siz_u-1)!}{\prod\limits_{v\in son(u)}siz_v!}\prod\limits_{v\in son(u)}g_v\)

這樣對于每一個 \(u\)，我們自底向上 dp，復(fù)雜度為 \(\mathcal{O}(n^3)\)

我們只有在最后會把 \(b_i\) 的貢獻乘上去，而且 \(u\) 和 \(fa_u\) 之間的轉(zhuǎn)移與其他的節(jié)點無關(guān)，于是可以考慮把 \(b_i\) 放在 dp 初值中，然后自頂向下 dp，只需要把轉(zhuǎn)移反過來就好了，最后 \(u\) 處的答案就是 \(f_{u,0}\times g_u\)，這樣復(fù)雜度是 \(\mathcal{O}(n^2)\)

CF1466H Finding satisfactory solutions

666

題目中還有一句每一個 \(b\) 都有唯一的 \(a\) 沒翻譯出來，這個還挺重要的，考慮如何對一個 \(b\) 找出來她所對應(yīng)的唯一的 \(a\)，我們連邊 \(i\rightarrow b_{i,1}\)，這樣會連出來一個內(nèi)向基環(huán)樹森林，而且顯然所有的環(huán)上的邊必須在 \(i\rightarrow a_i\) 中出現(xiàn)，這樣我們可以刪掉所有的環(huán)上的點以及他們的入邊，然后對于那些出邊被刪掉的非環(huán)上點來說，連邊 \(i\rightarrow b_{i,2}\)，一直這樣做，我們得到的就是 \(a\) 的置換環(huán)

那我們可以把 \(a\) 的那些置換環(huán)拉出來，然后再加入一些邊，對于 \(i\)，向所有排名比 \(a_i\) 小的點連邊，這時候一個合法的 \(b\)，不能存在一個環(huán)，環(huán)上的邊包含新加入的邊，考慮對這個進行計數(shù)

我們把 \(a\) 的環(huán)縮起來之后，只剩下新加入的邊，而這些邊肯定要形成一個 DAG，于是可以考慮做 DAG 計數(shù)，經(jīng)典的，我們?nèi)ッ杜e入度為 \(0\) 的點集，有轉(zhuǎn)移

其中 \(e(S,T)\) 表示 \(S\) 向 \(T\) 連邊的貢獻，如果一個點的出度為 \(deg_u\)，那么他的貢獻就是 \(deg_u!(n-deg_u-1)!\) 我們可以直接對于每一個點枚舉連邊數(shù)量，如果他要向大小為 \(s\) 的集合連邊，那他的貢獻就是 \(g(s)=\sum\limits_{i=0}^{s}\binom{s}{i}\times i! \times (n-i-1)!\)，那大小為 \(s\) 的點集向大小為 \(t\) 的點集連邊，其貢獻就是 \(g(t)^s\)，這樣可以 \(\mathcal{O}(1)\) 計算出來 \(e(S,T)\)，直接轉(zhuǎn)移就能做到 \(\mathcal{O}(3^{cyc})\)，\(cyc\) 是環(huán)的個數(shù)

然而我們關(guān)心的其實并不是某個環(huán)有沒有被選，所以對于大小相同的環(huán)，我們可以把他縮到一起，那可以記錄一個狀態(tài) \((c_1,c_2,...,c_{k})\) 表示長度為 \(1\sim k\) 的環(huán)的個數(shù)，這樣狀態(tài)數(shù)就只有 \(1440\) 了

直接轉(zhuǎn)移即可，復(fù)雜度 \(1440^2\times n\)

Random Variables

考慮 dp 出現(xiàn)次數(shù) \(\le k\) 的答案為 \(\text{ans}(k)\)，那現(xiàn)在就是有 \(n\) 個球，\(m\) 個盒子，要求每個盒子中放的球不超過 \(k\)，記 \(f_{i,j}\) 為考慮了前 \(i\) 個球，放到 \(j\) 個盒子的方案數(shù)，考慮容斥計算 \(f_{i,j}\)

則有 \(f_{i,j}=f_{i-1,j}\times j-f_{i-k-1,j-1}\times\binom{i-1}{k}\times j\)，前者是隨便填的方案，后者是欽定這個球放的盒子必須 \(>k\)，這樣 \(m-j\) 最多只有 \(\frac{n}{k+1}\) 種取值，直接 dp 就能做到 \(\mathcal{O}(n^2\log n)\)

【UNR 3】鴿子固定器

首先可以按大小排序，然后我們從右往左掃，并維護一個小根堆來計算牢固度之和，如果右端點被彈出來就停止

有結(jié)論，入堆的點的總和是 \(\mathcal{O}(nm)\) 的

考慮在掃 \(i\) 時 \(j\) 被入堆，對于所有 \(v_j\ge v_i\) 的 \((i,j)\)，每一個 \(i\) 最多對應(yīng)了 \(m\) 個 \(j\)，因為多了會讓 \(i\) 出堆，對于所有 \(v_j<v_i\) 的 \((i,j)\)，每一個 \(j\) 最多對應(yīng)了 \(m\) 個 \(i\)，否則 \(j\) 不會被入堆

這樣可以每次二分出來可以入堆的那個點，復(fù)雜度 \(\mathcal{O}(nm\log n)\)

6.4

36年？

今天做不了一點，模擬賽打不動，不想補題了

6.19

馬孔多在下雨

6.20

打成依托士了

模擬賽

T1

幽默

如果我們把每個關(guān)鍵點的距離 \(\text{dis}(i,j)\) 全都拉出來然后跑最小生成樹，那 \((u,v)\) 的答案就是最小生成樹上的最大邊權(quán)，求這個最小生成樹可以自然的想到 prim，直接跑一邊 dij 就做完了

T2

呃呃

首先他要求的這個東西是有可合并性的（暫時不會證明），也就是說最后選取的那 \(k\) 個點所構(gòu)成的點集 \(ans_S\)，滿足 \(ans_{S\cup T}\in ans_{S}\cup ans_{T}\)， 如果從合并兩集合的直徑角度來看還是挺自然的，\(q\) 比較小，直接線段樹，現(xiàn)在我們要做的是如何合并兩個大小為 \(k\) 的點集，實際上也是簡單的，我們考慮 \(l=1,r=n\) 的做法，只需要拉出來直徑上的某個端點，定其為根，做一遍長鏈剖分就可以了，我們要合并兩個點集，可以把虛樹建出來再定根長剖，這樣每次合并的復(fù)雜度是 \(\mathcal{O}(k\log k)\)，那總的復(fù)雜度就是 \(\mathcal{O}(nk\log k+qk\log n\log k)\)，按道理來說是過不了的，但是加一些剪枝可以卡過去，或者棧式線性建虛樹，然后用 nth_element（這個東西是期望線性的），可以做到 \(\mathcal{O}(nk+qk\log n)\)

正解咋做？考慮每 \(k\) 個元素分一塊，塊之間的答案存在 ST 表里面，這樣我們的復(fù)雜度就變成了 \(\mathcal{O}(\frac{n}{k}k\log n\log k+qk\log k)\) 也就是 \(\mathcal{O}(n\log n\log k+qk\log k)\)，當然我們可以用剛才所述的技巧把 \(\log k\) 都去掉以做到更優(yōu)

T3

好題啊

考慮 dp，記 \(f_{l,r}\) 為區(qū)間 \([l,r]\) 中的答案，而我們的轉(zhuǎn)移只需要考慮區(qū)間最大值，設(shè)其位置為 \(x\)，那么有

于是考慮建笛卡爾樹，這是我們發(fā)現(xiàn)，我們要詢問的肯定被包含在笛卡爾樹上的一個節(jié)點所表示的區(qū)間內(nèi)，這個節(jié)點其實就是 \(rs_x\) 或者 \(ls_x\)，這兩種情況對稱，那么現(xiàn)在要做的就是對于某一個 \([l,r]\) 求 \(f_{l,i},i\in [l,r]\)，考慮將其從左右兒子合并上來

然而這樣單次轉(zhuǎn)移還是線性的，考慮如何優(yōu)化，發(fā)現(xiàn)我們最后肯定只有一段前綴是取到后者，而一段后綴是取前者，因為不難歸納證明，我們 \(f_{l,r}\) 關(guān)于 \(r\) 的增量肯定是小于等于 \(h_x\) 的！這樣我們只需要二分出來那個位置，做區(qū)間覆蓋為一個一次函數(shù)/區(qū)間加就行了，寫線段樹二分的話容易做到 \(\mathcal{O}((n+q)\log n)\)

6.21

模擬賽

太幽默了

T1

純難

考慮 \(o=1\) 怎么做，我們首先任選一個點，如果這個點正好是 \(A/B/C\) 中的一個，我們的處理是簡單的，那不妨假設(shè)這個點不是關(guān)鍵點，那么可以問出來他的鄰域，記其為 \(S\)，同時記其補集為 \(T\)，此時肯定滿足 \(A\in S\)，我們發(fā)現(xiàn)和 \(S\) 有連邊的點并不重要，只需要找到任意一個與 \(S\) 沒有連邊的點就行了，而這個點就是 \(C\) ，我們直接雙指針的去掃，如果當前 \(S_i\) 和 \(T_j\) 沒有連邊， 那么 i++，否則 j++，這樣我們最后 \(T\) 剩下的就是 \(C\)，因為我們在掃的過程中，肯定會在 \(S\) 中碰到 \(A\)，這樣就把所有與 \(A\) 有連邊的點刪掉了，詢問次數(shù)是線性的

類似的，我們可以處理 \(o=2\)，任意選一個非關(guān)鍵的點，他肯定和 \(A\) 或者 \(B\) 有連邊，不妨讓與他有連邊的那個是 \(A\)，我們把這個點的鄰域摳出來記作 \(T_1\)，其補集記作 \(T_2\)，這樣我們可以把 \(T_1\) 和 \(T_2\) 做一遍上面的過程，找到 \(S_2\) 中與 \(A\) 無連邊的點，這個點要么是 \(D\)，要么是 \(S_2\) 中的一個點，\(D\) 的情況容易處理，只需要考慮其在 \(S_2\) 的情況

把我們的第一個點的鄰域記為 \(X\)，第二個點的鄰域記為 \(Y\)，其他點記作 \(Z\)，那么我們可以確定的是 \(A\in X,B\in Y,D\in Z\)，我們可以做一個三指針，如果 \(X_i\) 和 \(Z_k\) 沒連邊，令 i++，如果 \(Y_j\) 和 \(Z_k\) 沒連邊，令 j++，有邊就 k++，但是這樣我們可能會把 \(A\) 或者 \(B\) 去掉，太不牛了

這里有一個巧妙的方法，我們交替問 \(X\) 和 \(Y\)，這樣如果遇到當前 \(Z_k\) 與 \(X_i\) 有連邊，可以把這期間去掉的 \(Y_j\) 再加回來，而 \(Z_k\) 與 \(Y_j\) 有連邊也同理，這樣我們可以以 \(p\) 的代價問出來 \(2p\) 個點，這樣詢問次數(shù)還是線性的

T2

純難

首先觀察到答案就是讓求 \(\sum\limits 2^ic_i=n-1,\forall c_{i\ne 0}>0,c_{i-1}>0\) 的 \(c\) 的權(quán)值之和，其中 \(2^i\) 的權(quán)值為 \(f(i)=\sum\limits_{j=0}^{i}\binom{i}{j}\times \frac{1}{A+j+1}\)

有一個結(jié)論，對于一個二進制最高位為 \(2^e\) 的數(shù)，若滿足 \(\sum\limits 2^{p_i}=n\)，把這些 \(p_i\) 排序，肯定存在一段后綴的滿足 \(\sum\limits_{i>k} 2^{p_i}=2^e\)，對于二進制最低位，也有類似的結(jié)論

這樣我們可以直接逐位考慮，每次去掉最高位，這樣要求的就變成了從 \(c_l2^l\sim c_r2^r\) 組合出 \(2^i\) 的權(quán)值和，并且滿足 \(c_i>0\)，可以直接考慮一個區(qū)間 DP，記 \(h_{i,l,r}\) 為上述問題的答案，我們枚舉轉(zhuǎn)移中點 \(2^{m}\)，那么有 \(h_{i,l,r}\leftarrow h_{i-1,l,mid} \times h_{i-1,mid+1,r}+h_{i-1,l,mid} \times h_{i-1,mid,r}\)

這樣再 DP 可以做到單次 \(\log^3n\)

考慮一個 meet in the middle，我們預(yù)處理出來前后 \(15\) 位的答案，最后只需要 \(\log n\) 枚舉合并位置就行了，具體的，設(shè) \(f_{s,i}\) 表示最高位為 \(2^i\)，組合出來 \(s\) 的權(quán)值和，\(g_{s,i}\) 表示最低位為 \(2^i\)，組合出來 \(s\) 的權(quán)值和，這樣直接轉(zhuǎn)移是 \(\mathcal{O}(\sqrt n log^2n)\) 的

最后的復(fù)雜度就是 \(\mathcal{O}(\sqrt n \log^2n+T\log n+\log^4n)\)

6.22

[AGC052B] Tree Edges XOR

經(jīng)典

把邊權(quán)轉(zhuǎn)成點權(quán)，也就是令 \(w_{u,v}=a_u\oplus a_v\)，考慮每次操作進行了什么，發(fā)現(xiàn)是形如 \((a_u\oplus a_v)\oplus a_u\rightarrow a_u,(a_u\oplus a_v)\oplus a_v\rightarrow a_v\)，也就是相當于交換了 \(a_u\) 和 \(a_v\)

如果我們能確定一個不動點，那么可以直接從不動點自頂向下做，把第一顆樹上的所有點同時異或上一個權(quán)值 \(x\)，其邊權(quán)是不會發(fā)生改變的，于是存在合法方案，當且僅當存在一個 \(x\)，使得存在一個排列 \(p\)，使得 \(\forall i,a_{p_i}\oplus x=b_i\)

如何求解這個 \(x\) ？其應(yīng)該滿足 \(\oplus_{i=1}^{n}(a_i\oplus x)=\oplus_{i=1}^{n}b_i\)，由于 \(n\) 是奇數(shù)，可以求得 \(x=\oplus_{i=1}^{n}a_i\oplus b_i\)，只需要判斷是否存在 \(p\) 使得 \(a_{p_i}\oplus x=b_i\) 就行了，可以直接排序，再判斷每個位置是否相同就行了

CF1458D Flip and Reverse

？

把 \(0\) 當成 \(-1\)，把 \(1\) 當成 \(+1\)，考慮其前綴和序列 \(s\)，發(fā)現(xiàn)執(zhí)行一次操作相當于把 \(s_l\) 到 \(s_{r-1}\) 反轉(zhuǎn)，那么我們給 \(s_i\rightarrow s_{i+1}\) 建一條有向邊， 每次就相當于選擇一個環(huán)并全部反向，考慮到我們每次反轉(zhuǎn)的時候，一定滿足 \(s_{l-1}=s_r\)，那么 \(s_{l-1}\) 到 \(s_l\) 和 \(s_r\) 到 \(s_{r-1}\) 的邊是具有相同端點的，那么圖上每個點之間的邊數(shù)是不變的 ，要求最后走出的路徑經(jīng)過了每一條邊且只能經(jīng)過一次，也就是字典序最小的歐拉路徑

把圖上的邊都變成無向邊，那每一條歐拉路徑都對應(yīng)了一個反轉(zhuǎn)得到的字符串

直接貪心，如果當前在 \(x\)，那么我們下一步想走到 \(x-1\)，這時候如果有 \(x\rightarrow x+1\) 的邊，必須要滿足存在 \(x-1\rightarrow x\) 的邊才行，這樣跑一邊就行了，復(fù)雜度線性

[JOISC 2020] カメレオンの戀

如果我們詢問每一對 \((X_i,Y_j)\)，倘若答案是 \(1\)，說明要么是 \(X_i\) 喜歡 \(Y_j\) 但是 \(Y_j\) 不喜歡 \(X_i\)，要么是 \(Y_j\) 喜歡 \(X_i\) 但是 \(X_i\) 不喜歡 \(Y_j\)，要么滿足 \(X_i\) 和 \(Y_j\) 顏色相同，那么我們給 \(X_i\) 和 \(Y_j\) 連一條邊，最后會有一些三度點和一度點，一度點的連邊就是答案，三度點也容易分討出答案

問題在于如何快速找到每一條邊，如果能確定一個集合是否與某個點有連邊，那么我們可以二分這個集合來找到那條邊，而這個集合要滿足其中間是不存在邊的，于是考慮求出一個極大的獨立集，記一個集合 \(S\)，如果當前點 \(x\) 與 \(S\) 無連邊，那么把 \(x\) 加入 \(S\) 中，最后肯定滿足 \(S\) 中的點互相無連邊

記 \(S\) 的補集為 \(T\)，這里我們肯定有 \(3|S|\ge |T|\)，因為每個點的度數(shù)不超過三，那么我們對于 \(T\) 中的每個點，都可以通過與 \(S\) 進行二分，找到所有的 \(T\) 與 \(S\) 之間的連邊，而 \(S\) 的點之間是互相沒有連邊的，我們要求的就只剩下 \(T\) 中的連邊了，直接遞歸做，這樣詢問次數(shù)是 \(T(n)=n+T(\frac{3}{4}n)=4n\)，而我們每個點要問 \(3\log n\) 次，這樣總的詢問次數(shù)就是 \(\mathcal{O}(n\log n)\)

CF2057G Secret Message

？！

為了滿足 \(|S|\le \frac{1}{5}(s+p)\) 的限制，我們可以構(gòu)造五種方案，如果這五種方案的總和為 \((s+p)\)，那么一定存在一種方案滿足 \(|S|\le \frac{1}{5}(s+p)\)

考慮直接給這個矩陣進行染色 \(c_{i,j}=i+2j\bmod 5\)，對于每一種染色方案，我們會有一些點不被覆蓋到，這些點肯定在邊界上，而這些點邊界外的那個點肯定滿足于當前顏色相同，我們直接選中這個點，于是可以證明所有染色方案的代價總和為 \(s+p\)

【UR28】環(huán)環(huán)相扣

好題

首先有結(jié)論，若 \(x>y\)，則有 \((x \bmod y)+y\le x\)，這個不難證明，又發(fā)現(xiàn)我們每一個 \((i,j,k)\)，不妨設(shè) \(a_i>a_j>a_k\)，其貢獻肯定是 \(a_i \bmod a_k+ a_j+a_k\) 或者 \(a_i \bmod a_j+a_j\bmod a_k+a_k\)，所以 \((i,j,k)\) 的貢獻肯定滿足 \(\ge a_j+a_k\)，且 \(\le a_i+a_j\)，那么此時我們可以說明，\(i\) 和 \(j\) 肯定會取到一個區(qū)間內(nèi)的最大和次大

證明：如當前取到了 \((n,n-1,n-2)\)，其下確界大于等于 \(a_{n-1}+a_{n-2}\)，那么對于任意一個 \((i,j,k)\)，如果選擇第一種方案，有 \(a_{i} \bmod a_k+a_j+a_k\le a_i+a_j\)，如果 \(i\le n-1\)，肯定不優(yōu)，若 \(i=n\)，不等號兩邊都有一個 \(a_j\)，其貢獻是獨立的，肯定是取 \(j=n-1\) 最大，選擇第二種方案，則有 \(a_i \bmod a_k + a_j \bmod a_k+a_k\le min\left\{a_i,2a_j-1\right\}\)，若 \(i\le n-1\)， 其上確界肯定小于等于 \(a_{n-1}+a_{n-2}\)，若 \(i=n\)，則 \(j\) 如果不取到 \(n-1\)，就會有 \(2a_{n-2}-1<a_{n-1}\)，肯定不優(yōu)

形式化的，記 \(F([l,r],i)\) 表示 \(\max\limits_{k\in [l,r]}\left\{a_i\bmod a_k+a_k\right\}\)，這樣計算答案就是 \(F([l,r],i)+a_j\) 或者 \(F([l,r],j)+(a_i\bmod a_j)\) 其中 \(i\) 是最大值的位置，\(j\) 是最小值的位置，考慮計算 \(F([l,i],i)\) 和 \(F([i,r],i)\)，以 \(F([l,i],i)\) 為例，對于每一個 \(i\)，從右往左掃，同時維護一個當前的最大值（因為最大值不能取到），這一部分是容易處理的，復(fù)雜度可以做到 \(\mathcal{O}(n^2+q)\)

考慮優(yōu)化求 \(F([l,i],i)\) 的這個過程，這里給出結(jié)論，若出現(xiàn)了兩個 \(k\) 滿足 \(a_k> \frac{a_i}{2}\)，我們可以立馬在第二個 \(k\) 的位置停止掃描，證明不難，因為有兩個 \(k\)，那必然有一個是可以取的，其肯定滿足 \(a_i\bmod a_k+a_k=a_i\)，可以取到 \(F([l,i],i)\) 的上界。這樣再掃描，總次數(shù)是 \(\mathcal{O}(n\log V)\) 級別的，復(fù)雜度 \(\mathcal{O}(n\log V+q\log n)\)

又有結(jié)論，如果在掃描過程中有某個 \(k\) 在 \([k+1,i-1]\) 中有兩個位置 \(u,v\) 滿足 \(a_u,a_v\ge 2a_k\)，那么這個 \(k\) 是無用的，這很顯然

這個結(jié)論和上面的結(jié)論向契合，我們可以設(shè)計出一個掃描次數(shù)線性的算法

直接維護一個棧，存仍然可能有用的那些 \(k\)，同時對這些 \(k\) 記一個 \(del_k\) 表示已經(jīng)有多少 \(p>k,a_p\ge 2a_k\)

我們從左往右掃當前的 \(a_i\)，再從右往左掃棧中的數(shù)維護出來 \(F([l,i],i)\)，如果棧頂?shù)臄?shù) \(a_x\) 滿足 \(2a_x>a_i\)，那么計數(shù)器 \(cnt++\)，如果棧頂?shù)臄?shù)滿足 \(2a_x\le a_i\)，那么 \(del[x]++\)，如果某一個時刻滿足 \(cnt=2\)，直接停止掃描，最后我們把 \(del\) 的值等于二的數(shù)從棧中直接刪掉，這樣每個數(shù)最多會被掃描到 \(4\) 次，這樣總復(fù)雜度能做到 \(\mathcal{O}(n+q\log n)\)

Flower's Land 2

？

構(gòu)造三個隨機可逆矩陣 \(M_0,M_1,M_2\)，對于 \(i \equiv 0\pmod 2\) 的位置，令 \(A_i=M_{s_i}\)，否則令 \(A_i=M_{s_i}^{-1}\)，那一個區(qū)間最后能消除掉的充要條件就是 \(\prod\limits_{i=l}^r A_i=I\)，總復(fù)雜度為 \(\mathcal{O}(n\log n k^3)\)，其中 \(k\) 是矩陣大小

[Ynoi2013] D2T2

我操

考慮固定值域做區(qū)間信息合并，莫隊加線段樹可以做到 \(\mathcal{O}(n\sqrt m \log n)\)，太慢了，這個算法在詢問的時候復(fù)雜度只有 \(\mathcal{O}(q\log n)\)，我們事實上可以接受詢問復(fù)雜度更高的做法來平衡復(fù)雜度

考慮序列分塊，這時候我們每次要求的就是一個區(qū)間塊內(nèi)值域在 \([L,R]\) 中的答案，信息合并是 \(\mathcal{O}(1)\) 的，這樣詢問的復(fù)雜度就是 \(\mathcal{O}(q\sqrt n)\)

塊中答案怎么求？我們只需要找到一種復(fù)雜度上界為 \(\mathcal{O}(n^2)\) 的做法，考慮分治，這樣塊中的復(fù)雜度是 \(T(n)=2T(\frac{n}{2})+\mathcal{O}(n^2)=\mathcal{O}(n^2)\)，于是預(yù)處理我們可以就做到 \(\mathcal{O}(n\sqrt n)\) 了，這樣總復(fù)雜度是 \(\mathcal{O}((n+q)\sqrt n)\) 的

6.23

模擬賽

T1

孫神

考慮分治 \(D(l,r)\)，表示將 \([l,r]\) 中的數(shù)排好序，取中點 \(mid\)，如果 \([l,mid]\) 已經(jīng)排好序了，那我們可以對 \(i\in [mid+1,r]\) 中的每一個數(shù)問出來他在 \([l,mid]\) 中的相對位置，由于數(shù)據(jù)隨機，\([l,mid]\) 中每個數(shù)之間的在 \([mid+1,r]\) 中的數(shù)大小只有差不多 \(\mathcal{O}(\log n)\) 個，對于這些數(shù)我們再分治排序一遍就行了，最后操作次數(shù)只有差不多 \(440000\)，測了幾組發(fā)現(xiàn)在 \(4.3n\) 左右，應(yīng)該是期望線性的

T2

直接建圖，\(n+k\) 個點，對于 \(1\sim k\)，連 \((i,i+1,X)\)，對于 \(k+1\sim k+n\)，連 \((k+i,j,f_{i,j})\)，這樣我們要求的就變成了一個最小直徑生成樹

分討樹中心在第一種和第二種邊的情況，我們首先預(yù)處理出來 \(t_{i,j}\) 表示 \(i\rightarrow j+k\) 的最短路徑，那對于第二種邊，我們只需要預(yù)處理出來前綴最大值和后綴最大值，對于第一種邊，我們發(fā)現(xiàn)當中點在這條邊上移動時，對于每一個 \(i\in [1,n]\)，會出現(xiàn)一段左右斜率相反的上凸函數(shù)（參考 oi-wiki 最小直徑生成樹的圖）這時候我們能作為答案的只有最上面那一條輪廓線，輪廓線容易求出，算答案的時候考慮相鄰的兩個峰就行了，這樣復(fù)雜度可以 \(\mathcal{O}(nk^2+nk\log n)\)

6.24

模擬賽

T1

二分，找出來中點所對應(yīng)的那個圓，這樣所有線段都變成了一條弦，這樣可以直接二位數(shù)點算交點個數(shù)，找到這個直徑之后直接拉出來所有的交點就行了，復(fù)雜度 \(\mathcal{O}(n\log V\log n+m\log n)\)

T2

莫反，考慮 \(\sum\limits_{d|n}\varphi(d)=n\)，考慮枚舉 \(d\)，則原式可以通過交換求和符號等化為

所有的東西都是求積，于是考慮把其變成 \(\prod i^{\alpha_i}\) 的形式，這樣我們在最后的時候可以把 \(x\notin \mathbb{P}\) 的全都貢獻給其質(zhì)因子，然后在所有質(zhì)因子處做快速冪就可以了，具體而言就是找到一個 \(p|x\)，然后 \(\alpha_p\leftarrow \alpha_x,\alpha_{\frac{x}{p}}\leftarrow \alpha_x\)

把要求的拆成兩部分，先考慮求 \(\prod\limits_{d=1}^md^{\varphi(d)\left\lfloor\frac{m}w0obha2h00\right\rfloor^n}\)，這一部分是簡單的，只需要線性篩預(yù)處理出來 \(i^n \bmod (MOD-1)\) 就行了

再求 \(\left( \prod\limits_{x_i\in[1,\left\lfloor\frac{m}w0obha2h00\right\rfloor]}\text{lcm}_{i=1}^{n}x_i\right)^{\varphi(d)}\)，記 \(S(m)=\left( \prod\limits_{x_i\in[1,m]}\text{lcm}_{i=1}^{n}x_i\right)\)，直接整除分塊，算出來 \(\mathcal{O}(\sqrt m)\) 個 \(S\) 的值然后再乘上區(qū)間 \(\varphi\) 和就行了，現(xiàn)在考慮算 \(S(m)\)，我們考慮把他拆到每一個質(zhì)數(shù)上，而每一個質(zhì)數(shù)的貢獻實際上就是 \(\sum\limits m^n-\left(m-\left\lfloor\frac{m}{p^i}\right\rfloor\right)^n\)，直接枚舉質(zhì)數(shù)計算就行了

這樣總復(fù)雜度大概是 \(\mathcal{O}(\frac{m}{\ln m}\log MOD)\)

T3

直接做

考慮在樹的中點處統(tǒng)計答案，可以把無根樹變成有根樹，那么這時候要計算一個最大深度不超過 \(d\)，點數(shù)為 \(n\) 的有根樹方案數(shù)，從 \(i=1\sim n\) 一個個把 \(F_{i,d}\) 轉(zhuǎn)移到 \(F_{j>i,d+1}\) 就能保證轉(zhuǎn)移有序了，具體而言就是 \(F_{n-i\times k,d}\times \binom{F_{n-i\times k,d}+k-1}{k}\rightarrow F_{n,d+1}\)，直接插板法就行了