容斥原理

引入

入門例題

假設班裏有 \(10\) 個學生喜歡數學，\(15\) 個學生喜歡語文，\(21\) 個學生喜歡編程，班裏至少喜歡一門學科的有多少個學生呢？

是 \(10+15+21=46\) 個嗎？不是的，因為有些學生可能同時喜歡數學和語文，或者語文和編程，甚至還有可能三者都喜歡。

為了敍述方便，我們把喜歡語文、數學、編程的學生集合分別用 \(A,B,C\) 表示，則學生總數等於 \(|A\cup B\cup C|\)。剛才已經講過，如果把這三個集合的元素個數 \(|A|,|B|,|C|\) 直接加起來，會有一些元素重複統計了，因此需要扣掉 \(|A\cap B|,|B\cap C|,|C\cap A|\)，但這樣一來，又有一小部分多扣了，需要加回來，即 \(|A\cap B\cap C|\)。即

\[ |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C| \]

容斥原理 - venn 圖示例

把上述問題推廣到一般情況，就是我們熟知的容斥原理。

定義

設 U 中元素有 n 種不同的屬性，而第 i 種屬性稱為 \(P_i\)，擁有屬性 \(P_i\) 的元素構成集合 \(S_i\)，那麼

\[ \begin{aligned} \left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\cdots\\ &+(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^{m}S_{a_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n| \end{aligned} \]

即

\[ \left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right| \]

證明

對於每個元素使用二項式定理計算其出現的次數。對於元素 x，假設它出現在 \(T_1,T_2,\cdots,T_m\) 的集合中，那麼它的出現次數為

\[ \begin{aligned} Cnt=&|\{T_i\}|-|\{T_i\cap T_j|i<j\}|+\cdots+(-1)^{k-1}\left|\left\{\bigcap_{i=1}^{k}T_{a_i}|a_i<a_{i+1}\right\}\right|\\ &+\cdots+(-1)^{m-1}|\{T_1\cap\cdots\cap T_m\}|\\ =&\dbinom{m}{1}-\dbinom{m}{2}+\cdots+(-1)^{m-1}\dbinom{m}{m}\\ =&\dbinom{m}{0}-\sum_{i=0}^m(-1)^i\dbinom{m}{i}\\ =&1-(1-1)^m=1 \end{aligned} \]

於是每個元素出現的次數為 1，那麼合併起來就是並集。證畢。

補集

對於全集 U 下的 集合的並 可以使用容斥原理計算，而集合的交則用全集減去 補集的並集 求得：

\[ \left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right| \]

右邊使用容斥即可。

可能接觸過容斥的讀者都清楚上述內容，而更關心的是容斥的應用

那麼接下來我們給出 3 個層次不同的例題來為大家展示容斥原理的應用。

不定方程非負整數解計數

給出不定方程 \(\sum_{i=1}^nx_i=m\) 和 \(n\) 個限制條件 \(x_i\leq b_i\)，其中 \(m,b_i \in \mathbb{N}\). 求方程的非負整數解的個數。

沒有限制時

如果沒有 \(x_i<b_i\) 的限制，那麼不定方程 \(\sum_{i=1}^nx_i=m\) 的非負整數解的數目為 \(\dbinom{m+n-1}{n-1}\).

略證：插板法。

相當於你有 \(m\) 個球要分給 \(n\) 個盒子，允許某個盒子是空的。這個問題不能直接用組合數解決。

於是我們再加入 \(n-1\) 個球，於是問題就變成了在一個長度為 \(m+n-1\) 的球序列中選擇 \(n-1\) 個球，然後這個 \(n-1\) 個球把這個序列隔成了 \(n\) 份，恰好可以一一對應放到 \(n\) 個盒子中。那麼在 \(m+n-1\) 個球中選擇 \(n-1\) 個球的方案數就是 \(\dbinom{m+n-1}{n-1}\)。

容斥模型

接着我們嘗試抽象出容斥原理的模型：

全集 U：不定方程 \(\sum_{i=1}^nx_i=m\) 的非負整數解
元素：變量 \(x_i\).
屬性：\(x_i\) 的屬性即 \(x_i\) 滿足的條件，即 \(x_i\leq b_i\) 的條件

目標：所有變量滿足對應屬性時集合的大小，即 \(|\bigcap_{i=1}^nS_i|\).

這個東西可以用 \(\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|\) 求解。\(|U|\) 可以用組合數計算，後半部分自然使用容斥原理展開。

那麼問題變成，對於一些 \(\overline{S_{a_i}}\) 的交集求大小。考慮 \(\overline{S_{a_i} }\) 的含義，表示 \(x_{a_i}\geq b_{a_i}+1\) 的解的數目。而交集表示同時滿足這些條件。因此這個交集對應的不定方程中，有些變量有 下界限制，而有些則沒有限制。

能否消除這些下界限制呢？既然要求的是非負整數解，而有些變量的下界又大於 \(0\)，那麼我們直接 把這個下界減掉，就可以使得這些變量的下界變成 \(0\)，即沒有下界啦。因此對於

\[ \left|\bigcap_{a_i<a_{i+1} }^{1\leq i\leq k}S_{a_i}\right| \]

的不定方程形式為

\[ \sum_{i=1}^nx_i=m-\sum_{i=1}^k(b_{a_i}+1) \]

於是這個也可以組合數計算啦。這個長度為 \(k\) 的 \(a\) 數組相當於在枚舉子集。

HAOI2008 硬幣購物

4 種面值的硬幣，第 i 種的面值是 \(C_i\)。\(n\) 次詢問，每次詢問給出每種硬幣的數量 \(D_i\) 和一個價格 \(S\)，問付款方式。

\(n\leq 10^3,S\leq 10^5\).

如果用揹包做的話複雜度是 \(O(4nS)\)，無法承受。這道題最明顯的特點就是硬幣一共只有四種。抽象模型，其實就是讓我們求方程 \(\sum_{i=1}^4C_ix_i=S,x_i\leq D_i\) 的非負整數解的個數。

採用同樣的容斥方式，\(x_i\) 的屬性為 \(x_i\leq D_i\). 套用容斥原理的公式，最後我們要求解

\[ \sum_{i=1}^4C_ix_i=S-\sum_{i=1}^kC_{a_i}(D_{a_i}+1) \]

也就是無限揹包問題。這個問題可以預處理，算上詢問，總複雜度 \(O(4S+2^4n)\)。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const long long S = 1e5 + 5;
long long c[5], d[5], n, s;
long long f[S];

int main() {
  scanf("%lld%lld%lld%lld%lld", &c[1], &c[2], &c[3], &c[4], &n);
  f[0] = 1;
  for (long long j = 1; j <= 4; j++)
    for (long long i = 1; i < S; i++)
      if (i >= c[j]) f[i] += f[i - c[j]];  // f[i]：价格为i时的硬币组成方法数
  for (long long k = 1; k <= n; k++) {
    scanf("%lld%lld%lld%lld%lld", &d[1], &d[2], &d[3], &d[4], &s);
    long long ans = 0;
    for (long long i = 1; i < 16;
         i++) {  // 容斥，因为物品一共有4种，所以从1到2^4-1=15循环
      long long m = s, bit = 0;
      for (long long j = 1; j <= 4; j++) {
        if ((i >> (j - 1)) % 2 == 1) {
          m -= (d[j] + 1) * c[j];
          bit++;
        }
      }
      if (m >= 0) ans += (bit % 2 * 2 - 1) * f[m];
    }
    printf("%lld\n", f[s] - ans);
  }
  return 0;
}

完全圖子圖染色問題

前面的三道題都是容斥原理的正向運用，這道題則需要用到容斥原理逆向分析。

完全圖子圖染色問題

A 和 B 喜歡對圖（不一定連通）進行染色，而他們的規則是，相鄰的結點必須染同一種顏色。今天 A 和 B 玩遊戲，對於 \(n\) 階 完全圖 \(G=(V,E)\)。他們定義一個估價函數 \(F(S)\)，其中 S 是邊集，\(S\subseteq E\).\(F(S)\) 的值是對圖 \(G'=(V,S)\) 用 \(m\) 種顏色染色的總方案數。他們的另一個規則是，如果 \(|S|\) 是奇數，那麼 A 的得分增加 \(F(S)\)，否則 B 的得分增加 \(F(S)\). 問 A 和 B 的得分差值。

數學形式

一看這道題的算法趨向並不明顯，因此對於棘手的題目首先抽象出數學形式。得分差即為奇偶對稱差，可以用 -1 的冪次來作為係數。我們求的是

\[ Ans=\sum_{S\subseteq E}(-1)^{|S|-1}F(S) \]

容斥模型

相鄰結點染同一種顏色，我們把它當作屬性。在這裏我們先不遵守染色的規則，假定我們用 m 種顏色直接對圖染色。對於圖 \(G'=(V,S)\)，我們把它當作元素。屬性 \(x_i=x_j\) 的含義是結點 i,j 染同色（注意，並未要求 i,j 之間有連邊）。

而屬性 \(x_i=x_j\) 對應的集合定義為 \(Q_{i,j}\)，其含義是所有滿足該屬性的圖 \(G'\) 的染色方案，集合的大小就是滿足該屬性的染色方案數，集合內的元素相當於所有滿足該屬性的圖 \(G'\) 的染色圖。

回到題目，「相鄰的結點必須染同一種顏色」，可以理解為若干個 \(Q\) 集合的交集。因此可以寫出

\[ F(S)=\left|\bigcap_{(i,j)\in S}Q_{i,j}\right| \]

上述式子右邊的含義就是説對於 S 內的每一條邊 \((i,j)\) 都滿足 \(x_i=x_j\) 的染色方案數，也就是 \(F(S)\).

是不是很有容斥的味道了？由於容斥原理本身沒有二元組的形式，因此我們把所有的邊 \((i,j)\) 映射到 \(T=\frac{n(n+1)}{2}\) 個整數上，假設將 \((i,j)\) 映射為 \(k,1\leq k\leq T\)，同時 \(Q_{i,j}\) 映射為 \(Q_k\). 那麼屬性 \(x_i=x_j\) 則定義為 \(P_k\).

同時 S 可以表示為若干個 k 組成的集合，即 \(S\iff K=\{k_1,k_2,\cdots,k_m\}\).（也就是説我們在邊集與數集間建立了等價關係）。

而 E 對應集合 \(M=\left\{1,2,\cdots,\frac{n(n+1)}{2}\right\}\). 於是乎

\[ F(S)\iff F(\{ {k_i}\})=\left|\bigcap_{k_i}Q_{k_i}\right| \]

逆向分析

那麼要求的式子展開

\[ \begin{aligned} Ans &= \sum_{K\subseteq M}(-1)^{|K|-1}\left|\bigcap_{k_i\in K}Q_{k_i}\right|\\ &= \sum_{i}|Q_i|-\sum_{i<j}|Q_i\cap Q_j|+\sum_{i<j<k}|Q_i\cap Q_j\cap Q_k|-\cdots+(-1)^{T-1}\left|\bigcap_{i=1}^TQ_i\right| \end{aligned} \]

於是就出現了容斥原理的展開形式，因此對這個式子逆向推導

\[ Ans=\left|\bigcup_{i=1}^TQ_i\right| \]

再考慮等式右邊的含義，只要滿足 \(1\sim T\) 任一條件即可，也就是存在兩個點同色（不一定相鄰）的染色方案數！而我們知道染色方案的全集是 \(U\)，顯然 \(|U|=m^n\). 而轉化為補集，就是求兩兩異色的染色方案數，即 \(A_m^n=\frac{m!}{n!}\). 因此

\[ Ans=m^n-A_m^n \]

解決這道題，我們首先抽象出題目數學形式，然後從題目中信息量最大的條件，\(F(S)\) 函數的定義入手，將其轉化為集合的交併補。然後將式子轉化為容斥原理的形式，並 逆向推導 出最終的結果。這道題體現的正是容斥原理的逆用。

數論中的容斥

使用容斥原理能夠巧妙地求解一些數論問題。

容斥原理求最大公約數為 k 的數對個數

考慮下面的問題：

求最大公約數為 \(k\) 的數對個數

設 \(1 \le x, y \le N\)，\(f(k)\) 表示最大公約數為 \(k\) 的有序數對 \((x, y)\) 的個數，求 \(f(1)\) 到 \(f(N)\) 的值。

這道題固然可以用歐拉函數或莫比烏斯反演的方法來做，但是都不如用容斥原理來的簡單。

由容斥原理可以得知，先找到所有以 \(k\) 為 公約數 的數對，再從中剔除所有以 \(k\) 的倍數為 公約數 的數對，餘下的數對就是以 \(k\) 為 最大公約數 的數對。即 \(f(k)=\) 以 \(k\) 為 公約數 的數對個數 \(-\) 以 \(k\) 的倍數為 公約數 的數對個數。

進一步可發現，以 \(k\) 的倍數為 公約數 的數對個數等於所有以 \(k\) 的倍數為 最大公約數 的數對個數之和。於是，可以寫出如下表達式：

\[ f(k)= \lfloor (N/k) \rfloor ^2 - \sum_{i=2}^{i*k \le N} f(i*k) \]

由於當 \(k>N/2\) 時，我們可以直接算出 \(f(k)= \lfloor (N/k) \rfloor ^2\)，因此我們可以倒過來，從 \(f(N)\) 算到 \(f(1)\) 就可以了。於是，我們使用容斥原理完成了本題。

for (long long k = N; k >= 1; k--) {
  f[k] = (N / k) * (N / k);
  for (long long i = k + k; i <= N; i += k) f[k] -= f[i];
}

上述方法的時間複雜度為 \(O( \sum_{i=1}^{N} N/i)=O(N \sum_{i=1}^{N} 1/i)=O(N \log N)\)。

附贈三倍經驗供大家練手。

容斥原理推導歐拉函數

考慮下面的問題：

歐拉函數公式

求歐拉函數 \(\varphi(n)\)。其中 \(\varphi(n)=|\{1\leq x\leq n|\gcd(x,n)=1\}|\)。

直接計算是 \(O(n\log n)\) 的，用線性篩是 \(O(n)\) 的，杜教篩是 \(O(n^{\frac{2}{3}})\) 的（話説一道數論入門題用容斥做為什麼還要扯到杜教篩上），接下來考慮用容斥推出歐拉函數的公式

判斷兩個數是否互質，首先分解質因數

\[ n=\prod_{i=1}^k{p_i}^{c_i} \]

那麼就要求對於任意 \(p_i\)，\(x\) 都不是 \(p_i\) 的倍數，即 \(p_i\nmid x\). 把它當作屬性，對應的集合為 \(S_i\)，因此有

\[ \varphi(n)=\left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right| \]

全集大小 \(|U|=n\)，而 \(\overline{S_i}\) 表示的是 \(p_i\mid x\) 構成的集合，顯然 \(|\overline{S_i}|=\frac{n}{p_i}\)，並由此推出

\[ \left|\bigcap_{a_i<a_{i+1}}S_{a_i}\right|=\frac{n}{\prod p_{a_i}} \]

因此可得

\[ \begin{aligned} \varphi(n)&=n-\sum_{i}\frac{n}{p_i}+\sum_{i<j}\frac{n}{p_ip_j}-\cdots+(-1)^k\frac{n}{p_1p_2\cdots p_n}\\ &=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)\\ &=n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right) \end{aligned} \]

這就是歐拉函數的數學表示啦

容斥原理一般化

容斥原理常用於集合的計數問題，而對於兩個集合的函數 \(f(S),g(S)\)，若

\[ f(S)=\sum_{T\subseteq S}g(T) \]

那麼就有

\[ g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T) \]

證明

接下來我們簡單證明一下。我們從等式的右邊開始推：

\[ \begin{aligned} &\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)\\ =&\sum_{T\subseteq S}(-1)^{|S|-|T|}\sum_{Q\subseteq T}g(Q)\\ =&\sum_{Q}g(Q)\sum_{Q\subseteq T\subseteq S}(-1)^{|S|-|T|}\\ \end{aligned} \]

我們發現後半部分的求和與 \(Q\) 無關，因此把後半部分的 \(Q\) 剔除：

\[ =\sum_{Q}g(Q)\sum_{T\subseteq (S\setminus Q)}(-1)^{|S\setminus Q|-|T|} \]

記關於集合 \(P\) 的函數 \(F(P)=\sum_{T\subseteq P}(-1)^{|P|-|T|}\)，並化簡這個函數：

\[ \begin{aligned} F(P)&=\sum_{T\subseteq P}(-1)^{|P|-|T|}\\ &=\sum_{i=0}^{|P|}\dbinom{|P|}{i}(-1)^{|P|-i}=\sum_{i=0}^{|P|}\dbinom{|P|}{i}1^i(-1)^{|P|-i}\\ &=(1-1)^{|P|}=0^{|P|} \end{aligned} \]

因此原來的式子的值是

\[ \sum_{Q}g(Q)\sum_{T\subseteq (S\setminus Q)}(-1)^{|S\setminus Q|-|T|}=\sum_{Q}g(Q)F(S\setminus Q)=\sum_{Q}g(Q)\cdot 0^{|S\setminus Q|} \]

分析發現，僅當 \(|S\setminus Q|=0\) 時有 \(0^0=1\)，這時 \(Q=S\)，對答案的貢獻就是 \(g(S)\)，其他時侯 \(0^{|S\setminus Q|}=0\)，則對答案無貢獻。於是得到

\[ \sum_{Q}g(Q)\cdot 0^{|S\setminus Q|}=g(S) \]

綜上所述，得證。

推論

該形式還有這樣一個推論。在全集 \(U\) 下，對於函數 \(f(S),g(S)\)，如果

\[ f(S)=\sum_{S\subseteq T}g(T) \]

那麼

\[ g(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}f(T) \]

這個推論其實就是補集形式，證法類似。

DAG 計數

對 \(n\) 個點帶標號的有向無環圖進行計數，對 \(10^9+7\) 取模。\(n\leq 5\times 10^3\)。

直接 DP

考慮 DP，定義 \(f[i,j]\) 表示 \(i\) 個點的 DAG，有 \(j\) 點個入度為 \(0\) 的圖的個數。假設去掉這 \(j\) 個點後，有 \(k\) 個點入度為 \(0\)，那麼在去掉前這 \(k\) 個點至少與這 \(j\) 個點中的某幾個有連邊，即 \(2^j-1\) 種情況；而這 \(j\) 個點除了與 \(k\) 個點連邊，還可以與剩下的點任意連邊，有 \(2^{i-j-k}\) 種情況。因此方程如下：

\[ f[i,j]=\binom{i}{j}\sum_{k=1}^{i-j}(2^j-1)^k2^{(i-j-k)j}f[i-j,k] \]

計算上式的複雜度是 \(O(n^3)\) 的。

放寬限制

上述 DP 的定義是恰好 \(j\) 個點入度為 \(0\), 太過於嚴格，可以放寬為至少 \(j\) 個點入度為 \(0\)。直接定義 \(f[i]\) 表示 \(i\) 個點的 DAG 個數。可以直接容斥。考慮選出的 \(j\) 個點，這 \(j\) 個點可以和剩下的 \(i-j\) 個點有任意的連邊，即 \(\left(2^{i-j}\right)^j=2^{(i-j)j}\) 種情況：

\[ f[i]=\sum_{j=1}^i(-1)^{j-1}\binom{i}{j}2^{(i-j)j}f[i-j] \]

計算上式的複雜度是 \(O(n^2)\) 的。

Min-max 容斥

對於滿足全序關係並且其中元素滿足可加減性的序列 \(\{x_i\}\)，設其長度為 \(n\)，並設 \(S=\{1,2,3,\cdots,n\}\)，則有：

\[ \max_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\min_{j\in T}{x_j}} \]

\[ \min_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\max_{j\in T}{x_j}} \]

證明： 考慮做一個到一般容斥原理的映射。對於 \(x\in S\)，假設 \(x\) 是第 \(k\) 大的元素。那麼我們定義一個映射 \(f:x\mapsto \{1,2,\cdots,k\}\)。顯然這是一個雙射。

那麼容易發現，對於 \(x,y\in S\)，\(f(\min(x,y))=f(x)\cap f(y)\)，\(f(\max(x,y))=f(x)\cup f(y)\)。因此我們得到：

\[ \begin{aligned} \left|f\left(\max_{i\in S}{x_i}\right)\right| &= \left| \bigcup_{i\in S} f(x_i) \right|\\ &= \sum_{T\subseteq S}(-1)^{|T|-1} \left|\bigcap_{j\in T}f(x_j)\right|\\ &= \sum_{T\subseteq S}(-1)^{|T|-1} \left|f\left(\min_{j\in T}{x_j}\right)\right|\\ \end{aligned} \]

然後再把 \(\left|f\left(\max_{i\in S}{x_i}\right)\right|\) 映射回 \(\max_{i\in S}{x_i}\)，而 \(\min\) 是類似的。

證畢

但是你可能覺得這個式子非常蠢，最大值明明可以直接求。之所以 min-max 容斥這麼重要，是因為它在期望上也是成立的，即：

\[ E\left(\max_{i\in S}{x_i}\right)=\sum_{T\subseteq S}{(-1)^{|T|-1}E\left(\min_{j\in T}{x_j} \right)} \]

\[ E\left(\min_{i\in S}{x_i}\right)=\sum_{T\subseteq S}{(-1)^{|T|-1}E\left(\max_{j\in T}{x_j} \right)} \]

證明： 我們考慮計算期望的一種方法：

\[ E\left(\max_{i\in S}{x_i}\right)=\sum_{y}{P(y=x)\max_{j\in S}{y_j}} \]

其中 \(y\) 是一個長度為 \(n\) 的序列。

我們對後面的 \(\max\) 使用之前的式子：

\[ \begin{aligned}E\left(\max_{i\in S}{x_i}\right)&=\sum_{y}{P(y=x)\max_{j\in S}{y_j}}\\ &=\sum_{y}{P(y=x)\sum_{T\subseteq S}{(-1)^{|T|-1}\min_{j\in T}{y_j}}} \end{aligned} \]

調換求和順序：

\[ \begin{aligned}E\left(\max_{i\in S}{x_i}\right) &=\sum_{y}{P(y=x)\sum_{T\subseteq S}{(-1)^{|T|-1}\min_{j\in T}{y_j}}}\\ &=\sum_{T\subseteq S}{(-1)^{|T|-1}\sum_y{P(y=x)\min_{j\in T}{y_j}}}\\ &=\sum_{T\subseteq S}{(-1)^{|T|-1}E\left(\min_{j\in T}{y_j}\right)} \end{aligned} \]

\(\min\) 是類似的。

證畢

還有更強的：

\[ \underset{i\in S}{\operatorname{kthmax}{x_i}}=\sum_{T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}\min_{j\in T}{x_j}} \]

\[ \underset{i\in S}{\operatorname{kthmin}{x_i}}=\sum_{T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}\max_{j\in T}{x_j}} \]

\[ E\left(\underset{i\in S}{\operatorname{kthmax}{x_i}}\right)=\sum_{T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}E\left(\min_{j\in T}{x_j}\right)} \]

\[ E\left(\underset{i\in S}{\operatorname{kthmin}{x_i}}\right)=\sum_{T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}E\left(\max_{j\in T}{x_j}\right)} \]

規定若 \(n< m\)，則 \(\dbinom nm=0\)。

證明： 不妨設 \(\forall 1\le i<n,x_i\le x_{i+1}\)。則有：

\[ \begin{aligned} \sum_{T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}\min_{j\in T}{x_j}} &=\sum_{i\in S}{x_i\sum_{T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}\left[x_i=\min_{j\in T}{x_j} \right]}}\\ &=\sum_{i\in S}{x_i\sum_{j=k}^n{\dbinom {n-i}{j-1}\dbinom {j-1}{k-1}(-1)^{j-k}}} \end{aligned} \]

又因為有組合恆等式：\(\dbinom ab\dbinom bc=\dbinom ac\dbinom {a-c}{b-c}\)，所以有：

\[ \begin{aligned} \sum_{T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}\min_{j\in T}{x_j}} &=\sum_{i\in S}{x_i\sum_{j=k}^n{\dbinom {n-i}{j-1}\dbinom {j-1}{k-1}(-1)^{j-k}}}\\ &=\sum_{i\in S}{x_i\sum_{j=k}^n{\dbinom {n-i}{k-1}\dbinom {n-i-k+1}{j-k}(-1)^{j-k}}}\\ &=\sum_{i\in S}{\dbinom {n-i}{k-1}x_i\sum_{j=k}^n{\dbinom {n-i-k+1}{j-k}(-1)^{j-k}}}\\ &=\sum_{i\in S}{\dbinom {n-i}{k-1}x_i\sum_{j=0}^{n-i-k+1}{\dbinom {n-i-k+1}j(-1)^{j}}} \end{aligned} \]

當 \(i=n-k+1\) 時：

\[ \dbinom {n-i}{k-1}\sum_{j=0}^{n-i-k+1}{\dbinom {n-i-k+1}j(-1)^{j}}=1 \]

否則：

\[ \dbinom {n-i}{k-1}\sum_{j=0}^{n-i-k+1}{\dbinom {n-i-k+1}j(-1)^{j}}=0 \]

所以：

\[ \sum_{i\in S}{\dbinom {n-i}{k-1}x_i\sum_{j=0}^{n-i-k+1}{\dbinom {n-i-k+1}j(-1)^{j}}}=\underset{i\in S}{\operatorname{kthmax}}{x_i} \]

剩下三個是類似的。

證畢

根據 min-max 容斥，我們還可以得到下面的式子：

\[ \underset{i\in S}{\operatorname{lcm}}{x_i}=\prod_{T\subseteq S}{\left(\gcd_{j\in T}{x_j} \right)^{(-1)^{|T|-1}}} \]

因為 \(\operatorname{lcm},\gcd,a^{1},a^{-1}\) 分別相當於 \(\max,\min,+,-\)，就是説相當於對於指數做了一個 min-max 容斥，自然就是對的了

PKUWC2018 隨機遊走

給定一棵 \(n\) 個點的樹，你從 \(x\) 出發，每次等概率隨機選擇一條與所在點相鄰的邊走過去。

有 \(Q\) 次詢問。每次詢問給出一個集合 \(S\)，求如果從 \(x\) 出發一直隨機遊走，直到點集 \(S\) 中的點都至少經過一次的話，期望遊走幾步。

特別地，點 \(x\)（即起點）視為一開始就被經過了一次。

對 \(998244353\) 取模。

\(1\le n\le 18,1\le Q\le 5000,1\le |S|\le n\)。

期望遊走的步數也就是遊走的時間。那麼設隨機變量 \(x_i\) 表示第一次走到結點 \(i\) 的時間。那麼我們要求的就是

\[ E\left(\max_{i\in S}x_i\right) \]

使用 min-max 容斥可以得到

\[ E\left(\max_{i\in S}x_i\right) =E\left(\sum_{T\subseteq S}(-1)^{|T|-1}\min_{i\in T}x_i\right) =\sum_{T\subseteq S}(-1)^{|T|-1}E\left(\min_{i\in T}x_i\right) \]

對於一個集合 \(T\in[n]\)，考慮求出 \(F(T)=E(\min_{i\in T}x_i)\)。

考慮 \(E(\min_{i\in T}x_i)\) 的含義，是第一次走到 \(T\) 中某一個點的期望時間。不妨設 \(f(i)\) 表示從結點 \(i\) 出發，第一次走到 \(T\) 中某個結點的期望時間。

對於 \(i\in T\)，有 \(f(i)=0\)。
對於 \(i\notin T\)，有 \(f(i)=1+\frac{1}{\text{deg}(i)}\sum_{(i,j)\in E}f(j)\)。

如果直接高斯消元，複雜度 \(O(n^3)\)。那麼我們對每個 \(T\) 都計算 \(F(T)\) 的總複雜度就是 \(O(2^nn^3)\)，不能接受。我們使用樹上消元的技巧。

不妨設根結點是 \(1\)，結點 \(u\) 的父親是 \(p_u\)。對於葉子結點 \(i\)，\(f(i)\) 只會和 \(i\) 的父親有關（也可能 \(f(i)=0\)，那樣更好）。因此我們可以把 \(f(i)\) 表示成 \(f(i)=A_i+B_if(p_i)\) 的形式，其中 \(A_i,B_i\) 可以快速計算。

對於非葉結點 \(i\)，考慮它的兒子序列 \(j_1,\cdots,j_k\)。由於 \(f(j_e)=A_{j_e}+B_{j_e}f(i)\)。因此可以得到

\[ f(i)=1+\frac{1}{\deg(i)}\sum_{e=1}^k\left(A_{j_e}+B_{j_e}f(i)\right)+\frac{f(p_i)}{\deg(i)} \]

那麼變換一下可以得到

\[ f(i)=\frac{\deg(i)+\sum_{e=1}^kA_{j_e}}{\deg(i)-\sum_{e=1}^kB_{j_e}}+ \frac{f(p_i)}{\deg(i)-\sum_{e=1}^kB_{j_e}} \]

於是我們把 \(f(i)\) 也寫成了 \(A_i+B_if(p_i)\) 的形式。這樣可以一直倒推到根結點。而根結點沒有父親。也就是説

\[ f(1)=\frac{\deg(1)+\sum_{e=1}^kA_{j_e}}{\deg(1)-\sum_{e=1}^kB_{j_e}} \]

解一下這個方程我們就得到了 \(f(1)\)，再從上往下推一次就得到了每個點的 \(f(i)\)。那麼 \(F(T)=f(x)\)。時間複雜度 \(O(n)\)。

這樣，我們可以對於每一個 \(T\) 計算出 \(F(T)\)，時間複雜度 \(O(2^nn)\)。

回到容斥的部分，我們知道 \(E(\max_{i\in S}x_i)=\sum_{T\subseteq S}(-1)^{|T|-1}F(T)\)。

不妨設 \(F'(T)=(-1)^{|T|-1}F(T)\)，那麼進一步得到 \(E(\max_{i\in S}x_i)=\sum_{T\subseteq S}F'(T)\)。因此可以使用 FMT（也叫子集前綴和，或者 FWT 或變換）在 \(O(2^nn)\) 的時間內對每個 \(S\) 計算出 \(E(\max_{i\in S}x_i)\)，這樣就可以 \(O(1)\) 回答詢問了。

習題

參考文獻

王迪《容斥原理》，2013 年信息學奧林匹克中國國家隊候選隊員論文集

Cyhlnj《有標號的 DAG 計數系列問題》

Wikipedia - 全序關係

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用