容斥

記錄一點(diǎn)遇到的容斥題。多學(xué)容斥。

NOI2025 集合

看不懂 B 性質(zhì)咋辦，那得推式子才知道。枚舉 \(f(P)=f(Q)=S\)，并容斥欽定其滿(mǎn)足條件。即

\[\sum_{S}\sum_{S\subseteq T_1}\sum_{S\subseteq T_2}(-1)^{|T1|-|S|}(-1)^{|T2|-|S|}\prod_{P}(1+a_P[T_1\subseteq P]+a_P[T_2\subseteq P]) \]

進(jìn)行一個(gè)式子的推。不妨枚舉 \(T1\cup T2=T\)，即

\[\begin{aligned} &\sum_{S}\sum_{S\subseteq T}\sum_{S\subseteq T_1}\sum_{S\subseteq T_2}(-1)^{|T1|+|T2|}\prod_{T_1\subseteq P}(1+a_P)\prod_{T_2\subseteq P}(1+a_P)\prod_{T\subseteq P} \dfrac{(1+2a_P)}{(1+a_P)^2}\left[T_1\cup T_2=T\right] \\ =&\sum_{S}\sum_{S\subseteq T}\prod_{T\subseteq P} \dfrac{(1+2a_P)}{(1+a_P)^2}\sum_{S\subseteq T_1}\sum_{S\subseteq T_2}(-1)^{|T1|+|T2|}\prod_{T_1\subseteq P}(1+a_P)\prod_{T_2\subseteq P}(1+a_P)\left[T_1\cup T_2=T\right] \end{aligned} \]

然后這個(gè)時(shí)候就初見(jiàn)端倪，因?yàn)榉帜干铣霈F(xiàn)了 \(a+1\)，這下看懂了.png。不急，我們先做 B 性質(zhì)。不妨設(shè) \(w_S=(-1)^{|S|}\prod_{S\subseteq T}(1+a_T)\)，這個(gè)可以高維后綴積做出來(lái)。

\[\begin{aligned} =&\sum_{S}\sum_{S\subseteq T}\prod_{T\subseteq P} \dfrac{(1+2a_P)}{(1+a_P)^2}\sum_{S\subseteq T_1}\sum_{S\subseteq T_2}w_{T_1}w_{T_2}\left[T_1\cup T_2=T\right] \end{aligned} \]

然后這個(gè)時(shí)候我們已經(jīng)愉快地做到了 \(\Theta(3^nn)\)，不過(guò)給的分非常少，因?yàn)檫€依賴(lài) B 性質(zhì)。考慮交換 \(S,T\) 求和順序。

\[\begin{aligned} =&\sum_{T}\prod_{T\subseteq P} \dfrac{(1+2a_P)}{(1+a_P)^2}\sum_{S\subseteq T}\sum_{S\subseteq T_1}\sum_{S\subseteq T_2}w_{T_1}w_{T_2}\left[T_1\cup T_2=T\right] \end{aligned} \]

考察任意一對(duì) \(T_1,T_2\) 會(huì)對(duì)什么產(chǎn)生貢獻(xiàn)。很顯然它會(huì)對(duì) \(2^{|T_1\cap T_2|}\) 個(gè) \(S\) 產(chǎn)生貢獻(xiàn)。所以沒(méi)有必要枚舉 \(S\)。

\[\begin{aligned} =&\sum_{T}\prod_{T\subseteq P} \dfrac{(1+2a_P)}{(1+a_P)^2}\sum_{T_1}\sum_{T_2}w_{T_1}w_{T_2}2^{|T_1\cap T_2|}\left[T_1\cup T_2=T\right] \end{aligned} \]

然而很天才的事情是 \(|T_1\cap T_2|+|T_1\cup T_2|=|T_1|+|T_2|\)，所以我們發(fā)現(xiàn) \(|T_1\cap T_2|=|T_1|+|T_2|-|T_1\cup T_2|=|T_1|+|T_2|-|T|\)。于是

\[\begin{aligned} =&\sum_{T}\prod_{T\subseteq P} \dfrac{(1+2a_P)}{(1+a_P)^2}\sum_{T_1}\sum_{T_2}w_{T_1}w_{T_2}2^{|T_1|+|T_2|-|T|}\left[T_1\cup T_2=T\right] \\ =&\sum_{T}2^{-|T|}\left(\prod_{T\subseteq P} \dfrac{(1+2a_P)}{(1+a_P)^2}\right)\left(\sum_{T_1}\sum_{T_2}w_{T_1}2^{|T_1|}w_{T_2}2^{|T_2|}\left[T_1\cup T_2=T\right]\right) \end{aligned} \]

對(duì)，但是現(xiàn)在我們發(fā)現(xiàn)后半部分是沒(méi)有任何限制的或運(yùn)算卷積，可以 \(\Theta(n2^n)\) 做一下。前半部分也是高維后綴積。所以現(xiàn)在整個(gè) B 性質(zhì)全部可以通過(guò)，拼上暴力可以獲得 \(56\sim 68\) 分。

那咋辦。感覺(jué)上你要做到這個(gè)避免除以 \(0\) 的唯一方法就是記有幾個(gè) \(0\) 在因子里：換種說(shuō)法，我要表達(dá)的意思是，把 \(0\) 看做一個(gè)元 \(x\) 這樣。然后我們要做的就是求一個(gè) \(\lim\limits_{x\to 0} \dfrac{F(x)}{G(x)}\)。因?yàn)?\(G\) 此時(shí)是一個(gè)單項(xiàng)式，不妨考查 \(F(x)\) 的最低次項(xiàng)。如果 \(F\) 的最低次項(xiàng) \(> G\) 的，則答案為 \(0\)；否則答案為 \(F\) 與 \(G\) 最低次項(xiàng)系數(shù)的比。

我們可以證明 \(F\) 的最低此項(xiàng)不會(huì) \(<G\) 即極限無(wú)意義，因?yàn)?\(w_T\) 的次數(shù)在每一維上都是不增的，所以取 \(T_1=T_2=T\) 時(shí)帶來(lái)的次數(shù)最小，發(fā)現(xiàn)此時(shí)其次數(shù)也已經(jīng) \(=\deg G\)。

所以對(duì)做法進(jìn)行改編：我們維護(hù)每個(gè)點(diǎn)的最低次項(xiàng)次數(shù)，F(xiàn)MT 時(shí)是極好合并的。

復(fù)雜度 \(\Theta(n2^n)\)，可以通過(guò)。

PA 2019 Final 數(shù)圖

先瞎刻畫(huà)刻畫(huà)，就是這個(gè)有兩個(gè)長(zhǎng)為 \(n\) 的序列 \(a,b\)，要求 \(a_i\neq i,b_i\neq i,a_i\neq b_i\)，且 \(1\sim n\) 在里面都出現(xiàn)了恰好 \(2\) 次，方案數(shù)除以 \(2^n\) 就是要的答案。

呃，那就容斥，欽定 \(x\) 個(gè) \(a_i=b_i\)，\(y\) 個(gè) \(a_i\neq i\) 或 \(b_i\neq i\)，\(z\) 個(gè)都滿(mǎn)足。那么容斥系數(shù)會(huì)是 \((-1)^{x+y-z}\)。考慮其方案數(shù)。

首先算 \(x-z\) 這些位置的方案數(shù)。就是 \(n-y\) 個(gè)數(shù)里面，選出 \(x-z\) 個(gè)數(shù)填進(jìn)去，每個(gè)位置都不是 \(i\)。假設(shè) \(n\) 個(gè)數(shù)選 \(m\) 個(gè)數(shù)使得每個(gè)位置都不是 \(i\) 的方案數(shù)是 \(f_{n,m}\)。那么容斥可以得到

\[f_{n,m}=\sum_{i=0}^m \dbinom mi (-1)^i \dfrac{(n-i)!}{(n-m)!} \]

所以這些位置的貢獻(xiàn)是 \(f_{x-z,n-y}\)。然后考慮 \(y-z\) 這些數(shù)要?dú)J定是 \(a\) 還是 \(b\) 不滿(mǎn)足條件，帶來(lái) \(2^{y-z}\) 的貢獻(xiàn)。剩下的還有 \(y-z\) 個(gè)數(shù)和 \(2(n-x-y+z)\) 個(gè)數(shù)沒(méi)有填；不妨假設(shè)還沒(méi)填的數(shù)兩兩不同，最后再將系數(shù)除以被算多的 \(2^{n-x-y+z}\)。前半部分的貢獻(xiàn)是 \(f_{2(n-x-y+z)+y-z,y-z}\)，后半部分是 \((2(n-x-y+z))!\)。乘在一起即可。還要記得算欽定位置對(duì)應(yīng)的系數(shù)，是平凡的。復(fù)雜度三次方。

清華集訓(xùn) 2014 主旋律

太經(jīng)典了。

考慮用枚舉一些東西得到的式子表示總方案數(shù) \(2^m\)。然后會(huì)得到

\[2^{m}=\sum_{i=1}^n F(i)\sum_{S}g_{S,i}2^{M(S,U/S)+M(U/S)} \]

意思是，枚舉入度為 \(0\) 的強(qiáng)連通分量個(gè)數(shù) \(i\)，欽定有 \(i\) 個(gè)（注意這里是欽定，所以我們事實(shí)上需要使用容斥系數(shù) \(F(i)\) 將每個(gè) \(i\) 得到它應(yīng)得的系數(shù)）。\(g_{S,i}\) 是 \(S\) 內(nèi)選邊方案使得它是 \(i\) 個(gè)強(qiáng)連通分量的方案數(shù)。

考慮對(duì)于一種實(shí)際情況有 \(x\) 個(gè)入度為 \(0\) 的強(qiáng)連通分量；那么我們希望它的貢獻(xiàn)是 \(1\)。并且對(duì)于 \(i\le x\) 都會(huì)統(tǒng)計(jì)它，被統(tǒng)計(jì) \(\dbinom xi\) 次。于是

\[\sum_{i=1}^x \dbinom xi F(i)=1 \]

可以推得 \(F(i)=(-1)^{i+1}\)。然后你考慮把 \(i=1,S=U\) 單獨(dú)分離出來(lái)就可以得到答案。\(g_{S,i}\) 的貢獻(xiàn)是可以拆掉的，只要把 \(-1\) 的系數(shù)扔進(jìn) dp 就行了。精細(xì)實(shí)現(xiàn)可以 \(\Theta(3^n)\) 但是我不想實(shí)現(xiàn)。

聯(lián)合省選 2025 歲月

[某知名選手]：感謝你，所有在 D2T2 放非多項(xiàng)式復(fù)雜度題目的出題人。愿你們的媽媽在天堂相遇。

好吧，我們假設(shè)沿用了主旋律的做法，現(xiàn)在這個(gè) C 性質(zhì)就是要我們求這個(gè)圖入度為 \(0\) 的強(qiáng)連通分量恰有一個(gè)的方案數(shù)。

也就是，仍考慮枚舉 \(i,S\)：

\[ans=\sum_{i=1}^n F(i)\sum_{S}g_{S,i}2^{M(S,U/S)+M(U/S)} \]

對(duì)于一種合法方案，假設(shè)有 \(x\) 個(gè)入度為 \(0\) 的強(qiáng)聯(lián)通分量：會(huì)被計(jì)算 \(\dbinom xi\) 次。這次我們希望

\[\sum_{i=1}^x \dbinom xi F(i)=[x=1] \]

于是我們可以得到，\(F(i)=i(-1)^{i+1}\)。看起來(lái)完全正確！

但是這樣我們?cè)趺囱赜弥暗淖龇ㄗ龅?\(3^n\) 呢？你發(fā)現(xiàn)，呃，就是這個(gè) \(-1\) 的貢獻(xiàn)就沒(méi)辦法簡(jiǎn)單地拆開(kāi)了，那咋辦。

考慮令

\[G_S=\sum_{i=1}^n (-1)^i g_{S,i} \]

\[H_S=\sum_{i=1}^n (-1)^i i g_{S,i} \]

考慮 \(g_{S,i}\) 的定義，然后把式子帶進(jìn)去拆開(kāi)就行。發(fā)現(xiàn)也可以?xún)?yōu)化掉。

「KDOI-11」彩燈晚會(huì)

首先把所有點(diǎn)重標(biāo)號(hào)使得 \(1\sim n\) 是一個(gè)拓?fù)湫颍褂猛負(fù)渑判蛲瓿伞?/p>

平方的組合意義太典了啊，那就等價(jià)于你選定兩條長(zhǎng)為 \(l\) 的路徑，欽定它們顏色相同。假設(shè)一個(gè)路徑的點(diǎn)集為 \(X\) 另一個(gè)為 \(Y\)。產(chǎn)生的貢獻(xiàn)是

\[k^{n-|X\cup Y|+1}W(X)W(Y) \]

其中

\[W(S)=\prod_{i=2}^{|S|}w(S_{i-1},S_i) \]

\[\begin{aligned} &\sum_{S} k^{n-2l+1+|S|}\sum_{S\subseteq T}(-1)^{|T|-|S|}\left(\sum_{T\subseteq X,|X|=l} W(X)\right)^2 \\ =&k^{n-2l+1}\sum_{T}(-1)^{|T|}\left(\sum_{T\subseteq X,|X|=l} W(X)\right)^2 \sum_{S\subseteq T} (-k)^{|S|}\\ =&k^{n-2l+1}\sum_{T}(k-1)^{|T|}\left(\sum_{T\subseteq X,|X|=l} W(X)\right)^2 \\ \end{aligned} \]

其實(shí)這個(gè)時(shí)候看起來(lái)就好做了，為什么呢？考慮確定一個(gè) \(T\)，那么 \(X,Y\) 的元素事實(shí)上會(huì)被 \(T\) 分成若干個(gè)區(qū)間；那么我們對(duì)一個(gè)區(qū)間處理出 \(f_{l,r,i}\) 表示選定 \(l, r\)，中間額外選了 \(i\) 個(gè)元素的所有合法 \(S\) 的 \(W(S)\) 之和，這個(gè)可以 \(\Theta(n^3l)\) 處理出來(lái)；再進(jìn)行 dp，即 \(g_{i,x,y}\) 表示考慮了 \(1\sim i\) 并欽定 \(i\in T\)，此時(shí) \(|X|\cap [1,i]=x,|Y|\cap [1,i]=y\) 的貢獻(xiàn)之和。

暴力轉(zhuǎn)移需要枚舉 \(j\) 表示 \(i\) 在 \(T\) 中的前驅(qū)，以及 \([j,i]\) 段 \(X\) 和 \(Y\) 選了幾個(gè)，做形如二維卷積的轉(zhuǎn)移。復(fù)雜度 \(\Theta(n^2l^4)\)，可以獲得隨機(jī)分?jǐn)?shù)，總之無(wú)法獲得滿(mǎn)分。

考慮直接分步卷積，先卷第一維再卷第二維即可，因?yàn)樨暙I(xiàn)系數(shù)是可拆的。復(fù)雜度 \(\Theta(n^2l^3)\)，可以獲得 \([88,100]\) 分，因?yàn)榭ǔ４蟾怕蕸](méi)辦法獲得滿(mǎn)分。。

DFS Order 4

太帥了。

如果你在做一個(gè)計(jì)數(shù)題，不妨先考慮判定一個(gè)主體是否合法。對(duì)于一個(gè) dfs 序，我們可以這樣反著構(gòu)建一棵樹(shù)：維護(hù)“當(dāng)前點(diǎn)”，如果要加入的點(diǎn)編號(hào)大于當(dāng)前點(diǎn)，則直接掛為兒子，并挪上去；否則往上跳到分界點(diǎn)，以分界點(diǎn)上邊為兄弟（即掛在其父親下）。那么計(jì)數(shù)的主體變?yōu)椋耗鼙粯?gòu)建出來(lái)的樹(shù)方案數(shù)。

首先考慮這些樹(shù)滿(mǎn)足什么性質(zhì)：對(duì)于一個(gè)不是其父親的第一個(gè)兒子的點(diǎn)，其必然需要小于其上一個(gè)兄弟的最后一個(gè)兒子的編號(hào)。如果其大于，那么肯定不會(huì)被掛在這里。如果最后一個(gè)兒子不存在呢？可以證明，不存在這種情況；即，所有葉子都是以父親的最后一個(gè)兒子形式出現(xiàn)的，同樣不難證明。

對(duì)于兩棵不同的樹(shù)，有可能形態(tài)不同，也有可能標(biāo)號(hào)不同，考慮固定其形態(tài)，計(jì)算其標(biāo)號(hào)方案。其形態(tài)要求即所有葉子都是父親的最后一個(gè)兒子。標(biāo)號(hào)呢？在有被欽定大小關(guān)系的點(diǎn)之間連邊，大的連向小的；現(xiàn)在我們得到了類(lèi)似于 dag 拓?fù)湫蛴?jì)數(shù)的東西。

。事實(shí)上我們可以刪掉很多邊。因?yàn)槿绻粋€(gè)點(diǎn)不是其父親的第一個(gè)兒子，則他到父親的邊是不必要的，因?yàn)槲覀円呀?jīng)欽定了它大于上一個(gè)兒子，而第一個(gè)兒子大于父親。這等價(jià)于我們用類(lèi)似于左兒子右兄弟的方式表達(dá)了這棵樹(shù)，不過(guò)這無(wú)所謂，關(guān)鍵的在于如何處理那些“小于其上一個(gè)兄弟的最后一個(gè)兒子的編號(hào)”的限制。

我們很幸運(yùn)，因?yàn)橛幸恍┖芷婷畹挠^察：你選中這些限制邊的任意子集，不在子集中的邊先扔掉，在子集里的保留并反向，然后再扔掉一些無(wú)用的原有限制邊，那么你會(huì)得到一棵樹(shù)！而樹(shù)的拓?fù)湫蚴呛糜?jì)算的，即 \(n!\prod \dfrac{1}{siz!}\)。

假設(shè)這棵樹(shù)形態(tài)固定，于是我們欽定容斥。那么容斥系數(shù)必然是 \((-1)^{|S|}\)。感性很容易理解，理性分析即對(duì)于任意一種有 \(k\) 條不滿(mǎn)足的方案，會(huì)被計(jì)入 \(\sum_{i=0}^k \dbinom ki F_i\) 次，解得 \(F_i=(-1)^i\)。繼續(xù)觀察發(fā)現(xiàn)，我們可以將上面保留內(nèi)向樹(shù)的過(guò)程簡(jiǎn)化為：保留每個(gè)點(diǎn)第一個(gè)兒子到自己的限制，而對(duì)每個(gè)非其父親第一個(gè)兒子的點(diǎn)，以 \(1\) 的系數(shù)連它到它上一個(gè)兄弟的邊，以 \(-1\) 的系數(shù)連它到它上一個(gè)兄弟最后一個(gè)兒子的邊。

直接對(duì)原問(wèn)題做 dp：\(f_{i,j}\) 表示，當(dāng)前有一棵樹(shù)大小為 \(i\)，其右側(cè)有一棵樹(shù)大小為 \(j\)，\(j\) 需要選擇連 \(i\) 或者 \(i\) 的最后一個(gè)兒子，容斥系數(shù)及貢獻(xiàn)之和（不計(jì)算 \(j\) 內(nèi)的系數(shù)）；令 \(g_{i,j}\) 表示，當(dāng)前有若干棵樹(shù)，大小和為 \(i\)，在最后一棵樹(shù)的根上掛了一棵大小為 \(j\) 的樹(shù)（這里的“掛”指的是，這棵 \(j\) 樹(shù)在原樹(shù)上和 \(i\) 同地位，而被欽定限制的外向樹(shù)連上 \(i\)），容斥系數(shù)及貢獻(xiàn)之和（不計(jì)算 \(j\) 內(nèi)的系數(shù)）。轉(zhuǎn)移是簡(jiǎn)單的，做到小常數(shù)三次方。

P10004 [集訓(xùn)隊(duì)互測(cè) 2023] Permutation Counting 2

喜提最劣解。

考慮欽定原排列 \(i\) 個(gè)位置 \(<\)，則等價(jià)于把排列劃分為 \(n-i\) 條鏈。那么從小到大填數(shù)：每個(gè)數(shù)選擇一條鏈，得到一個(gè)長(zhǎng)為 \(n\) 值域?yàn)?\([1,n-i]\) 的序列 \(s\)，要求 \([1,n-i]\) 都在里面至少出現(xiàn)一次。對(duì)所有 \(j\) 計(jì)算 \(\sum [s_i\le s_{i+1}]=j\) 的 \(s\) 個(gè)數(shù)。

假設(shè)上述答案記為 \(f_{i,j}\)，則有 \(f_{i,j}=\sum_{l=j}^{n-1} \binom {l}{j} ans_{l,j}\)，可以二項(xiàng)式反演出來(lái) \(ans_{i,j}\)。考慮算出 \(f_{i,j}\)。

即我們要對(duì)所有 \(i,j\) 算長(zhǎng)為 \(n\) 值域?yàn)?\(i\) 非嚴(yán)格上升對(duì)數(shù)為 \(j\)，且 \([1,i]\) 內(nèi)數(shù)全部出現(xiàn)的 \(s\) 個(gè)數(shù)。考慮先容斥掉全部出現(xiàn)的限制，發(fā)現(xiàn)轉(zhuǎn)化后形式相同。現(xiàn)在對(duì)所有 \(i,j\) 算長(zhǎng)為 \(n\) 值域?yàn)?\(i\) 非嚴(yán)格上升對(duì)數(shù)為 \(j\) 的 \(s\) 個(gè)數(shù)。

繼續(xù)改為欽定 \(q\) 個(gè)位置是非嚴(yán)格上升的，最后繼續(xù)二項(xiàng)式反演回來(lái)；枚舉值域 \(v\)，假設(shè)劃分成了長(zhǎng)度為 \(w_1,w_2,\dots,w_{n-q}\) 的若干段，則方案數(shù)為

\[\prod_{t=1}^{n-q}\dbinom{v-1+w_t}{v-1} \]

令 \(k=n-q\)。考慮直接上生成函數(shù)，一段的生成函數(shù)為：

\[F_1(x)=\sum_{i=1}^{+\infty} \dbinom{i+v-1}{v-1}x^i=\dfrac{1}{(1-x)^v}-1 \]

所以 \(k\) 段應(yīng)該是

\[\begin{aligned} F_k(x)&=\left(\dfrac{1}{(1-x)^v}-1\right)^k \\ &=\sum_{i=0}^k \dbinom ki (-1)^{k-i}\dfrac{1}{(1-x)^{vi}} \\ \end{aligned} \]

則

\[\begin{aligned} [x^n]F_k(x) &=\sum_{i=0}^k \dbinom ki (-1)^{k-i}\dbinom{n+vi-1}{n} \\ \end{aligned} \]

考慮預(yù)處理出 \(i\in [0,n^2)\) 的所有 \(\dbinom{i+n}n\)，這個(gè)是簡(jiǎn)單的；那么我們可以三次方計(jì)算所有 \((v,q)\) 形如“值域?yàn)?\(v\) 長(zhǎng)為 \(n\)，欽定了 \(q\) 個(gè)非嚴(yán)格上升對(duì)”的序列個(gè)數(shù)。

于是我們也可以二項(xiàng)式反演回來(lái)，得到“值域?yàn)?\(v\) 長(zhǎng)為 \(n\)，恰好有 \(q\) 個(gè)非嚴(yán)格上升對(duì)”的序列個(gè)數(shù)。

于是我們也可以二項(xiàng)式反演回來(lái)，得到“值域?yàn)?\(v\) 長(zhǎng)為 \(n\)，保證 \([1,v]\) 都至少出現(xiàn)一次，恰好有 \(q\) 個(gè)非嚴(yán)格上升對(duì)”的序列個(gè)數(shù)。

于是我們也可以二項(xiàng)式反演回來(lái)，得到原問(wèn)題的答案。

每次二項(xiàng)式反演都是三次方的，所以就做完了。

寫(xiě)完發(fā)現(xiàn)要跑 15s，就嗯卡常，然后上了個(gè) barrett，以 4.87s 極限通過(guò)。

posted @ 2025-07-21 15:23 Erine 閱讀(86) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

Erine

Answers

容斥