9.24

P8331 [ZJOI2022] 簡(jiǎn)單題

幽默題

這張圖肯定是若干個(gè)杏仁拼在一起，證明？隨便拿一個(gè)杏仁出來(lái)，如果我們加邊，要么會(huì)有一個(gè) \(K_4\) 同胚，要么會(huì)有至少一組平行的環(huán)，要么仍然是一個(gè)杏仁，前面兩種情況容易分討出來(lái)都是不合法的，這里就不寫(xiě)了

由于我們要求 \(S\) 到 \(T\) 的簡(jiǎn)單路徑和，考慮建圓方樹(shù)，這條路徑會(huì)穿過(guò)多個(gè)杏仁，每個(gè)杏仁上有兩個(gè)點(diǎn)需要被考慮，除了在 LCA 處的兩個(gè)點(diǎn)肯定都是樹(shù)上一對(duì)爺爺和孫子，如果我們能預(yù)處理出來(lái)每一對(duì)爺爺和孫子的原點(diǎn)的貢獻(xiàn)就可以快速算了，可以維護(hù)一個(gè)二元組

現(xiàn)在考慮怎么快速算杏仁中兩個(gè)點(diǎn)的貢獻(xiàn)，只需要分討兩個(gè)點(diǎn)是否在同一條鏈上，設(shè)這個(gè)杏仁的兩個(gè)端點(diǎn)是 \(A,B\)，杏仁中每個(gè)點(diǎn)和 \(A\) 的距離為 \(da\)，和 \(B\) 的距離為 \(db\)，不妨假設(shè) \(da_{S}<da_{T}\)，記 \(C\) 為這個(gè)杏仁上的鏈數(shù)，\(V\) 為這個(gè)鏈上所有邊的權(quán)值和，分類討論：

• 當(dāng) \(S\) 和 \(T\) 在一條鏈上，二元組為 \(\left(C,V+(C-2)(da_{S}+db_{T})\right)\)
• 當(dāng) \(S\) 和 \(T\) 不在一條鏈上，二元組為 \(\left(2(C-1),2V+(C-3)(da_{S}+db_{T})\right)\)

這樣兩點(diǎn)的貢獻(xiàn)可以 \(\mathcal{O}(1)\) 算了，理論復(fù)雜度可以線性，瓶頸在于求 LCA

P12536 [XJTUPC 2025] 我永遠(yuǎn)喜歡希兒·芙樂(lè)艾

這都被出爛了。

換根沒(méi)用，本質(zhì)就是子樹(shù)和

對(duì) \(A\) 分塊，預(yù)處理一個(gè)系數(shù)數(shù)組，整塊好處理，散塊會(huì)有 \(nB\) 次鏈加和 \(B\) 次子樹(shù)查，發(fā)現(xiàn)鏈加字?jǐn)?shù)和可以看作一個(gè) \(kdep_u+b\) 的形式，維護(hù)一下系數(shù)做單點(diǎn)修區(qū)間查就行了，復(fù)雜度 \(\mathcal{O}(n\sqrt{n})\)

AT_wtf19_c1 Triangular Lamps Easy

我們發(fā)現(xiàn)可以從一個(gè)點(diǎn)出發(fā)到達(dá)他下面的所有行，使得只有他下面的行里有亮的，那么可以說(shuō)明，如果我們把所有最后亮著的燈推到同一行，再把初始的點(diǎn)也推到那一行，如果這一行的兩個(gè)亮燈的狀態(tài)相同，這個(gè)初始點(diǎn)就是合法的，現(xiàn)在再觀察一下把每個(gè)點(diǎn)推下去，亮燈的狀態(tài)，考慮點(diǎn) \((0,0)\)，記每個(gè)點(diǎn)的亮燈狀態(tài)為 \(t_{x,y}\)，我們可以遞推得到 \(t_{x,y}=t_{x,y-1}\oplus t_{x-1,y-1}\)，這就是一個(gè)組合數(shù)的形式，那么亮燈當(dāng)且僅當(dāng) \(x\subseteq y\)，對(duì)于不是 \((0,0)\) 的位置，只需要考慮其坐標(biāo)的差值

我們?cè)诔跏键c(diǎn) \((x,0)\)，發(fā)現(xiàn) \(y\) 是不變的，而亮燈的充要是 \(\Delta x\subseteq y\)，由于保證有解，我們?nèi)我馊∫恍信袛喽际强梢缘模覀儾环寥?\(y=-2^{60}+1\) 那一條線，這條線上從 \(x\) 開(kāi)始往后都是亮的，于是可以考慮二分，每次判斷所有最終狀態(tài)下亮著的點(diǎn)的推過(guò)去，在 \((x,-2^{60}+1)\) 處是不是還亮著的，判斷一下奇偶性即可

AT_arc141_d [ARC141D] Non-divisible Set

我擦。

考慮到 \(2m\) 這個(gè)東西，我們可以把每個(gè)數(shù)拆成 \(k2^p\) 的形式，其中 \(k\) 是奇數(shù)，那么每一組 \(k\) 只能選而且必須選一個(gè)，接著考慮 \(k\) 之間有倍數(shù)關(guān)系的，若 \(c|d\)，那么 \(c2^{x}\) 和 \(d2^{y}\) 必須滿足 \(x>y\)，那對(duì)于每一個(gè) \(k\)，其合法的必然是一段區(qū)間，記為 \([l_k,r_k]\)，需滿足 \(\forall k|k_1,l_k>l_{k_1},r_{k}<r_{k_1}\)，可以調(diào)和級(jí)數(shù)求解 \(l\) 和 \(r\)，復(fù)雜度線性對(duì)數(shù)

#6713. 「EC Final 2019」狄利克雷 k 次根 加強(qiáng)版

學(xué)習(xí)了迪克生成函數(shù)。

先取 ln 再 exp，關(guān)鍵是 DGF 的 ln 和 exp 怎么算

我們得知道怎么算導(dǎo)數(shù)和積分，有

而我們不用真的去算 \(\ln n\)，反正最后會(huì)被消掉，我們可以直接取 \(\ln n\) 為 \(n\) 的質(zhì)因子次數(shù)之和

那 ln 就是：

exp：

CF1738G Anti-Increasing Addicts

牛。

補(bǔ)習(xí)了序理論。

首先最長(zhǎng)鏈等于最小反鏈覆蓋，所以我們必須要用 \(\le k-1\) 個(gè)反鏈覆蓋所有最后選擇留下來(lái)的點(diǎn)，\(k-1\) 條反鏈最多覆蓋 \(n^2-(n-k+1)^2\) 個(gè)位置，因?yàn)榈谝粭l最多覆蓋 \(2n-1\) 個(gè)，第二條最多覆蓋 \(2n-3\) 個(gè)，以此類推，所以題目的限制已經(jīng)是最嚴(yán)格的了

記 \(f_{x,y}\) 為從 \((x,y)\) 開(kāi)始，只經(jīng)過(guò)必須保留的點(diǎn)，最長(zhǎng)鏈長(zhǎng)度，那么存在 \(f_{x,y}=k\) 的時(shí)候必然無(wú)解，如果我們根據(jù) \(f_{x,y}\) 的值分層，值相同的位置必定不存在偏序關(guān)系，為了最大化覆蓋的位置，我們不妨令第 \(i\) 條反鏈從 \((n,i)\) 走到 \((i,n)\)，并且把所有沒(méi)被覆蓋過(guò)的 \(f\) 值為 \(k-i\) 的位置都覆蓋了，這樣如果所有的反鏈都不相交，我們就能覆蓋 \(n^2-(n-k+1)^2\) 個(gè)位置

經(jīng)典的，我們考慮貪心地往上走，也就是說(shuō)，如果上面已經(jīng)被覆蓋了，或者再往上走就無(wú)法覆蓋到某個(gè) \(f\) 值為 \(k-i\) 的位置，這時(shí)候就該向右走了，具體的，我們記 \(lim_{v,y}\) 為第 \(y+1\) 列及以后，\(f\) 值為 \(v\) 的最大行，如果當(dāng)前 \(lim_{k-i,y}=x\)，那么我們不會(huì)再往右走了

只要每條反鏈都能取滿，我們就肯定能構(gòu)造出來(lái)最優(yōu)方案，也就是需要證明在上述貪心策略下，第 \(i\) 條反鏈必定經(jīng)過(guò) \((n-k+i,i)\) 和 \((i,n-k+1)\)

對(duì)于第 \(i\) 條反鏈，第 \(i+1\) 列及右邊不會(huì)出現(xiàn)行數(shù) \(>n-k+i\) 的 \(f\) 值為 \(k-i\) 的位置 \((x,y)\)，如果存在，那么有 \(x>n-k+i\)，這時(shí)候，其鏈末端行數(shù) \(x'\) 有 \(x'\ge x+(k-i)>n\)，爆了

求 \(f\) 是簡(jiǎn)單的，總復(fù)雜度 \(\mathcal{O}(n^2)\)

9.25

模擬賽

T1

幽默。

T2

幽默。

T3

點(diǎn)分治。

T4

\(\frac{\binom{30}{4}2^4n}{w}\) 能過(guò)，難點(diǎn)在于想到 bitset

AT_hitachi2020_d Manga Market

之前的模擬賽原，很傻的 Exchange Argument

AT_arc138_e [ARC138E] Decreasing Subsequence

牛逼

把 \(a_i\) 減一，然后把 \(a_i\) 大于等于 \(0\) 的 \(i\) 連向 \(a_i\)，由于不存在 \(a_i=a_j\)，所以合法的方案肯定是若干條鏈，這樣我們就構(gòu)造出來(lái)了一個(gè) \(a_i\) 的雙射

如何刻畫(huà)下降子序列呢？我們發(fā)現(xiàn)他一定是一個(gè)彩虹狀物，也就是每條邊都互相包含，我們的任務(wù)就是數(shù)出來(lái)合法的彩虹的數(shù)量，則有

把后面的和式預(yù)處理出來(lái)直接算就可以了，復(fù)雜度 \(\mathcal{O}(n^2)\)

AT_agc065_d [AGC065D] Not Intersect

牛。

Raney 引理： 對(duì)于長(zhǎng)度為 \(n\) 的 整數(shù) 序列 \(a\)，如果 \(\sum a=1\)，那么 \(a\) 的 \(n\) 個(gè)循環(huán)位移中有且僅有一個(gè)滿足所有的前綴和均為正整數(shù)

考慮原題目，我們不妨把環(huán)看成一個(gè) \(n\) 邊形，因?yàn)檫@個(gè) \(n\) 邊形中相鄰的兩個(gè)點(diǎn)連邊是不影響其他邊的，所以我們可以直接枚舉連了多少條這樣的邊，假如連了 \(i\) 條，我們剩下要求的就是用 \(m-i\) 條邊劃分這個(gè) \(n\) 邊形的方案數(shù)

我們可以構(gòu)造如下操作序列和劃分?jǐn)?shù)構(gòu)成一個(gè)雙射：

• 維護(hù)一個(gè)棧，再維護(hù)一個(gè)指針從 \(2\) 到 \(n\)，每次有兩種操作，第一種操作：往棧中加入 \(j\)；第二種操作：選擇一個(gè)正整數(shù) \(k\)，滿足 \(k<\) 當(dāng)前棧的大小，彈出棧頂 \(x\)，再?gòu)棾鰲ｍ斶B續(xù)的 \(k\) 個(gè)數(shù)，將 \(x\) 和當(dāng)前的棧頂連邊，如果棧為空則和 \(1\) 連邊，最后把 \(x\) 壓入棧中

其實(shí)這個(gè)雙射還有一點(diǎn)小問(wèn)題，就是可能會(huì)出現(xiàn) \(n\rightarrow 1\) 的邊，這個(gè)好說(shuō)，我們直接強(qiáng)制令 \(n\) 會(huì)連向 \(1\) 就行了

把棧大小的變化值看成一個(gè)序列，那么每次要么是 \(+1\)，要么是 \(-k\)，而且任意時(shí)刻，棧中都必須有元素，且最后棧大小為 \(1\)，這正好就是我們用 Raney 引理的時(shí)候！

枚舉外層連邊 \(i\)，記 \(k=m-i+1\)，則有

復(fù)雜度線性

另外還有設(shè)二元生成函數(shù)拉反的做法，但是遠(yuǎn)遠(yuǎn)沒(méi)這個(gè)聰明

AT_arc170_c [ARC170C] Prefix Mex Sequence

如果有 \(m\ge n\)，那么對(duì)于每一個(gè)時(shí)刻，如果 \(a_i=1\)，只有一種填法，否則肯定有 \(m\) 種填法

如果 \(m< n\)，可能會(huì)出現(xiàn) \(\text{mex}> m\) 的情況，考慮往 \(m+1\) 個(gè)桶里填數(shù)，記 \(f_{i,j}\) 表示考慮了前 \(i\) 個(gè)數(shù)，已經(jīng) \(j\) 個(gè)桶有數(shù)，則有轉(zhuǎn)移：

• 當(dāng) \(a_i=1\) 時(shí)，\(f_{i,j}\rightarrow f_{i+1,j+1}\)
• 當(dāng) \(a_i=0\) 時(shí)，\(f_{i,j}\times j\rightarrow f_{i+1,j}\)
• 當(dāng) \(a_i=0\) 時(shí)，\(f_{i,j}\times(m-j)\rightarrow f_{i+1,j+1}\)

AT_cf16_exhibition_final_e Water Distribution

有點(diǎn)強(qiáng)，，，

不妨讓對(duì) \(0\) 取 \(\max\) 變成直接加上 \(l-\text{dis}\)，這樣在最優(yōu)情況下必然是合法的

如果我們把 \(i\rightarrow j\) 連一條無(wú)向邊，最后肯定會(huì)形成一些樹(shù)，如果形成了環(huán)狀物，肯定浪費(fèi)了更多的水，而且對(duì)于每一棵樹(shù)，其最優(yōu)情況是取到平均數(shù)，即 \(\frac{\sum a-\sum e}{size}\)

枚舉每一個(gè)點(diǎn)集，跑一邊最小生成樹(shù)，最后子集 dp 合并起來(lái)即可，復(fù)雜度 \(\mathcal{O}(n^2\log n2^n+3^n)\)

9.26

AT_hitachi2020_f Preserve Diameter

很牛啊！

我們考慮最后生成的 \(H\)，考察他有什么性質(zhì)，其必然只有一條直徑，否則肯定存在方案使得直徑長(zhǎng)度不變，我們以其直徑一端點(diǎn) \(s\) 為根跑出來(lái)一個(gè) BFS 樹(shù)，發(fā)現(xiàn)對(duì)于這顆樹(shù)上第 \(i\) 層上的點(diǎn)，一定都互相在原圖上連邊，且都與 \(i-1\)、\(i+1\) 層的所有點(diǎn)在原圖上有邊，否則可以連一條上述的邊以使得直徑不變，所以我們發(fā)現(xiàn)，如果每一個(gè)點(diǎn)到 \(s\) 的距離都相等，就可以唯一確定出來(lái)一個(gè) \(H\)，而一個(gè) \(H\) 對(duì)應(yīng)了兩個(gè)相反的 \(\text{dis}\) 數(shù)組，所以我們只需要 dp 出合法的 \(\text{dis}\) 數(shù)組

接下來(lái)刻畫(huà)一下合法的 \(\text{dis}\) 數(shù)組要滿足什么性質(zhì)：

• 有且僅有一個(gè)點(diǎn)滿足 \(\text{dis}=0\)
• 有且僅有一個(gè)點(diǎn)滿足 \(\text{dis}=d\)，\(d\) 是原直徑的長(zhǎng)度
• 所有點(diǎn)都滿足 \(\text{dis}\le d\)
• 對(duì)于原樹(shù)上的點(diǎn) \((u,v)\)，滿足 \(\text{dis}(u,v)\le 1\)

原圖可能有多條直徑，而中點(diǎn)只有一個(gè)，所以我們不妨以直徑中點(diǎn)為根 dp，記狀態(tài) \(f_{u,0/1/2,0/1/2}\)，表示 \(u\) 子樹(shù)內(nèi)，滿足 \(\text{dis}_u-\text{dis}_{v}=maxdep\) 的個(gè)數(shù)為 \(0/1/\ge 2\)，另一維則記的是 \(\text{dis}_v-\text{dis}_u\)

直接 dp 就行了，注意直徑長(zhǎng)度是奇數(shù)的時(shí)候從中邊開(kāi)始 dp 兩顆子樹(shù)，直徑長(zhǎng)度為偶數(shù)只需要從 中點(diǎn)開(kāi)始 dp 就行了，復(fù)雜度線性

CF1194F Crossword Expert

幽默題

記結(jié)束輪數(shù)為 \(x\)，有

答案即為 \(\sum P(x\ge i)\)，求組合數(shù)前綴和可以莫隊(duì)，這題中上界和上指標(biāo)都是單調(diào)的，直接掃一遍就行了

CF785D Anton and School - 2

依舊幽默

枚舉最后一個(gè) (，記前面的 ( 有 \(a\) 個(gè)，后面的 ) 有 \(b\) 個(gè)，那么其貢獻(xiàn)就是

復(fù)雜度線性

#1284. Partition Number

考慮容斥，欽定哪幾個(gè) \(a_i\) 必填，貢獻(xiàn)是 \(p(m-\sum_{i\in S} a_i)\times (-1)^{|S|}\)，容斥系數(shù)直接背包就完了

誒多，分拆數(shù)咋算來(lái)著

想起來(lái)了，把網(wǎng)格圖畫(huà)出來(lái)，中間有一個(gè) \(\sqrt n\times \sqrt n\) 的矩形，枚舉這個(gè)矩形的大小就完了

復(fù)雜度 \(\mathcal{O}(m\sqrt m+nm)\)

AT_abc205_e [ABC205E] White and Black Balls

反射容斥。

AT_arc145_c [ARC145C] Split and Maximize

排序不等式，最優(yōu)一堆是 \(i\times (i+1)\)，答案為 \(n!\times 2^n\times Cat(n)\)

#1261. Inv

求置換 \(P \circ P=I\)，且 \(P\) 的逆序?qū)?shù)等于 \(k\)，發(fā)現(xiàn)此時(shí) \(P=P^{-1}\)，而 \(P\) 的逆序?qū)?shù)等于 \(P^{-1}\) 的逆序?qū)?shù)，直接算逆序?qū)?shù)為 \(k\) 的排列數(shù)即可，寫(xiě)出來(lái) gf 就是 \(\prod \frac{1-x^i}{1-x}=(1-x)^{-n}\prod (1-x^i)\)，直接 bitset 就完了

#308. 【UNR #2】UOJ拯救計(jì)劃

染 \(k\) 的方案數(shù)一定是形如

其中 \(f_i\) 為恰好染 \(i\) 種顏色的方案數(shù)（不分配顏色），那么只有當(dāng) \(i<3\) 的時(shí)候是有用的

當(dāng) \(m=0\) 時(shí)，答案為 \(k^n\)

當(dāng) \(m>0\) 時(shí)，\(f_1\) 沒(méi)有貢獻(xiàn)，\(f_2\) 的貢獻(xiàn)是 \(\binom{k}{2}\times2^c\)，\(c\) 是連通塊個(gè)數(shù)，如果圖中有奇環(huán)就直接寄了

復(fù)雜度線性

#7313. Connected Spanning Subgraph

如果不連通，顯然答案為 \(0\)

考慮每一個(gè)邊子集，給出一種染色方案，將 \(1\) 染成黑色，如果有一條 \((u,v)\) 的邊，那 \(u,v\) 的顏色必須相同，這樣的染色方案有 \(2^{c-1}\) 個(gè)，其中 \(c\) 為這個(gè)邊子集對(duì)應(yīng)的連通塊數(shù)，那我們直接數(shù)這個(gè)染色方案就和原問(wèn)題模 \(2\) 答案一樣了

反過(guò)來(lái)從染色方案考慮邊子集，對(duì)于一個(gè)染色方案，其邊子集合法當(dāng)且僅當(dāng)所有的 \((u,v)\) 都滿足 \(u\) 的顏色等于 \(v\) 的顏色，這樣一個(gè)染色方案對(duì)應(yīng)的合法邊子集個(gè)數(shù)為 \(2^{e}\)，其中 \(e\) 為兩端點(diǎn)顏色相同的邊的個(gè)數(shù)

我們只有在 \(e=0\) 的時(shí)候會(huì)有貢獻(xiàn)，這時(shí)候要求存在一種二染色的方案，即原圖是一個(gè)二分圖

于是原圖是連通二分圖的時(shí)候答案是 \(1\)，否則答案是 \(0\)

P6806 [CEOI 2020] 象棋世界

兵、車、后都是簡(jiǎn)單的

象：

為了使跳躍次數(shù)盡量的少，我們每次都選擇碰壁反彈往下走，這樣操作次數(shù)顯然是最優(yōu)的，我們一直這樣走直到走到了一個(gè) \(x\ge n,y=c_{R}\) 的點(diǎn)，在這個(gè)點(diǎn)之前會(huì)有若干個(gè)拐點(diǎn)，我們可以把一個(gè)拐點(diǎn)往里縮，這樣最后走到的點(diǎn)的 \(x\) 坐標(biāo)會(huì) \(-2\)，那直接插板就行

王：

如果我們直接 dp，\(f_{i,j}=f_{i-1,j-1}+f_{i-1,j}+f_{i-1,j+1}\)，但是有邊界存在，很煩人，所以考慮一個(gè)反射容斥，我們把 dp 數(shù)組寫(xiě)下來(lái)，考慮把 dp 數(shù)組最右邊接一列 \(0\)，然后再把原來(lái)的 dp 數(shù)組左右翻轉(zhuǎn)接在 \(0\) 的右邊，左邊也同理，這樣一直接下去，我們會(huì)驚奇的發(fā)現(xiàn)分界線處的 \(0\) 正好能被 dp 出來(lái)，于是相鄰兩個(gè)框的 dp 數(shù)組是一個(gè)周期，我們只需要做一個(gè)循環(huán)卷積就行了，也就是計(jì)算 \((x+x^{-1}+1)^{R-1} \bmod (x^{2C+2}-1)\)，直接暴力做就行，復(fù)雜度 \(\mathcal{O}(n^2\log n)\)

9.27

打了信友隊(duì)模擬賽！

模擬賽

T1

幽默。

T2

二維數(shù)點(diǎn)。

T3

注意到 \(f_{i,j}=f_{i-1,j-1}\times j+f_{i-1,j}\times j\)，考慮 \(\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix}\)，則有 \(f_{n,k}=k!\begin{Bmatrix}n\\k\end{Bmatrix}\)，直接算 \(\begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{i=0}^{k}(-1)^{k}\binom{k}{i}i^n\) 即可

T4

把每個(gè)點(diǎn)拆成上下兩個(gè)再平衡樹(shù)維護(hù)即可

P6672 [清華集訓(xùn) 2016] 你的生命已如風(fēng)中殘燭

那啥引理。

先把 \(a_i\) 都減一，這樣我們要求的就變成了 \(\sum_{i=1}^{j}a_i\ge 0,\sum_{i=1}^{m}a_i=0\)，考慮如何構(gòu)造一個(gè) Raney 引理的形式，直接在最前面加一個(gè) \(1\)？肯定不對(duì)，因?yàn)檫@樣并不能保證我們最開(kāi)始選的是 \(1\)，觀察一下序列，其中有若干 \(-1\) 和若干非負(fù)整數(shù)，所以我們考慮加一個(gè) \(-1\) 來(lái)構(gòu)造 Raney 引理的形式，如果把折線圖畫(huà)出來(lái)，從右往左讀，這就是我們想要的形式了，這樣相當(dāng)于對(duì) \(a\) 進(jìn)行了什么操作呢？其實(shí)就是取反、翻轉(zhuǎn)之后再算前綴和

然后就能直接算了，根據(jù) Raney 引理，答案大概是 \(\frac{(m+1)!}{m+1}=m!\)，我們還要剔除加進(jìn)去的那個(gè) \(-1\) 的貢獻(xiàn)，這之前有 \(m-n\) 個(gè) \(-1\)，那最后答案就是 \(\frac{m!}{m-n+1}\)

P5900 無(wú)標(biāo)號(hào)無(wú)根樹(shù)計(jì)數(shù)

Eular 變換：

如果 \(F\) 對(duì)應(yīng)的是一個(gè)組合類 \(\mathcal{A}\)，那么 \(\mathcal{E}(F(x))\) 就是 \(\mathcal{A}\) 中所有元素組成的可重集的組合類對(duì)應(yīng)的生成函數(shù)，和 \(\exp\) 不同在于，這里并不是有序集

怎么理解這個(gè)式子？就是大小為 \(i\) 的這一種每次在 \(f_i\) 里面選幾種方案，那這個(gè)式子就是顯然的了

這個(gè)式子實(shí)在是太丑了，去個(gè)對(duì)數(shù)再經(jīng)過(guò)一些自然的代數(shù)推到可以得到：

或者是考慮 Burnside，枚舉每一個(gè)置換環(huán)最后再 \(\exp\) 回去，那對(duì)于一個(gè)長(zhǎng)度為 \(k\) 的置換環(huán)，你的方案是由 \(k\) 個(gè)點(diǎn)選擇了同樣的方案，記這個(gè) EGF 為 \(C_k(x)\)，那么有

把所有的 \(C_k\) 加起來(lái)再 \(\exp\) 就能得到那個(gè)式子

回到本題，先考慮數(shù)有根樹(shù)的方案，則有

也就是去掉根，把其子樹(shù)組合成一個(gè)大小為 \(n-1\) 的東西，然后推一下式子

記 \(G(x)=\sum_i F'(x^i)x^i\)，有 \(g_n=\sum_{d|n}f_d\times d\)

那么有

分治 NTT 即可

然后怎么數(shù)無(wú)根樹(shù)的方案？

經(jīng)典的，考慮根是重心的時(shí)候我們才記錄答案

當(dāng) \(n\) 是奇數(shù)：

如果根不是重心，則必然存在一個(gè)子樹(shù)，滿足其大小大于等于 \(\frac{n+1}{2}\)，那么答案就是

當(dāng) \(n\) 是偶數(shù)：

此時(shí)如果兩個(gè)重心的子樹(shù)大小相同，會(huì)算重一次，那答案就要額外再減去 \(\binom{f_n}{2}\)

復(fù)雜度 \(\mathcal{O}(n\log^2 n)\)

CF1662J Training Camp

容易觀察到的是我們可以給每個(gè)點(diǎn)，讓他往其行列上比他大的點(diǎn)連邊，那我們的限制就是不能存在兩個(gè)被選了的點(diǎn) \((u,v)\)，使得存在一條 \(\le2\) 的路徑能夠從 \(u\) 到達(dá) \(v\)

這個(gè)約束實(shí)在是太丑了，把他放寬到不存在路徑能夠從 \(u\) 到達(dá) \(v\)，如果這個(gè)東西和原問(wèn)題等價(jià)，那么我們只需要求一個(gè)最大權(quán)反鏈，接下來(lái)說(shuō)明其和原問(wèn)題等價(jià)：

考慮取出來(lái)一個(gè)最短的路徑 \(u_1,u_2,\cdots,u_k\)（\(k\ge 3\)），其中 \(u_1\) 和 \(u_k\) 被選了，不妨假設(shè) \(u_1\)、\(u_2\) 在同一行，\(u_2\)、\(u_3\) 在同一列，我們?nèi)〕?\(u_2\)、\(u_3\) 所在那一列的被選的點(diǎn) \(x\)，如果 \(x<u_2\)，則有 \(x,u_3,\cdots,u_k\)，比原來(lái)短，矛盾；如果 \(x>u_2\)，則可以直接構(gòu)造 \(u_1,u_2,x\)，這樣結(jié)論得證

于是我們只需要求一個(gè)最大權(quán)反鏈，經(jīng)典的，拆點(diǎn)連邊 \((u,u')\)，\(u\) 點(diǎn)權(quán)為 \(-c_u\)，\(u'\) 點(diǎn)權(quán) \(c_u\)，對(duì)于原有的 \((u,v)\)，連邊 \((u',v)\)，再跑一個(gè)最大權(quán)閉合子圖就是答案

AT_cf17_final_i Full Tournament

觀察一下樣例，我們不難得到，對(duì)于一個(gè)合法的最終序列，我們每次砍成兩半，會(huì)有右邊的一半對(duì)位偏序左邊的一半，也就是說(shuō)，如果最終 \(i\) 位置上的數(shù)是 \(a_i\)，那么有 \(a_{i}<a_{i+2^k}\)，其中 \(2^k\not \in i\)，只要滿足這個(gè)條件我們就一定能構(gòu)造出來(lái)一種方案！在第 \(n\) 輪，讓 \(a_i\) 和 \(a_{i+2^{n-1}}\) 比賽，然后遞歸子問(wèn)題，我們發(fā)現(xiàn)最后 \(a_i\) 會(huì)被放到二進(jìn)制位相反的位置，那我們求出任意一組合法的 \(a\) 做一遍蝴蝶變換就能得到答案

9.28

#5573. Holiday Regifting

這么聰明啊

考慮按照拓?fù)湫驈男〉酱蠹尤朦c(diǎn)，顯然對(duì)于一個(gè)拓?fù)湫虻那熬Y，其存在一個(gè)周期，我們用一個(gè)變量維護(hù)這個(gè)周期，記作 \(ans\)，同時(shí)記 \(a_i\) 為沒(méi)被加入的那些點(diǎn)，在這個(gè)周期過(guò)后會(huì)有多少點(diǎn)，那么每次加入一個(gè)點(diǎn) \(i\)，周期會(huì)乘上 \(\frac{c_i}{\gcd(a_i,c_i)}\)，同時(shí)給其他沒(méi)被加入的點(diǎn)也乘上這個(gè)數(shù)，復(fù)雜度 \(\mathcal{O}(nm)\)

#4217. Graph Coloring

原來(lái)小廖還給我說(shuō)過(guò)這題

發(fā)現(xiàn) \(\binom{14}{7}>3000\)，于是給每個(gè)點(diǎn)一個(gè)長(zhǎng)度為 \(14\)，\(1\) 的個(gè)數(shù)為 \(7\) 的二進(jìn)制串，然后對(duì)于邊 \((u,v)\)，染色 \(u\) 中為 \(1\) 且 \(v\) 中為 \(0\) 的那一位就行了

為啥是 \(\binom{14}{7}\) 呢，這其實(shí)是讓我們保證不存在互相包含的二進(jìn)制串，這要用到組合數(shù)學(xué)中的一個(gè)定理

Sperner 定理：

• 設(shè) \(S\) 是一個(gè) \(n\) 元集合，則 \(S\) 的子集族 \(F\) 如果是一個(gè)反鏈，那么 \(F\) 的最大大小為 \(\binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}\)。而且，當(dāng) \(F\) 取所有大小為 \(\left\lfloor\frac{n}{2}\right\rfloor\) 的子集時(shí)，達(dá)到這個(gè)最大值。

證明這個(gè)定理，要用到 LYM 不等式

LYM 不等式：

如果 \(F\) 是 \(S\) 的一個(gè)反鏈，那么

如何證明上面的那個(gè)不等式？

• 考慮 \(S\) 的 \(n!\) 個(gè)排列，對(duì)于每個(gè)子集 \(A\in F\)，我們計(jì)算有多少排列滿足 \(A\) 中的元素都出現(xiàn)在 \(S/A\) 的元素之前，那么對(duì)于固定的 \(A\)，滿足上述條件的排列有 \(|A|!(n-|A|)!\) 個(gè)
• 由于 \(F\) 是反鏈，那么對(duì)于任意的 \(A,B\in F\)，不可能 \(A\) 和 \(B\) 同時(shí)上面那個(gè)條件，那么我們可以得到不等式：

• 兩邊同時(shí)除以 \(n!\) 就得到了 LYM 不等式

然后我們要從 LYM 不等式推導(dǎo) Sperner 定理

組合數(shù) \(\binom{n}{k}\) 在 \(k=\left\lfloor\frac{n}{2}\right\rfloor\) 時(shí)取得最大值，所以對(duì)于任意的 \(k\)，都有

LYM 不等式里每一項(xiàng)都用這個(gè)下界估計(jì)，可以得到

所以就能得到 \(|F|\le \binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}\)，同時(shí)我們可以構(gòu)造得到一個(gè) \(F\) 取得這個(gè)上界

#6703. 小 Q 的序列

給出 dp：

這個(gè)實(shí)在是太丑了，如果直接寫(xiě) GF 的話會(huì)多出來(lái)一個(gè) \(x^2\frac{\mathrmw0obha2h00}{\mathrmw0obha2h00x}\)，把他寫(xiě)成斯特林?jǐn)?shù)類似的形式，令第二維等于 \(i-j\)，則有

如果你比較牛逼，可以發(fā)現(xiàn)

那么可以直接

令 \(G_i=F_ie^{-x}\)，則有

分治乘然后多點(diǎn)求值即可

如果你沒(méi)那么牛逼，可以考慮

的組合意義，就是從 \(i\) 個(gè)數(shù)中選若干個(gè)數(shù)劃分到 \(j\) 個(gè)集合中的帶權(quán)方案

• 不選，有 \((a_i+i)\) 的貢獻(xiàn)
• 新開(kāi)一個(gè)集合，有 \(1\) 的貢獻(xiàn)
• 塞到一個(gè)集合里面，貢獻(xiàn)為 \(-j\)

不選的貢獻(xiàn)可以分治乘，選的貢獻(xiàn)，考慮一個(gè)集合的 EGF \(\hat F\)，則有

再對(duì)其 \(\exp\) 就能得到選的答案

#2068. Fast as Ryser

戰(zhàn)勝了一個(gè)快！

把 \(n\) 補(bǔ)成偶數(shù)，然后令 \(2i\) 強(qiáng)制向 \(2i+1\) 連邊，這樣一組合法的匹配在圖上會(huì)形成若干個(gè)鏈和若干個(gè)環(huán)，我們只需要求出鏈和環(huán)的生成函數(shù)再 \(\exp\) 一遍就行了

如何求出鏈和環(huán)的權(quán)值？考慮 dp，先算鏈，記 \(f_{i,s}\)，為終點(diǎn)在 \(i\)，狀態(tài)為 \(s\) 的鏈的答案，直接枚舉下一個(gè)點(diǎn)在哪兒就行了，對(duì)于環(huán)，我們同樣記 \(f_{i,s}\)，但是為了不算重，我們?cè)诿杜e終點(diǎn)的時(shí)候強(qiáng)制讓 \(i\ge \text{lowbit}(s)\)

直接轉(zhuǎn)移，最后還要集合冪級(jí)數(shù) \(\exp\)，總復(fù)雜度 \(\mathcal{O}(n^22^{\frac{n}{2}})\)

F - Fast as Fast as Ryser

戰(zhàn)勝了兩個(gè)快！

仍然用一個(gè)快的方法算出來(lái) \(f\) 和 \(g\)，最后我們要求的就是對(duì)于每一個(gè) \(k\)，求出

直接嗯求是 \(\mathcal{O}(n^32^\frac{n}{2})\)，爆完了，考慮轉(zhuǎn)置原理，我們需要一個(gè)輸入的向量 \(b\)，不妨令 \(b_{S}=[S=U]\)，于是有

轉(zhuǎn)置一下，就是

求解轉(zhuǎn)置問(wèn)題，具體來(lái)說(shuō)，有

求轉(zhuǎn)置算法，就是

這中間其實(shí)有一個(gè)問(wèn)題，我們的 \(/k!\) 怎么辦？發(fā)現(xiàn)在復(fù)合的最開(kāi)始，我們會(huì)求若干次導(dǎo)數(shù)，這樣系數(shù)正好和 \(k!\) 抵消了！所以就不用管 \(/k!\) 的系數(shù)

復(fù)雜度 \(\mathcal{O}(n^22^\frac{n}{2})\)

A - Chords and Checkered

口胡了，不知道對(duì)不對(duì)

算總數(shù)再算黑的減白的

考慮貢獻(xiàn)，每次插一個(gè)線，貢獻(xiàn)就 \(-1,0,1\)

然后前綴和一下算一下，可能會(huì)有一個(gè)帶權(quán)上指標(biāo)求和的東西，直接裂項(xiàng)算應(yīng)該就行了

B - Cyclic Jump

和李思睿想了一個(gè)小時(shí)，想出來(lái) \(0\) 個(gè)有用的東西

記 \(f(a_1,a_2,\cdots,a_n)\) 為最優(yōu)解，不妨設(shè) \(a_1\) 是最小值，我們可以說(shuō)明 \(f(a_1,a_2,\cdots,a_n)=a_1+f(a_1,a_2-a_1,a_3-a_1,\cdots,a_n-a_1)\)，如果我們能夠構(gòu)造一種方案，使得所有不為零的跳到的坐標(biāo)都 \(\ge a_1\)，那么我們可以把第一步和最后一步都拆掉，變成形如 \(a_i-a_1\) 和 \(a_1\)，然后再把坐標(biāo)原點(diǎn)放到 \(a_1\)，這樣就能遞歸子問(wèn)題了。

我們隨便拉出來(lái)一個(gè) \(f(a_1,a_2,\cdots,a_n)\) 的最優(yōu)解，為了構(gòu)造這樣的方案，最后肯定不能存在一個(gè)形如 \(p\rightarrow x\rightarrow q(x< a_1,x<p,q)\) 的谷，這樣我們直接遞歸子問(wèn)題會(huì)出現(xiàn)有點(diǎn)落在負(fù)半軸上，假如 \(p\rightarrow x\) 那一步跳的是 \(-a_i\)，\(x\rightarrow q\) 那一步跳的是 \(+a_j\)，我們可以把前一步變成 \(-(a_i-a_1)\)，后一步變成 \(+(a_j-a_1)\)，這樣會(huì)形成一個(gè) \(p\rightarrow x+a_1\rightarrow q\)，滿足了 \(x+a_1\ge a_1\)，而且 \(a_i-a_1\) 和 \(a_j-a_1\) 也都在 \(\left\{a_1,a_2-a_1,a_3-a_1,\cdots,a_n-a_1\right\}\) 中。我們照此步驟就可以不斷將每一個(gè)谷調(diào)整到 \(\ge a_1\) 的位置，此時(shí)每一步都在集合 \(\left\{a_1,a_2-a_1,a_3-a_1,\cdots,a_n-a_1,a_1,a_2,\cdots ,a_n\right\}\) 中，我們只需要讓當(dāng)前的每一步 \(a_i\) 都拆成 \(a_i-a_1\) 和 \(a_1\)，就可以遞歸子問(wèn)題。于是結(jié)論得證。

那么我們便可以設(shè)計(jì)算法，每次取出最小值 \(a_1\)，把所有 \(>a_1\) 的都減掉 \(a_1\)，直到 \(a_1>0\)，這樣復(fù)雜度是 \(\mathcal{O}(nV)\) 的，注意到如果最小值變動(dòng)，此時(shí)肯定是原來(lái)的 \(a_2\) 成了最小值，它減去了若干輪 \(a_1\)，于是此時(shí)就變成了 \(a_2\bmod a_1\)，那我們沒(méi)必要每一輪都操作，只需要在最小值更替的時(shí)候操作一次就夠了。

分析一下復(fù)雜度，每經(jīng)過(guò)兩輪，最小值至少會(huì)減半，此處可以類似輾轉(zhuǎn)相除法分析，那最終的復(fù)雜度就是 \(\mathcal{O}(n\log \max(A_i))\)。