陰雨后 蒼藍(lán)天空，溫度略 有所回升。

11.1

有點害怕，感覺會炸。

考前開玩笑說如果考到一半天放晴了就是我干的，如果沒有就是我考炸了，然后雨真的沒有停，我也真的考炸了。

然后就 CSP-S2025 游記。

11.2

補(bǔ)了下題，然后無所事事，因為很累。

內(nèi)驅(qū)力仍然不夠用，雖然已經(jīng)高一而且 CSP 考炸了。

11.3

下午又下大雨了啊。已經(jīng)不知道“雨”這個意象對我來說意味著什么了呢。

在某個角落聽著雨落的人啊
這般的漫漫長夜過去后
仍會愛著這些漆黑時光嗎

有的時候會盡力去體會過去某個時刻某個階段的感受，但是無論如何都沒有當(dāng)時的感覺了，最后只留下一點莫名的悵然和憂傷。而在一次次追憶的過程中對過去的感覺越來越模糊，也莫名產(chǎn)生了一種恐慌。可是我就是這么念舊啊。面對名為“成長”的“禮物”，又是如此有心而無力，又是如此無心而無力。

ARC068F Solitaire

考察一個出隊序列合法當(dāng)且僅當(dāng)其可以分解為不超過兩個遞減序列，然后 \(1\) 在第 \(k\) 個。

\(1\) 在第 \(k\) 個這個條件不好刻畫，于是取其逆排列，偏序關(guān)系不會變，還順手干掉一個限制。

然后是很板的計數(shù)部分。

CF1149C Tree Generator?

一個點的深度是其對應(yīng)左括號的嵌套層數(shù)。考察兩個點之間的路徑，也就是兩個點之間的 LCA 怎么求。

這東西感覺很歐拉序，左括號進(jìn)入子樹，右括號出子樹，那么兩點之間 LCA 其實就是一個區(qū)間 \(\min\) 狀物。

接著考慮如何對全局求這個答案。這里又被詐騙了，以為線段樹不能直接維護(hù)，但是其實兩個點之間即使算上了非最小值對答案不會有影響，那么線段樹直接維護(hù)是好做的。

[HNOI/AHOI2018] 轉(zhuǎn)盤

沒人覺得被同一個 trick 連著詐騙兩次很……嗎。

起手式就在詐騙，不管是中途停下來還是繞幾圈都是沒有意義的，直接在開始停一會兒然后一圈繞完就可以做到最優(yōu)。那么容易刻畫出答案，枚舉起點討論左邊右邊分離變量求區(qū)間最大值。

這個東西看起來不太好做，但是右半部分的式子恰好比左半部分多了 \(n\)，所以可以直接把左半部分貢獻(xiàn)放到全局上，變成了后綴信息維護(hù)，單側(cè)遞歸即可。

2023-2024 集訓(xùn)隊互測 Round 5 栞

感覺很好的題目，不管是思維部分還是計數(shù)部分都有耳目一新的感覺（見過的東西還是太少了）。

從 \(p\) 生成 \(q\) 的貪心過程考慮。從小到大考慮，如果能通過調(diào)整將一個數(shù)分到更前面的位置且仍然能分出 \(k\) 段，貪心地選最靠前的那個劃分點。嘗試形式化這個模糊的說法。從 \(q\) 的角度看，如果存在 \(q_i>q_{i+1}\) 的地方，一定是因為把在 \(p\) 中 \(q_{i+1}\) 分到前面之后不能再劃分為 \(k\) 段。

所以大概知道斷點的形式，令第一個 \(q_i>q_{i+1}\) 的位置為 \(x\)，\(q_{x+1}\) 在 \(p\) 中的位置為 \(y\)，那么從 \(x\) 處劃分能劃出 \(k\) 段，但是在 \(y\) 處直接劃就不行。同時 \((x,y)\) 中間不能有數(shù)比 \(p_y(q_{x+1})\) 小，否則不會在 \(q\) 中分到 \(x+1\) 這個位置。

雖然在 \(y\) 處直接劃不行，但是 \(p_y\) 最終還是到了 \(x+1\) 這個位置，說明同時劃上 \(x,y\) 之后是可以劃出 \(k\) 段的。那么 \(y\) 所在段后面應(yīng)該是一堆單點，否則可以把后面的某個點翻到前面來。

這一部分實際上是結(jié)合 \(p\) 生成 \(f(p)\) 的過程與 \(q\) 的最終結(jié)果作分析。我一開始做的時候只考慮了 \(p\) 到 \(f(p)\) 的貪心過程，雖然會得到類似形式的東西（比如說在最后長度 \(>1\) 的段 \(p_y\) 是 \([x,y]\) 最小的之類，這里 \(x\) 是當(dāng)前確定的一個斷點，\(y\) 是下一個可能的斷點），但是刻畫起來終究不方便，所以感覺很困難。

考慮如何計數(shù)這個結(jié)構(gòu)。枚舉合法的 \(y\)，\([x,y]\) 的部分是除了 \(p_y=q_{x+1}\) 隨便亂排，\((y,n]\) 已經(jīng)確定了。

接下來可以發(fā)現(xiàn) \([1,x]\) 的部分本質(zhì)上就是特殊性質(zhì) \(q=(1,2,3,\cdots,n)\)。

注意這里 \(n,k\) 的含義與原題已經(jīng)不一樣了。考察 \(p\) 生成 \(q\) 的過程，每次選擇值域上從最小值開始連續(xù)的地方斷開，如果能斷 \(k\) 次就合法。可以先求出 \(f_i\) 表示長度為 \(i\) 的極小的連續(xù)段方案數(shù)，答案是 \([x^n]f^k\)。根據(jù)組合意義，令階乘為 \(F\)，有 \(F=\dfrac{1}{1-f}\)，本題中都可以暴力求。

FPS 24: 24 Problems on Formal Power Series

形式冪級數(shù)好玩，但是還是當(dāng)成無背景的計數(shù)題來做。放到一起簡單說說，雖然我沒打，簡單做做，不過今天一天肯定是弄不完的。

A：考慮為什么是 \(1,3,4,6\)。先給每個都塞個 \(1\)，變成 \(2,3,5\)，然后多項式 \(2+3=5\)，就好做了。

B：枚舉 \(a,b\)，然后做完了。

C：經(jīng)典問題，對 \(\leq M\) 這個限制容斥即可。

D：關(guān)于我還不會不用多項式做法的這件事，我還沒想好怎么編。

E：為什么數(shù)據(jù)范圍只有 \(300\)，暴力卷 EGF 都能過。

F：矩陣快速冪板子。

G：滑動窗口+回退背包板子。

H：枚舉多少次 \(a=0\)，做完了。

I：這真的逃不掉多項式了吧。考慮分治卷積。

J：半在線卷積板子。

K：等價于求在 \(n\) 的時候第一次值域 \([1,i]\) 連續(xù)，可以寫出和栞一樣的式子。

L：連 \(i\rightarrow p_i\)，等價于沒有自環(huán)或二元環(huán)。沒有自環(huán)就是錯排，二元環(huán)的限制容斥掉即可。

M：連通生成子圖計數(shù)板子，link。

N：答案為 \([x^N]\prod\limits_{i=1}^N\prod\limits_{j=0}^{A_i}x^{ij}\)。后面那個等比數(shù)列求和，然后 \(\ln\) 轉(zhuǎn)除轉(zhuǎn)減，再 \(\exp\) 回去。

O：考察 Prufer 序列，其中除了 \(1\) 都是質(zhì)數(shù)次。那么 EGF 卷一下就行了。

P：暴力式子為 \(\sum\limits_{i=0}^K\binom{N}{i}m^{N-i}\)，這是一個多項式多點求值。

后面的不咋會了，放了。

11.4

整個人被蒙在鼓里的一天。

模擬賽通讀題面，T1 \(n\leq 13\) 圖計數(shù)，這個最短路的限制很不好做啊。T2 沒理解透條件，以為是互質(zhì)才能選。T3 tzy/yzq 做過，但是我不會。T4 會了 \(2|N\)。

在 T1T2T3T4 之間反復(fù)橫跳。寫出這四個字的時候說明這場比賽已經(jīng)炸了。T1 猜到了復(fù)雜度，就是爆搜按最短路分層，轉(zhuǎn)移比較簡單，但是調(diào)了好久，11:00 才過。中途寫了 T3T4 暴力，同時發(fā)現(xiàn) T3 利用 Hall 定理可以得到神秘的不會分析復(fù)雜度的打不過暴力的做法。T2 11:50 反應(yīng)過來條件轉(zhuǎn)化錯了，然后一通轉(zhuǎn)化之后還是錯了，淦。最后 \(100+30+50+10=190\)，T4 掛了 5pts。

賽后發(fā)現(xiàn)沒有同時過前三個題的。同時這個 T3 感覺沒見過不可能會做，怎么想得到的。得知賽前他們有人找到 T3T4 原題并分享題解，怪不得 T3 通過率比 T1T2 高。之后得知 tzy T1 代碼是 czy 的，擱著沒有一個題是自己做的是吧（

tzy 那個神人怎么又去上語文課了。

[省選聯(lián)考 2021 A/B 卷] 滾榜

我咋這么菜。

考慮將一個滾榜方案映射到最優(yōu)的 \(b\) 的分配方案上計數(shù)，直接狀壓是 \(O(2^nn^2m^2)\)。

但是由于 \(b\) 單調(diào)不增所以可以費用提前計算，可以砍掉記錄上一個 \(b\) 的那一維，于是做到 \(O(2^nn^2m)\)。

CF1608F MEX counting

前面一個數(shù)對后面 \(MEX\) 的影響不好記錄，那么延遲欽定。

令 \(dp_{i,j,k}\) 表示考慮前 \(i\) 個數(shù)，\(MEX\) 為 \(j\)，有 \(k\) 種大于 \(j\) 的數(shù)。轉(zhuǎn)移時枚舉前 \(i+1\) 的 \(MEX\) \(m\)，\(dp_{i+1,m,k+1-(m-j)}\leftarrow dp_{i,j,k}\times \dfrac{k!}{[k+1-(m-j)]!}\)，\(dp_{i+1,j,k}\leftarrow dp_{i,j,k}\times (j+k)\)，\(dp_{i+1,j,k+1}\leftarrow dp_{i,j,k}\)。由于有 \(b_i\) 的限制，狀態(tài)數(shù) \(O(n^2k)\)，轉(zhuǎn)移 \(O(k)\)。可以前綴和優(yōu)化做到 \(O(n^2k)\)。

這里狀態(tài)定義如果是 \(k\) 個大于 \(j\) 的數(shù)，只能做到 \(O(n^2k^3)\) 或者 \(O(n^2k^2)\)。主要原因在于 \(MEX\) 這樣一個按種類可重復(fù)貢獻(xiàn)的東西處理個數(shù)是不好做的。果然還是太菜了。

11.5

極 度 憤 怒。為自己的愚蠢感到 極 度 憤 怒。

開場讀題，T1 博弈，T2T3 計數(shù)，T4 神仙題，居然給了 SMAWK 20pts，但是估計沒有時間打。

T1 不會。

T2 轉(zhuǎn)化題意。容斥掉 \(p_i\not=i\) 的限制，基于斯特林?jǐn)?shù)有 \(O(n^2)\) 做法。感覺沒有前途。又想出一個 \(O(n^2)\) 遞推，感覺更沒有前途了。于是拆斯特林通項，但是推了好久。為自己的愚蠢感到 極 度 憤 怒。推完之后處理個前綴和可以做到 \(O(n^2)\)。為自己的愚蠢感到 極 度 憤 怒。為什么還是 \(O(n^2)\)。為自己的愚蠢感到 極 度 憤 怒。

怎么已經(jīng) 10:00 了。趕緊寫個 T4 \(O(n^2\log n)\) 暴力先。怎么只有 28pts。

T1 不會。

雖然中途經(jīng)常切去 T3，但是連第一檔 8pts 都沒推對。會了第四問的 \(O(n^4)\) 做法，有 40pts，寫。

調(diào)不出來。T1 還沒過。T1 不會。為自己的愚蠢感到 極 度 憤 怒。

T2 不會優(yōu)化。為自己的愚蠢感到 極 度 憤 怒。

賽后看題解，哦原來外面兩層循環(huán)是一個二項式定理狀物。也就是場上我寫了一個巨丑無比的 \(O(n^2)\) 循環(huán)去算二項式定理 \(O(\log n)\) 解決的問題。為自己的愚蠢感到 極 度 憤 怒。冷靜下來，發(fā)現(xiàn)需要一個線性求 \(i^n\)，我怎么不會。為自己的愚蠢感到 極 度 憤 怒。哦原來線性篩就可以了。為自己的愚蠢感到 極 度 憤 怒。

T3 的 \(O(n^4)\) 改成回退背包就能過了。為自己的愚蠢感到 極 度 憤 怒。原來第一問和第三問這么簡單。為自己的愚蠢感到 極 度 憤 怒。