博客寫得太長看得時候會很累，于是再開一篇。順便在這里記一下主席的ZR密碼：xyt1538482243

CF590E Birthday

對于兩個字符串\(S_i,S_j\)，如\(S_i\)是\(S_j\)的子串，那么我們就稱\(S_i\leq S_j\)。不難發(fā)現(xiàn)\((S,\leq)\)構成了一個偏序集。我們要找到一個子集使得兩兩字符串不存在包含關系，就等價于找到一個子集兩兩不可比，即找到最大反鏈。

首先考慮把這個偏序關系求出來，一個簡單的想法是建出AC自動機，把每一個串拿上去跑，每到一個節(jié)點就暴力跳\(fail\)，這樣的時間復雜度是\(O(n\sum |S_i|)\)。不難注意到跳\(fail\)的過程中跳到第一個有結束標記的節(jié)點就沒有必要往上跳了，因為偏序關系具有傳遞性，所以那些更靠上的點一定會被其他這個點跳到。于是再建自動機的時候維護每個點往上最近的帶有結束標記的點，這樣最多只需要跳一次。最后用floyd求一個傳遞閉包即可。

根據(jù)\(\rm Dilworth\)定理，最大反鏈長度=最小偏序集劃分。顯然這個偏序關系構成了一個\(\rm DAG\)，在\(\rm DAG\)上，最小偏序集劃分=最小鏈劃分。最小鏈劃分是一個經(jīng)典問題，將原圖中的每個點\(i\)拆成\(i\)和\(i'\)，對于原圖中的一條邊\((x,y)\)，我們建邊\((x,y')\)，這樣就得到了一張二分圖，最小鏈劃分=原圖點數(shù)-最大匹配數(shù)。于是跑一個匈牙利即可。

之后是根據(jù)最小偏序集劃分求出最大反鏈，大概就是這樣：

時間復雜度\(O(n^3+\sum_{i=1}^n|s_i|)\)，代碼。

CF526F Pudding Monsters

一番轉化發(fā)現(xiàn)就是求滿足\(\max-\min+1=r-l+1\)的區(qū)間\([l,r]\)的數(shù)量。枚舉\(r\)，那么\(\max-\min+l=r\)，不難發(fā)現(xiàn)\(\max-\min+l\)一定是最小值，于是用線段樹維護區(qū)間最小值和最小值出現(xiàn)次數(shù)，\(\max,\min\)用單調(diào)棧維護即可。

時間復雜度\(O(n\log n)\)，代碼。

CF1270F Awesome Substrings

設\(s_i\)為序列的前綴和，一個區(qū)間\([i,j]\)是好的當且僅當\(i-j=d(s_i-s_j),d\in \mathbb{N^*}\)。移一下項可以發(fā)現(xiàn)即為\(i-ds_i=j-ds_j\)，這樣一個區(qū)間\([i,j]\)是好的條件就轉化為\(g_d(i)=g_d(j)\)，設\(g_d(i)=i-ds_i\)。設一個閥值\(B\)，對于所有不超過\(B\)的\(d\)，我們求出其\(g_d(i)\)的值，設滿足\(g_d(i)=x\)的\(i\)有\(y\)個，那么就會有\(\binom{y}{2}\)的區(qū)間是好的。這邊優(yōu)秀的處理即可做到\(O(nB)\)。

再來考慮\(d>B\)的情況，即\(\frac{i-j}{s_i-s_j}>B\)，即\(s_i-s_j<\frac{i-j}{B}\)。顯然\(s_i-s_j\)不會超過\(\frac{n}{B}\)。對于每一個數(shù)我們處理其后面第一個\(1\)的位置，枚舉一個點作為左端點，之后往后跳\(1\)的位置即可，當\(1\)的個數(shù)超過\(\frac{n}{B}\)的時候就停下來。這樣相當于在枚舉\(s_i-s_j\)的值，有了\(1\)的個數(shù)就可以直接算了。這里計算的時候還需要注意去掉\(d\leq B\)的情況，這邊的復雜度是\(O(n\frac{n}{B})\)。

顯然根號平衡一下復雜度就是\(O(n\sqrt{n})\)。

HZOI省選模擬84C 字符串

兩個串\(S,T\)相似的定義是至多存在一個不相等的位置。考慮\(S=Xc_1Y,T=Xc_2Y\)，顯然這個時候\(S\)和\(T\)相似，不難發(fā)現(xiàn)\(X\)是\(S,T\)的最長公共前綴，\(Y\)是\(S,T\)的最長公共后綴。于是\(S,T\)相似的充要條件為\({\rm LCP}(S,T)+{\rm LCS}(S,T)\geq m-1\)。

不難想到\({\rm LCP},{\rm LCS}\)分別是后綴樹和前綴樹上\(lca\)的深度，于是把兩棵樹用SAM建出來。對于每一個長度為\(m\)的子串，我們求出其在兩棵樹上的位置。在第一棵樹上做啟發(fā)式合并，這樣相當于確定了\({\rm LCS}\)，這樣就有\({\rm LCP}\geq m-1-{\rm LCS}\)，就可以利用樹上倍增在第二棵樹上確定位置了。顯然滿足條件的點在一棵子樹中，于是我們按dfs序維護線段樹，求一下這個子樹內(nèi)有多少點，再去線段樹上區(qū)間加。可能需要標記永久花等高明的實現(xiàn)方法。

復雜度時\(O(n\log^2 n)\)，代碼。據(jù)說有厲害的做法能做到\(O(n\log n)\)。

CF875E Delivery Club

先二分一個\(mid\)，之后是經(jīng)典套路，設\(f_{i,j}\)表示第\(i\)時刻一個人在\(x_i\)位置，另一個人在\(j\)位置是否可行。有兩種轉移，一種是第一個人走到\(x_{i+1}\)位置，即\(f_{i,j}\rightarrow f_{i+1,j}\)；另一種是在\(j\)位置的人移動到\(x_{i+1}\)，即\(f_{i,j}\rightarrow f_{i+1,x_i}\)。由于任意時刻距離都不能超過\(mid\)，所以只有當\(|j-x_i|> mid\)的時候\(f_{i,j}\)一定是\(0\)。

發(fā)現(xiàn)這個dp的兩種轉移都非常簡單，第一種轉移就是直接繼承上一層的狀態(tài)，第二種轉移只操作一個位置，于是考慮整體dp；我們用一個set來維護滿足\(f_{i,j}=1\)的\(j\)，第一種轉移就是直接繼承前一個set，第二種轉移就是單點插入。之后我們需要刪除\(|j-x_{i+1}|>mid\)的\(j\)，這樣的\(j\)一定位于set的兩端，暴力刪除即可。由于只插入了\(n\)次，所以刪除的復雜度時均攤線性的。套上一個二分，復雜度就是\(O(n\log n\log w)\)。

這個兩個\(\log\)的做法看起來有點垃圾，考慮進一步優(yōu)化；考慮求出每一次插入被刪除的時間，這樣就能知道是否有一個時刻set為空；進一步觀察，并沒有必要對于每一個元素都求出其被刪除時間，由于只需要求是否有一個時刻被刪空，所以我們只需要關心當前刪除時間最晚的在哪里被刪除就好了。設目前已經(jīng)處理了前\(i\)個，最晚刪除時間為\(t\)。對于\(i+1\)，我們先用一個st表\(O(1)\)判斷一下其是否在\(t\)之前就被刪除了；如果被刪除了，那么\(i+1\)一定不如之前某個元素優(yōu)，直接跳過就好了；如果還沒被刪除，那么我們就往后暴力就出其在何時被刪除。這樣一次\(check\)的復雜度就來到了\(O(n)\)；于是復雜度就是\(O(n\log w)\)，代碼。

LGP6556 The Forest

用一下樹上連通塊滿足\(|V|-|E|=1\)的性質(zhì)，可以寫一個\(O(n^2)\)的暴力；反過來考慮一條紅色樹上的邊\((u,v)\)在藍色樹上的哪些路徑中出現(xiàn)過，發(fā)現(xiàn)一條路徑只需包含\((u,v)\)即可，這個條件可以用dfs序寫成矩陣的形式，于是考慮用數(shù)據(jù)結構來維護。

外面先套一個點分治，之后dfs當前分治塊；掃到一個點\(u\)的時候我們遍歷一下與其在紅色樹上相鄰的點\(v\)，如果\(v\)不在當前分治塊里，那么分治塊中不可能存在一條路徑包含\((u,v)\)；否則的話我們分情況討論一下。

• 當\(v\)是\(u\)的祖先節(jié)點，那么從\(u\)出發(fā)的任何一條經(jīng)過分治重心的路徑都包含\((u,v)\)這條路徑，于是令整體減一。

• 當\(v\)在其他子樹中，那么任取\(v\)子樹中的點\(x\)，\((x,u)\)都包含\((u,v)\)這條路徑，于是令\(v\)子樹中的點都減一；其實就是在dfs序上區(qū)間減一。

用線段樹來維護區(qū)間最小值和區(qū)間最小值個數(shù)即可，復雜度是\(O(n\log^2 n)\)。代碼。

CF1278F Cards

其實就是求

因為\(k\)不大，所以大家都知道\(i^k\)需要用斯特林數(shù)展開一波，于是展開來大概是這個樣子

把\(\binom{n}{i}\binom{i}{j}\)展開成\(\frac{1}{j!}\frac{n!}{(i-j)!(n-i)!}\)，想辦法把后面配成組合數(shù)，因為\(n!=(n-j)!n^{\underline j}\)，于是可以寫成\(\frac{n^{\underline j}}{j!}\binom{n-j}{i-j}\)，提出來之后大概長這樣：

不難想到改寫一下里面那個\(\sum\)的上下角標，于是\(\sum_{i=1}^n\binom{n-j}{i-j}p^{i}(1-p)^{n-i}=\sum_{j=0}^{n-j}\binom{n-j}{i}p^{i+j}(1-p)^{n-j-i}\)，提出一個\(p^i\)后用一下二項式定理，于是后面就全沒了。最后答案就是

NTT即可做到\(O(k\log k)\)，代碼。還有一個\(O(k)\)做法是把第二類斯特林數(shù)用容斥的形式展開后，再遞推一個柿子。

ZR2020寒假省選集訓Day3 A

考慮到點分樹的形態(tài)和點分的方案是一一對應的關系，于是我們轉為統(tǒng)計點分樹的形態(tài)數(shù)。考慮現(xiàn)在有一棵點分樹，斷掉原樹中的一條邊\((u,v)\)后會對點分樹有什么影響；斷掉一條邊后原樹形成了兩個聯(lián)通塊，把其中一個聯(lián)通塊的點稱為黑點，剩下的稱為白點；可以發(fā)現(xiàn)對于每一個黑點（白點），找到其點分樹祖先中最近的黑點（白點）作為其新的父親，這樣各有白點和黑點各有一個找不到新父親，可以將其直接斷開；這樣就得到了兩個新的點分樹，這就是原樹斷開一條邊后得到兩個聯(lián)通塊的點分樹。這就是點分樹的分裂。

再來考慮連接\((u,v)\)這條邊會有什么影響，首先我們要從\(u\)或\(v\)所在的兩棵點分樹中選一個當根，根在原點分樹中的兒子仍作為其兒子，之后用剩下的點組成一棵點分樹來做根的兒子；不難發(fā)現(xiàn)本質(zhì)上就是將\(u\)到根路徑上的點和\(v\)到根路徑上的點按照深度歸并了起來，這樣就得到的點分樹就是連接\((u,v)\)后新樹的點分樹了。于是我們設\(dp_{x,i}\)表示\(x\)在點分樹中深度為\(i\)的方案數(shù)，把原樹中的每一條邊連上去即可，轉移的話就是枚舉原來\(x\)上面有多少點，即\(dp'_{x,i}=\sum_{j=1}^i\sum_{k=i-j}^n dp_{x,j}dp_{v,k}\binom{i-1}{j-1}\)，預處理\(dp_v\)的后綴和就能做到\(O(n^2)\)。代碼。

ZR2020三月省選集訓Day2 B

我們發(fā)現(xiàn)操作一個點只會影響其祖先中的點，于是可以將這個問題視為翻硬幣博弈。在翻硬幣博弈中，局面的\(SG\)值等于所有可以被操作的硬幣單獨存在時的\(SG\)值的異或和，于是我們對于每一個白色節(jié)點\((i,j)\)求一下\(SG(i,j)\)之后異或起來即可。

經(jīng)過打表可以發(fā)現(xiàn)，\(SG(i,j)={\rm lowbit}(\max(i,j))\)。由于白色節(jié)點以矩形的形式給出，數(shù)量較多，同時注意到\(n\leq 10^5\)，所以可以考慮用類似掃描線求矩形面積并的方式來做。把一個矩形\((x_l,x_r,y_l,y_r)\)拆成\((x_l,y_l,y_r,1)\)和\((x_r+1,y_l,y_r,-1)\)，表示在\(x_l\)時刻插入一條線段\([y_l,y_r]\)，在\([x_r+1]\)時刻刪除線段\([y_l,y_r]\)。對于時刻\(i\)，我們求一下\(\leq i\)的點有多少個，這些點對答案的貢獻都是\({\rm lowbit}(i)\)；在統(tǒng)計一下大于\(i\)且被覆蓋了的點的\(\rm lowbit\)的異或和。由于需要快速求出一個區(qū)間的\(\rm lowbit\)異或和，所以我們直接將線段樹的值域設為\([0,2^{30})\)，這樣線段樹上每一段區(qū)間的長度都是\(2\)的整數(shù)次冪，就能快速求出這段區(qū)間的\(\rm lowbit\)異或和。

之后在線段樹上維護一下最小值和最小值的\(\rm lowbit\)異或和即可，復雜度是\(O(n+k\log m)\)。代碼。

ZR2020三月省選集訓Day2 C

將這棵有根樹視為外向樹，所求即所有拓撲序的順序對。考慮兩個點\(i,j\)且\(i<j\)，我們求一下在多少種拓撲序中，點\(i\)出現(xiàn)的位置比\(j\)靠前。首先如果\(i\)是\(j\)的祖先，那么在所有拓撲序中，\(i\)都會比\(j\)靠前。于是\(O(n)\)求一下樹的拓撲序個數(shù)就可以直接算了。

對于\(i,j\)不存在祖先關系的情況，先預處理一個\(dp_{i,j,k}\)表示點\(i\)在子樹\(j\)中拓撲序為\(k\)的方案數(shù)，轉移即合并兩棵子樹的時候枚舉一下有多少個點放在\(i\)前面，比如在點\(i\)前面放\(t\)個，那么就需要\(dp_{i,j,k}\)乘上\(\binom{k+t-1}{t}\binom{sz_v+sz_j-k-t}{sz_v-t}\)，即在前面插入\(t\)個后\(i\)的排名變?yōu)榱?span id="w0obha2h00" class="math inline">\(k+t\)，那么就從前\(k+t-1\)個位置里選出那\(t\)個要插入的點放在哪里，剩下的\(sz_v+sz_j-k-t\)個位置里再插入剩下的\(sz_v-t\)個點的位置，還需要乘上子樹\(v\)的拓撲序個數(shù)\(g_v\)，轉移到\(dp_{i,j,k+t}\)。轉移復雜度同樹上背包，對\(n\)個點都求一遍復雜度為\(O(n^3)\)。

之后我們欽定兩個不是祖先關系的點\(i,j\)，使得他們在\(lca\)處合并，使得編號較小的點\(i\)出現(xiàn)在前面。合并的方式和上面差不多，也是枚舉在\(i\)前面插入多少個數(shù)，乘上幾個組合數(shù)，求出這個方案數(shù)再正常求一遍拓撲序即可。由于合并的時候兩個子樹可能會很大，所以這個做法是\(O(n^4)\)的。進一步觀察發(fā)現(xiàn)并不需要枚舉\(j\)，我們多個\(j\)的方案數(shù)加起來一起算即可，這樣復雜度就變成了\(O(n^3)\)。代碼。

ZR2020三月省選集訓Day2 A

一個經(jīng)典trick，前綴\(\gcd\)變化次數(shù)是\(O(\log w)\)級別的，于是用一個單調(diào)棧可以在\(O(n\log w)\)的時間內(nèi)求出一堆四元組\((l,r,x,v)\)，表示\(\forall i\in [l,r]\)，區(qū)間\([i,x]\)的\(\gcd\)為\(v\)。這些四元組能表示所有區(qū)間的\(gcd\)。

考慮正難則反，改為對每個點求有多少種方案不包含它，之后拿總方案數(shù)一減即可。考慮使得所有選出的區(qū)間的\(\gcd\)為\(w\)，設\(pre_i\)表示從\([1,i]\)中選出若干\(\gcd\)為\(w\)的區(qū)間的方案數(shù)，\(beh_i\)表示從\([i,n]\)選出若干\(\gcd\)為\(w\)區(qū)間的方案數(shù)。那么對于不包含點\(i\)的方案數(shù)就是\((pre_{i-1}+1)\times (beh_{i+1}+1)-1\)。

考慮求出\(pre\)，把所有\(v=w\)的四元組拿出來，如果不存在一個四元組\((l,r,x,v)\)滿足\(x=i\)，那么\(pre_i=pre_{i-1}\)；否則選一段以\(i\)結尾的區(qū)間，那么\(pre_i=pre_{i-1}+\sum_{j=l}^r 1+pre_{j-1}\)。第一類轉移可以直接使用線段樹來區(qū)間覆蓋，第二類轉移求一個區(qū)間和即可。于是復雜度是和四元組個數(shù)相關的。同理，\(beh\)也可以這樣求出。

相同的\(pre\)和\(beh\)會構成一段段區(qū)間，區(qū)間個數(shù)即為四元組個數(shù)；于是直接將區(qū)間排序后區(qū)間覆蓋，用差分實現(xiàn)區(qū)間加即可。復雜度是\(O(n\log n\log w)\)，代碼。

HZOI省選模擬89A 石子

經(jīng)過打表可以發(fā)現(xiàn)\(SG(x)=\log_2 \rm lowbit(x)\)；證明的話考慮證明\(SG(x)=SG(xq)\)，\(q\)為一奇數(shù)，大概就是考慮\(SG(x-d_1),SG(x-d_2)\dots SG(x-d_m)\)和\(SG(q(x-d_1)),SG(q(x-d_2))\dots SG(q(x-d_m))\)一一對應，之后歸納下去就好了；

之后設\(tax_i\)表示\(SG(x)=i\)的\(x\)有多少個，顯然\(tax_i=\lceil\frac{\lfloor\frac{n}{2^i}\rfloor}{2}\rceil\)，這玩意大概需要寫一個高精度；現(xiàn)在將問題轉化成了選\(m\)個數(shù)，第\(i\)中數(shù)有\(tax_i\)種選法，問異或和不為\(0\)的方案數(shù)，這直接把\(tax_i\)給fwt掉后對位乘\(m\)次，即每個數(shù)取一個\(m\)次方，再ifwt回來就好了；時間復雜度\(O(\log n\log m+\log n\log \log n)\)。

HZOI省選模擬82C 絕對伏特加

題意：有\(n\)個整形隨機變量，均為\([1,k]\)等概率隨機，設\(a_i\)表示\(i\)出現(xiàn)的次數(shù)，求\(\prod_{i=1}^L a_i^F\)的期望，對\(2003\)取模。

考慮\(a_i^F\)的組合意義，我們把\(i\)出現(xiàn)的位置列出來，分別為\(A_1,A_2\dots A_{a_i}\)，\(a_i^F\)表示從這\(a_i\)個位置中選\(F\)個出來，可以有重復；而\(\prod_{i=1}^L a_i^F\)就是從對于每個\(a_i\)都選\(F\)個位置，由于一個位置的取值唯一，所以不同的\(a_i\)選出的位置不同。

設\(b_i\)表示\(i\)選出來的\(F\)個出現(xiàn)位置構成集合的大小，即去重后的大小；考慮先給每個\(i\)選好出現(xiàn)的位置，那么方案數(shù)就是\(\binom{n}{b_1}\times \binom{n-b_1}{b_2}\times \dots \times \binom{n-\sum_{i=1}^{L-1}b_i}{b_L}\)，，將這個組合數(shù)拆開約分后發(fā)現(xiàn)其實就是\(\frac{\binom{n}{\sum_{i=1}^L b}(\sum_{i=1}^L b)!}{\prod_{i=1}^L b_i!}\)，注意到這個分母是一堆階乘，于是不難想到需要搞一個\(\rm EGF\)。

設生成函數(shù)為\(F(x)=\sum_{i=1}^F D(i,F)\frac{x^i}{i!k^i}\)，\(D(i,F)\)表示一個長度為\(F\)的序列，\(i\)種數(shù)都出現(xiàn)至少一次的方案數(shù)，選出的這\(i\)位置都要填上特定的數(shù)于是概率是\(\frac{1}{k^i}\)。不難發(fā)現(xiàn)\(D(i,F)=[F](e-1)^iF!\)，于是我們可以在\(O(F^3)\)的時間內(nèi)求出所有數(shù)的\(D(i,F)\)，這樣把\(L\)個\(F(x)\)乘起來就好了。注意到最后要乘一個\((\sum_{i=1}^L b)!\)，當\(\sum_{i=1}^L b_i \geq mod\)的時候，顯然有\((\sum_{i=1}^L b)!=0\)；于是再做多項式乘法的時候對\(x^{mod}\)取模即可，這樣做的復雜度是\(O(F^3+mod^2\log m)\)。

進一步，我們發(fā)現(xiàn)\(D(i,x)\)可以直接使用第二類斯特林數(shù)寫成\(S(F,i)i!\)，于是\(O(F^2+mod^2\log m)\)即可。代碼。