反演与容斥

反演

假设有两个函数$f$和$g$满足:$f ( n ) = \sum_{ k } a_{ n , k } g ( k )$,已知f求g的过程称为反演.

一般情况下,求反演只能高斯消元,但是有一些形式的反演有巧妙解法.

子集反演

一般形式:

$$\begin{aligned} f ( S ) & = \sum_{ T \subseteq S } g ( T ) \Leftrightarrow g ( S ) = \sum_{ T \subseteq S } ( - 1 )^{ | S | - | T | } f ( T ) \\ f ( S ) & = \sum_{ S \subseteq T \subseteq U } g ( T ) \Leftrightarrow g ( S ) = \sum_{ S \subseteq T \subseteq U } ( - 1 )^{ | T | - | S | } f ( T ) \end{aligned}$$

证明:

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

不难发现,这个子集反演也就相当于在做高维前后缀和.

Example1(2019zrpzt七连day1D)

根据子集反演,设$cnt_S$为集合为$S$的数量,然后设$f_S = \sum_{ S ‘ \subseteq S } cnt_{ S ‘ }$,有:$ans = \sum_{ S } 2^{ f_S } ( - 1 )^{ n - | S | }$.

做一遍高维前缀和就好,复杂度$O ( n 2^n )$,应该也可以用分治FMT无脑做到$O ( n^2 2^n )$.

Example2(有标号DAG计数)

设$f_{ i , j }$表示$i$个点,其中有$j$个点的入度数为$0$的方案数.(等一下,为撒子想到要记度数为$0$的点咧?因为你要一层一层转移,而在DAG中一层一层的就是零度点.而且说到底,你注意到有编号这个事实其实是很烦的,因为考虑如果一个一个点放上去,就有可能出现放的地方是等价的.而这么一层一层是绝对不会出现等价点的问题的.再说的仔细一点,如果我们把位置空着,然后选出一些放上来,是会出现等价点的问题的.但如果我们先选出来,然后再把边连上就不会.于是我们必须要枚举一些点然后再连到上面去)

这样我们每次枚举删去这$j$个点后,还剩下$k$个零度点.于是自然有:

$$f_{ i , j } = \binom{ i }{ j } \sum_{ k = 1 }^{ i - j } ( 2^j - 1 )^k 2^{ j ( i - j - k ) } f_{ i - j , k }$$

等一下咧,这复杂度$O ( n^3 )$了,这咋办啊?

好像转移优化不太了,因为$k$很难省去(在指数上).但我们注意到我们定义的时候说:$0$度点的数量恰好为$k$,这个条件好像太强了果然OI就是发现限制太强了就弱一点,发现太弱了就强一点,所以我们想办法把它放弱一点.

一个经典的方法是:我们把定义改为至少$k$个零度点.但是这样转移好像还是不太行:零度点的情况太多了.那我们不妨考虑容斥,因为推导容斥的过程中,永远不害怕情况太多:我们直接考虑所有情况的集合.当然能不能推到最后是另一回事.

我们设$f ( n , S )$表示$n$个点,其中只有$S$中的点的入度为$0$;类似定义$g ( n , S )$表示$n$个点,至少$S$中的点的入度为$0$.显然我们所求也就是$g ( n , \emptyset )$,注意到:

$$\begin{aligned} g ( n , S ) & = 2^{ | S | ( n - | S | ) } g ( n - | S | , \emptyset ) \\ g ( n , S ) & = \sum_{ S \subseteq T } f ( n , T ) \end{aligned}$$

对第二个式子用子集反演,有:

$$f ( n , S ) = \sum_{ S \subseteq T } ( - 1 )^{ | T | - | S | } g ( n , T )$$

接下来使用反复带入大法:

$$\begin{aligned} g ( n , \emptyset ) & = \sum_{ \emptyset \ne T } f ( n , T ) \\ & = \sum_{ T \subseteq S } ( - 1 )^{ | S | - | T | } g ( n , S ) \\ & = \sum_{ T \subseteq S } ( - 1 )^{ | S | - | T | } 2^{ | S | ( n - | S | ) } g ( n - | S | , \emptyset ) \\ & = \sum_{ m = 1 }^n \sum_{ | T | = m } \sum_{ T \subseteq S } ( - 1 )^{ | S | - | T | } 2^{ | S | ( n - | S | ) } g ( n - | S | , \emptyset ) \\ & = \sum_{ m = 1 }^n \binom{ n }{ m } \sum_{ k = m }^n \binom{ n - m }{ k - m } ( - 1 )^{ k - m } 2^{ k ( n - k ) } g ( n - k , \emptyset ) \\ \end{aligned}$$

可以发现:我们在推式子的过程中,将和集合本身有关的性质转化为了只和集合大小有关的式子,于是就简化了大量运算.

接下来我们继续化简:

$$\begin{aligned} & \sum_{ m = 1 }^n \binom{ n }{ m } \sum_{ k = m }^n \binom{ n - m }{ k - m } ( - 1 )^{ k - m } 2^{ k ( n - k ) } g ( n - k , \emptyset ) \\ = & \sum_{ k = 1 }^n \sum_{ m = 1 }^k \binom{ n }{ m } \binom{ n - m }{ k - m } ( - 1 )^{ k - m } 2^{ k ( n - k ) } g ( n - k , \emptyset ) \\ = & \sum_{ k = 1 }^n \binom{ n }{ k } 2^{ k ( n - k ) } g ( n - k , \emptyset ) \sum_{ m = 1 }^k \binom{ k }{ m } ( - 1 )^{ k - m } \\ = & \sum_{ k = 1 }^n \binom{ n }{ k } 2^{ k ( n - k ) } g ( n - k , \emptyset ) ( ( 1 - 1 )^k - ( - 1 )^k ) \\ = & \sum_{ k = 1 }^n \binom{ n }{ k } 2^{ k ( n - k ) } g ( n - k , \emptyset ) ( - 1 )^{ k - 1 } \\ \end{aligned}$$

注意到复杂度已经降到$O ( n^2 )$了.

上面是从集合的角度一步步分析得到的.但如果你直接从容斥的角度考虑,忽略掉那个$( - 1 )^{ k - 1 }$,把它当成一个可以数学归纳出来的容斥系数,那么这个式子会得到一个很简单的理解方式:

$$\begin{aligned} f_n & = \sum_{ k = 1 }^n \binom{ n }{ k } ( - 1 )^{ k - 1 } 2^{ k ( n - k ) } f_{ n - k } \\ \end{aligned}$$

也就是直接设,然后钦定其有至少$j$个,然后配容斥系数.

二项式反演

一般形式:

$$\begin{aligned} f ( n ) & = \sum_{ k = 0 }^n C_n^k g ( k ) \Leftrightarrow g ( n ) = \sum_{ k = 0 }^n ( - 1 )^{ n - k } C_n^k f ( k ) \\ f ( n ) & = \sum_{ k = 0 }^n ( - 1 )^k \binom{ n }{ k } g ( k ) \Leftrightarrow g ( n ) = \sum_{ k = 0 }^n ( - 1 )^k \binom{ n }{ k } f ( k ) \\ f ( n ) & = \sum_{ k = n }^N C_k^n g ( k ) \Leftrightarrow g ( n ) = \sum_{ k = n }^N ( - 1 )^{ k - n } C_k^n f ( k ) \\ f ( n ) & = \sum_{ k = n }^N ( - 1 )^k \binom{ k }{ n } g ( k ) \Leftrightarrow g ( n ) = \sum_{ k = n }^N ( - 1 )^k \binom{ k }{ n } f ( k ) \\ \end{aligned}$$

显然以$( - 1 )^n g ( n )$代替$g ( n )$即可从第一个式子推导第二个式子,下面证明第一个式子:

$$\begin{aligned} g ( n ) & = \sum_{ k = 0 }^n ( - 1 )^{ n - k } C_n^k f ( k ) \\ & = \sum_{ m = 0 }^n \sum_{ k = 0 }^{ n - m } ( - 1 )^k C_{ n - m }^k C_n^m g ( m ) \\ & = \sum_{ k = 0 }^n ( - 1 )^k C_n^k \sum_{ m = 0 }^{ n - k } C_{ n - k }^m g ( m ) \\ & = \sum_{ k = 0 }^n ( - 1 )^k C_n^k f ( n - k ) \\ & = \sum_{ k = 0 }^n ( - 1 )^{ n - k } C_n^k f ( k ) \\ \end{aligned}$$

Example1(错排问题)

$n$个有编号的人站成一排,求他们都没有站到自己编号对应位置的方案数.

设$f ( n )$为$n$个人随便站的方案数,$g ( n )$为$n$个人都站错的方案数.

如果知道$g$的表达式,我们可以通过枚举有多少人站错位置来得到$f$,即:$f ( n ) = \sum_{ k = 0 }^n C_n^k g ( k )$.

显然就是一个二项式反演,$g ( n ) = \sum_{ k = 0 }^n ( - 1 )^{ n - k } C_n^k f ( k ) = \sum_{ k = 0 }^n ( - 1 )^{ n - k } C_n^k k !$.

值得一提的是,我们再观察一下最后得到的错排公式并进行一定的化简,可以得到:$g ( n ) = n ! \sum_{ 0 \leq k \leq n } \cfrac{ ( - 1 )^k }{ k ! } \\$.

不难发现$n !$的后面形如$e^{ - 1 }$的泰勒展开,我们考虑直接将泰勒展开的公式带入,可以得到:

$$\begin{aligned} g ( n ) & = \cfrac{ n ! }{ e } - n ! \sum_{ k > n } \cfrac{ ( - 1 )^k }{ k ! } \\ & = \cfrac{ n ! }{ e } - \cfrac{ ( - 1 )^{ n + 1 } }{ n + 1 } \sum_{ 0 \leq k } ( - 1 )^k \cfrac{ ( n + 1 ) ! }{ ( k + n + 1 ) ! } \end{aligned}$$

用一些我不会的方法分析误差,会发现后面的项所能带来的误差很小,于是有$g ( n ) = \lfloor \cfrac{ n ! }{ e } + \cfrac{ 1 }{ 2 } \rfloor + [ n = 0 ]$.

另外,观察$g$关于$f$的表达式,不难求出$g$的递推式:$g ( n ) = ng ( n - 1 ) + ( - 1 )^n$.

下面证明$g_n = ( n - 1 ) ( g_{ n - 1 } + g_{ n - 2 } )$,事实上,右边等于:

$$\begin{aligned} & ( n - 1 ) ( g_{ n - 1 } + g_{ n - 2 } ) \\ = & ( - 1 )^{ n - 1 } ( n - 1 ) + ( n - 1 ) \sum_{ k = 0 }^{ n - 2 } ( ( n - 1 ) ! \frac{ ( - 1 )^k }{ k ! } + ( n - 2 ) ! \frac{ ( - 1 )^k }{ k ! } ) \\ = & n ! \sum_{ k = 0 }^{ n - 2 } \frac{ ( - 1 )^k }{ k ! } - ( n - 1 ) ( - 1 )^n \\ \end{aligned}$$

Example2(CF1750G)

如果没有字典序限制就是经典的二项式反演:考虑能被分为$k$段,说明有$n - k$个位置和前一个位置是大一的关系.我们钦定这些位置即可.

而有字典序限制也很经典,枚举LCP,枚举下一个位置,这个时候值域被分为若干个区间,假设剩了$x$个数字,$y$个区间,那么钦定$j$对的方案是$\binom{ x - y }{ j } ( x - j ) !$.然后要乘上前面已经有了的,也就是乘上形如$( 1 + z )^k$.这样复杂度$O ( n^4 )$.

这种问题通常LCP后的下一个位置都可以规避,这里你发现不同的取值只会让后面的$x , y , k$有$O ( 1 )$种不同的取值,因此不用枚举.这样就是$O ( n^3 )$.但是那个多项式乘法也可以规避,考虑最后的答案形如$\sum ( 1 + z )^k P_k ( x )$,我们考虑写成$P_{ n - 1 } ( z ) + = ( 1 + z ) P_n ( z )$,然后不断这么做,就只需要$O ( n^2 )$.

Example3(CF1228E)

不妨设至多有$i$行$j$列最小值为$1$的答案是$f_{ i , j }$,恰好有$i$行$j$列最小值为$1$的答案是$g_{ i , j }$,注意到:

$$f_{ n , m } = \sum_{ i = 0 }^n \binom{ n }{ i } \sum_{ j = 0 }^m \binom{ m }{ j } g_{ i , j }$$

令$h_{ n , m } = \sum_{ j = 0 }^m \binom{ m }{ j } g_{ n , j } \\$,则$f_{ n , m } = \sum_{ i = 0 }^n \binom{ n }{ i } h_{ i , m } \\$,而$f_{ n , m } = k^{ nm } ( k - 1 )^{ NM - nm }$.做两次二项式反演得到$g$.

写到这里发现一个问题(其实是我发现问题后把上面原本写错的给改了),为啥$f_{ n , m } \ne \binom{ N }{ n } \binom{ M }{ m } k^{ nm } ( k - 1 )^{ NM - nm }$呢?我们写成子集反演形式看看:

$$\begin{aligned} f_{ S , T } & = \sum_{ s \subseteq S } \sum_{ t \subseteq T } g_{ s , t } \\ f_{ S , T } & = \sum_{ s \subseteq S } h_{ s , T } \\ h_{ S , T } & = \sum_{ t \subseteq T } g_{ S , t } \\ \end{aligned}$$

做子集反演:

$$\begin{aligned} f_{ S , T } & = k^{ | S | \times | T | } ( k - 1 )^{ NM - | S | | T | } \\ h_{ s , T } & = \sum_{ S \subseteq s } ( - 1 )^{ | s | - | S | } f_{ S , T } \\ g_{ s , t } & = \sum_{ T \subseteq t } ( - 1 )^{ | t | - | T | } h_{ s , T } \end{aligned}$$

把集合改成集合大小就可以发现问题所在:

换句话说,$g_{ n , m }$本身就包含了所有$| S | = n , | T | = m$的情况的和,并且在组合数$\binom{ m }{ j }$那里就找到了唯一确定的$f_{ s , t }$,因此$f_{ n , m }$是唯一确定的.这意味着这里$f$的$n , m$并非集合之和,而是已经确定的集合的大小.

啥?这和我平常接触的二项式反演不一样啊?不说别的,第四题(BZOJ2839)的式子是这样的:

$$\begin{aligned} f_i & = 2^{ 2^{ n - i } } \binom{ n }{ i } \\ f_k & = \sum_{ i = k }^n \binom{ i }{ k } g_i \\ g_k & = \sum_{ i = k }^n ( - 1 )^{ i - k } \binom{ i }{ k } f_i \end{aligned}$$

冷静一下,二项式反演的公式肯定没错,那也就一定是下面这几句出现了问题:

$$f_{ n , m } = \sum_{ i = 0 }^n \binom{ n }{ i } \sum_{ j = 0 }^m \binom{ m }{ j } g_{ i , j }$$

这个问题其实非常显然,我们的$g_{ i , j }$定义为所有$| S | = i , | T | = j$的答案之和.$f$也是这么定义的,那这个式子就是错的,应该写成:

$$f_{ n , m } = \sum_{ i = 0 }^n \binom{ N - i }{ n - i } \sum_{ j = 0 }^m \binom{ M - j }{ m - j } g_{ i , j }$$

这样才是在不确定的那些行列中选择组合数,而不是在确定的那些行列中选.

但这样又有一个问题,就是这个题的特殊性,这个题要求$g_{ N , M }$,那此时$g$怎么定义不应该是一样的吗?

当然不一样,二项式反演讲究统一性,所有的定义必须遵循一个统一的原则,不然如果什么样子的函数都能反演,那一般的反演就不是一个需要解方程才能完成的东西了.

回到第四题,再看一遍这个式子:

$$\begin{aligned} f_k & = \sum_{ i = k }^n \binom{ i }{ k } g_i \\ \end{aligned}$$

这个定义式就非常良性,$g$是已知的集合,$f$是未知的集合.我们乘上组合数就可以得到对于$f$来说已知的集合.因此这个就非常正确.

回到这个题上,为什么我们最后把$f$的定义改成$f_{ n , m } = k^{ nm } ( k - 1 )^{ NM - nm }$就对了呢?

再看看这个式子:

$$f_{ n , m } = \sum_{ i = 0 }^n \binom{ n }{ i } \sum_{ j = 0 }^m \binom{ m }{ j } g_{ i , j }$$

这个式子的右边在干这样一件事:那就是在已知$n$行$m$列的集合的前提下,从中选出$i$行$j$列并求$g$.那么你从哪知道的$n$行$m$列呢?你得组合数啊!

所以,实际上的$f$是这样的:

$$\begin{aligned} f_{ n , m } & = \binom{ N }{ n } \binom{ M }{ m } \sum_{ i = 0 }^n \binom{ n }{ i } \sum_{ j = 0 }^m \binom{ m }{ j } g_{ i , j } \\ f_{ n , m } & = \binom{ N }{ n } \binom{ M }{ m } k^{ nm } ( k - 1 )^{ NM - nm } \end{aligned}$$

好麻烦啊,能不能避免这种需要进一步思考集合意义的问题呢?

考虑二项式反演的第二个形式:

$$\begin{aligned} f ( n ) & = \sum_{ k = n }^N C_n^k g ( k ) \Leftrightarrow g ( n ) = \sum_{ k = n }^N ( - 1 )^{ k - n } C_n^k f ( k ) \\ \end{aligned}$$

不难发现这个式子无论怎么写,前后都一定是从已知集合中选东西.绝对不会出现上面的问题.

因此,我们重新写一下这个题的相关式子,考虑直接正难则反,设$f ‘_{ i , j }$为至少有$i$行$j$列不满足条件的方案数,自然有$f ‘_{ i , j } = f_{ N - i , M - j }$.你发现此时一定有:

$$f '_{ n , m } = \sum_{ i = n }^N \binom{ i }{ n } \sum_{ j = m }^M \binom{ j }{ m } g '_{ i , j }$$

最后答案就是$g ‘_{ 0 , 0 }$.

斯特林反演

一般形式:

$$\begin{aligned} f ( n ) & = \sum_{ k = 0 }^n \left \{ \begin{array} { c } n \\ k \end{array} \right \} g ( k ) \Leftrightarrow g ( n ) = \sum_{ k = 0 }^n \left [ \begin{array} { c } n \\ k \end{array} \right ] ( - 1 )^{ n - k } f ( k ) \\ f ( n ) & = \sum_{ k = 0 }^n \left [ \begin{array} { c } n \\ k \end{array} \right ] g ( k ) \Leftrightarrow g ( n ) = \sum_{ k = 0 }^n \left \{ \begin{array} { c } n \\ k \end{array} \right \} ( - 1 )^{ n - k } f ( k ) \\ f ( m ) & = \sum_{ n = m }^M ( - 1 )^{ m - n } \left [ \begin{array} { c } n \\ m \end{array} \right ] g ( n ) \Leftrightarrow g ( m ) = \sum_{ k = 0 }^M \left \{ \begin{array} { c } k \\ m \end{array} \right \} f ( k ) \\ f ( m ) & = \sum_{ n = m }^M ( - 1 )^{ m - n } \left \{ \begin{array} { c } n \\ m \end{array} \right \} g ( n ) \Leftrightarrow g ( m ) = \sum_{ k = 0 }^M \left [ \begin{array} { c } k \\ m \end{array} \right ] f ( k ) \\ \end{aligned}$$

考虑第一类斯特林数和第二类斯特林数的对称性,只需证明第一个和第三个式子即可.

反转公式:

$$\begin{aligned} \sum_{ k = 0 }^n \left [ \begin{array} { c } n \\ k \end{array} \right ] \left \{ \begin{array} { c } k \\ m \end{array} \right \} ( - 1 )^{ n - k } & = \sum_{ k = 0 }^n \left \{ \begin{array} { c } n \\ k \end{array} \right \} \left [ \begin{array} { c } k \\ m \end{array} \right ] ( - 1 )^{ n - k } = [ m = n ] \\ \end{aligned}$$

第一个式子的证明:

$$\begin{aligned} g ( n ) & = \sum_{ m = 0 }^n [ m = n ] g ( m ) \\ & = \sum_{ m = 0 }^n \sum_{ k = 0 }^n \left [ \begin{array} { c } n \\ k \end{array} \right ] \left \{ \begin{array} { c } k \\ m \end{array} \right \} ( - 1 )^{ n - k } g ( m ) \\ & = \sum_{ k = 0 }^n \left [ \begin{array} { c } n \\ k \end{array} \right ] ( - 1 )^{ n - k } \sum_{ m = 0 }^k \left \{ \begin{array} { c } k \\ m \end{array} \right \} g ( m ) = \sum_{ k = 0 }^n \left [ \begin{array} { c } n \\ k \end{array} \right ] ( - 1 )^{ n - k } f ( k ) \\ \end{aligned}$$

第三个式子的证明:

$$\begin{aligned} g ( m ) & = \sum_{ n = m }^M [ n = m ] g ( n ) \\ & = \sum_{ n = m }^M \sum_{ k = 0 }^M \left [ \begin{array} { c } n \\ k \end{array} \right ] \left \{ \begin{array} { c } k \\ m \end{array} \right \} ( - 1 )^{ n - k } g ( n ) \\ & = \sum_{ k = 0 }^M \left \{ \begin{array} { c } k \\ m \end{array} \right \} f ( k ) \\ \end{aligned}$$

莫比乌斯反演

一般形式:

$$\begin{aligned} f ( n ) & = \sum_{ d | n } g ( d ) \Leftrightarrow g ( n ) = \sum_{ d | n } \mu ( \frac{ n }{ d } ) f ( d ) \\ f ( n ) & = \sum_{ n | d } g ( d ) \Leftrightarrow g ( n ) = \sum_{ n | d } \mu ( \frac{ d }{ n } ) f ( d ) \\ f ( x ) & = \sum_{ 1 \leq d } g ( d ) \Leftrightarrow g ( x ) = \sum_{ 1 \leq d } f ( \cfrac{ x }{ d } ) \mu ( d ) \end{aligned}$$

第一个式子的证明:

$$\begin{aligned} g ( n ) & = \sum_{ m | n } [ \frac{ n }{ m } = 1 ] g ( m ) \\ & = \sum_{ m | n } \sum_{ d | \frac{ n }{ m } } \mu ( d ) g ( m ) \\ \end{aligned}$$

注意到$[ d | \frac{ n }{ m } ] = [ md | n ] = [ m | \frac{ n }{ d } ] \\$.

$$\begin{aligned} g ( n ) & = \sum_{ d | n } \mu ( d ) \sum_{ m | \frac{ n }{ d } } g ( m ) \\ & = \sum_{ d | n } \mu ( d ) f ( \frac{ n }{ d } ) \\ & = \sum_{ d | n } \mu ( \frac{ n }{ d } ) f ( d ) \\ \end{aligned}$$

第二个式子的证明:

$$\begin{aligned} g ( n ) & = \sum_{ n | d } [ \frac{ d }{ n } = 1 ] g ( d ) \\ & = \sum_{ n | d } \sum_{ c | \frac{ d }{ n } } \mu ( c ) g ( d ) \\ & = \sum_{ c | d } \sum_{ nc | d } \mu ( c ) g ( d ) \\ & = \sum_{ c } \mu ( c ) f ( nc ) \\ & = \sum_{ n | d } \mu ( \frac{ d }{ n } ) f ( d ) \\ \end{aligned}$$

第三个式子的证明:

$$\begin{aligned} \sum_{ 1 \leq d } g ( \cfrac{ x }{ d } ) \mu ( d ) & = \sum_{ d \geq 1 } \mu ( d ) \sum_{ k \geq 1 } f ( \cfrac{ x }{ kd } ) \\ & = \sum_{ m \geq 1 } f ( \cfrac{ x }{ m } ) \sum_{ d , k \geq 1 } [ m = dk ] \mu ( d ) \\ & = \sum_{ m \geq 1 } f ( \cfrac{ x }{ m } ) \sum_{ d | m } \mu ( d ) \\ & = f ( x ) \end{aligned}$$

Example1

求长度为$n$且仅包含小写英文字母且循环节长度恰为$n$的字符串个数.

不妨设$f ( n )$表示长度为$n$的字符串个数,$g ( n )$表示长度为$n$且循环节长度恰为$n$的字符串个数.

有$f ( n ) = \sum_{ d | n } g ( d )$,根据莫比乌斯反演,$g ( n ) = \sum_{ d | n } \mu ( \cfrac{ n }{ d } ) f ( d )$.

Example2

求$\sum_{ i = 1 }^{ n } \sum_{ j = 1 }^m gcd ( i , j ) \\$.

我们通过这个题来讲一下推导技巧.

增加枚举量

$$\begin{aligned} \sum_{ i = 1 }^{ n } \sum_{ j = 1 }^m gcd ( i , j ) & = \sum_{ i = 1 }^n \sum_{ j = 1 }^m id [ gcd ( i , j ) ] \\ & = \sum_{ i = 1 }^n \sum_{ j = 1 }^m \sum_{ d | gcd ( i , j ) } \varphi ( d ) \\ \end{aligned}$$

交换枚举顺序

$$\begin{aligned} \sum_{ i = 1 }^n \sum_{ j = 1 }^m \sum_{ d | gcd ( i , j ) } \varphi ( d ) & = \sum_{ d = 1 }^{ \min ( n , m ) } \sum^{ \lfloor \frac{ n }{ d } \rfloor }_{ i = 1 } \sum^{ \lfloor \frac{ m }{ d } \rfloor }_{ j = 1 } \varphi ( d ) \\ \end{aligned}$$

分离无关变量

$$\begin{aligned} \sum_{ d = 1 }^{ \min ( n , m ) } \sum^{ \lfloor \frac{ n }{ d } \rfloor }_{ i = 1 } \sum^{ \lfloor \frac{ m }{ d } \rfloor }_{ j = 1 } \varphi ( d ) & = \sum^{ \min ( n , m ) }_{ d = 1 } \varphi ( d ) \times \lfloor \cfrac{ n }{ d } \rfloor \times \lfloor \cfrac{ m }{ d } \rfloor \\ \end{aligned}$$

考虑使用数论分块,只需处理出$\varphi ( d )$的前缀和即可在$O ( \sqrt{ n } + \sqrt{ m } )$的复杂度解决此问题.

Example3

求$\sum_{ i = 1 }^{ n } \sum_{ j = 1 }^m [ gcd ( i , j ) = 1 ] \\$.

和上一道题几乎没区别,唯一不同的是需要处理的函数从$id$变为了$\epsilon$.

Example4

求$\sum_{ i = 1 }^{ n } \sum_{ j = 1 }^m [ gcd ( i , j ) \in \mathrm{ prime } ] \\$.

考虑增加枚举量,则:

$$\begin{aligned} \sum_{ i = 1 }^{ n } \sum_{ j = 1 }^m [ gcd ( i , j ) & \in \mathrm{ prime } ] = \sum_{ i = 1 }^{ n } \sum_{ j = 1 }^m \sum_{ p \in \mathrm{ prime } } [ gcd ( i , j ) = p ] \\ & = \sum_{ p \in \mathrm{ prime } } \sum^{ \lfloor \frac{ n }{ d } \rfloor }_{ i = 1 } \sum^{ \lfloor \frac{ m }{ d } \rfloor }_{ j = 1 } [ gcd ( pi , pj ) = p ] \\ & = \sum_{ p \in \mathrm{ prime } } \sum^{ \lfloor \frac{ n }{ p } \rfloor }_{ i = 1 } \sum^{ \lfloor \frac{ m }{ p } \rfloor }_{ j = 1 } [ gcd ( i , j ) = 1 ] \\ & = \sum_{ p \in \mathrm{ prime } } \sum_{ d = 1 }^{ \min ( \lfloor \frac{ m }{ p } \rfloor , \lfloor \frac{ n }{ p } \rfloor ) } \mu ( d ) \lfloor \cfrac{ n }{ pd } \rfloor \lfloor \cfrac{ m }{ pd } \rfloor \\ \end{aligned}$$

于是转化为上一道题,但复杂度仍不可接受.

换元

考虑设$x = pd$,则变为$\sum_{ x = 1 }^{ \min ( n , m ) } \sum_{ p \in \mathrm{ prime } \land p | x } \mu ( \frac{ x }{ p } ) \lfloor \frac{ n }{ x } \rfloor \lfloor \frac{ m }{ x } \rfloor \\$.

Example5([UR #5]怎样跑得更快)

首先先考虑去掉$lcm$使得式子中只有$i , j , \gcd ( i , j )$.

显然可以构造函数$f ( x ) = x^{ c - d } , g ( x ) = x^d , h ( x ) = x^d \\$,然后将题目转化为$\sum_{ j = 1 }^n f ( gcd ( i , j ) ) g ( i ) h ( j ) x_j \equiv b_i ( \mod p ) \\$.

$\gcd ( i , j )$很难处理,于是考虑用莫比乌斯反演消掉.

可以求出$f_r ( n )$使得$f ( n ) = \sum_{ d | n } f_r ( d ) \\$,也即$f_r ( n ) = \sum_{ d | n } \mu ( \cfrac{ n }{ d } ) f ( d )$.

则原式即:

$$\begin{aligned} \sum_{ j = 1 }^n \sum_{ d } [ d | i ] [ d | j ] f_r ( d ) g ( i ) h ( j ) x_j & \equiv b_i ( \mod p ) \\ \sum_{ d | i } f_r ( d ) \sum_{ j = 1 }^n [ d | j ] h ( j ) x_j & \equiv \frac{ b_i }{ g ( i ) } ( \mod p ) \\ \end{aligned}$$

令$z_d = \sum_{ j = 1 }^n [ d | j ] h ( j ) x_j \\$,有$\sum_{ d | i } f_r ( d ) z_d \equiv \frac{ b_i }{ g ( i ) } ( \mod p ) \\$.

这个也是一个莫比乌斯反演的形式,我们可以求出左边,进而求出$z_d$.

而$z_d = \sum_{ j = 1 }^n [ d | j ] h ( j ) x_j = \sum_{ d | j }^n h ( j ) x_j$,可以再次使用莫比乌斯反演求出$h ( j ) x_j$,进而求$x_j$.

无解条件显然是$g_i = 0 \land x_i \ne 0$.

简而言之,这个题的步骤就是:

1. 通过增加枚举量消掉$lcm$以及$\gcd$这些难以处理的项.

2. 将$i$与$j$尽量分到式子两边.

3. 先通过莫比乌斯反演求出一些值,再通过这些值反推.

Example6([CF1566H]Xor-quiz)

首先注意到一个重要的事实:我们只需要询问所有$\mu ( x ) \ne 0$的$x$,就可以得到全部信息,而这些$x$的数量是完全足够我们全部询问一遍的.

注意到一个事实是,异或是模意义下的按位加减法,这意味着我们可以对异或做莫比乌斯反演.事实上,我们有:

$$\begin{aligned} f ( n ) & = \bigoplus_{ i \in A } i [ \gcd ( i , n ) = 1 ] \\ & = \bigoplus_{ i \in A }^c i \sum_{ d | i , d | n } \mu ( d ) \\ \end{aligned}$$

注意到$\sum_{ d | i } \mu ( d ) = \bigoplus_{ d | i } | \mu ( d ) |$,于是:

$$f ( n ) = \bigoplus_{ d | n } | \mu ( d ) | \bigoplus_{ d | i , i \in A } i$$

接下来只要我们形式上写作$n$,我们就默认$\mu ( n ) \ne 0$,又令$g ( n ) = \bigoplus_{ n | i , i \in A } i$,此时自然有$f ( n ) = \bigoplus_{ d | n } g ( d ) \\$.这是一个经典的莫反形式,我们再反演回去就可以得到$g ( n ) = \bigoplus_{ d | n } \mu ( \frac{ n }{ d } ) f ( d ) = \bigoplus_{ d | n } f ( d )$,也就是说我们可以求得所有的$g ( n )$,也就是这个集合中所有是$n$的倍数的异或值.

注意一个事实:如果我们设$w ( m ) = \prod_{ p \in \mathrm{ prime } , p | m } p$,那么我们就可以按照$w$的不同将所有数划分为若干个集合,每个集合在每次查询的时候要么都不被异或要么都被异或.这也告诉我们:我们只能求出每个集合中被选进$A$的这些数的异或值,而不能分开得知它们.接下来考虑如何知道这个,不妨设$S ( n ) = \{ x | w ( x ) = n \}$,又设$h ( n ) = \bigoplus_{ i \in A , i \in S ( n ) } i$.考虑用$g ( n )$表示$h ( n )$,我们有:

$$g ( n ) = \bigoplus_{ n | d } | \mu ( \frac{ d }{ n } ) | h ( d )$$

反演,有$h ( n ) = \bigoplus_{ n | d } g ( d ) \\$.于是我们可以求得所有的$h ( n )$了.

现在的问题在于:对于数$n , \mu ( n ) \ne 0$,我们要在$S ( n )$中选出若干个数,使得它们的异或和为$h ( n )$,并且选出的数字总共有$| A |$个.

然后是根据数据随机,拿每个集合的线性基随机一下自由元,然后对着构造.多随机几次,最后做背包.

多重子集反演

设$S$为可重集合.

一般形式:定义$\mu ( S )$,若$S$包含重复元素则为$0$,否则为$( - 1 )^{ | S | }$.

$$\begin{aligned} f ( S ) & = \sum_{ T \subseteq S } g ( T ) \Leftrightarrow g ( S ) = \sum_{ T \subseteq S } \mu ( S - T ) f ( T ) \\ \end{aligned}$$

证明:

根据莫比乌斯反演,这个是显然的.

单位根反演(离散傅里叶变换)

一般形式($\omega_n = e^{ \frac{ 2 \pi i }{ n } }$):

$$f_m = \sum_{ k = 0 }^{ n - 1 } \omega_n^{ mk } g_k \Leftrightarrow g_m = \frac{ 1 }{ n } \sum_{ k = 0 }^{ n - 1 } \omega_n^{ - mk } f_k$$

可以发现这个式子其实就是FFT时所做的DFT与IDFT.

一般情况

考虑莫比乌斯反演的过程,我们实际上使用的是$[ m | n ] \sum_{ d | \frac{ n }{ m } } \mu ( d ) = [ n = m ] \\$.

令$c = md$,左边$= \sum_{ c | n } [ m | c ] \mu ( \frac{ c }{ m } ) = \sum ( [ c | n ] ) ( [ m | c ] \mu ( \frac{ c }{ m } ) ) \\$.

令$A_{ c , n } = [ c | n ]$,$B_{ m , c } = [ m | c ] \mu ( \frac{ c }{ m } ) \\$,那我们有$BA = I$.

刚才的过程相当于:

$$\begin{aligned} Ax & = b \\ x & = Ix \\ x & = ( BA ) x \\ x & = B ( Ax ) \\ x & = Bb \\ \end{aligned}$$

无论是二项式反演还是莫比乌斯反演,他们都满足$f ( n )$所依赖的$g ( k )$有$k \leq n \\$.

根据上面的情况,我们发现$A$是一个下三角矩阵,$B$是$A^{ - 1 }$.

现在来推导满足$k \leq n$的一般情况反演:

$$\begin{aligned} f ( n ) & = \sum_{ k = 1 }^n a_{ n , k } g ( k ) \\ \end{aligned}$$

不妨设算子$\mu ( n , m )$,满足$\sum_{ k = 1 }^n a_{ n , k } \mu ( k , m ) = \sum_{ k = 1 }^n \mu ( n , k ) a_{ k , m } = [ n = m ] \\$.

即$AB = BA = I \\$.

$$\begin{aligned} g ( n ) & = \sum_{ m = 1 }^n [ n = m ] g ( m ) \\ & = \sum_{ m = 1 }^n \sum_{ k = 1 }^n \mu ( n , k ) a_{ k , m } g ( m ) \\ & = \sum_{ k = 1 }^n \mu ( n , k ) f ( k ) \\ \end{aligned}$$

由上我们发现,反演解决了一些在下标上的二元运算卷积:

$$\begin{aligned} c_r & = \sum_{ p , q } [ f ( p , q ) = r ] a_p b_q \\ \end{aligned}$$

而我们需要把$f$分成两个独立的部分,通常正变换一下,处理一下,逆变换回来.

容斥

一般形式

即:将求并集中元素个数转化成了求交集中元素个数.

我们有:$\mid \bigcup_{ i = 1 }^n S_i \mid = \sum_{ T \subseteq \{ 1 , . . . , n \},T\ne \emptyset } ( - 1 )^{ | T - 1 | } \mid \bigcap_{ p \in T } S_p \mid$.

证明:我们考虑对于每个元素,看它对最终答案的贡献.假设它所属$m$个集合$S_1 , . . . , S_m$,而除了这些集合以外的集合,

$$\begin{aligned} cnt & = \sum_{ i = 1 }^m ( - 1 )^{ i - 1 } \binom{ m }{ i } \\ & = \binom{ m }{ 0 } - \sum_{ i = 0 }^m ( - 1 )^i \binom{ m }{ i } \\ & = 1 - [ m = 0 ] \end{aligned}$$

显然,当这个元素被包含的时候,贡献为$1$,反之贡献为$0$.

如果我们定义一类在集合上的函数$F ( S ) = \sum_{ p \in S } F ( p )$,那么自然也有:

$$F ( \bigcup_{ i = 1 }^n S_i ) = \sum_{ T \subseteq \{ 1 , . . . , n \} } ( - 1 )^{ | T | - 1 } F ( \bigcap_{ p \in T } S_p )$$

另外,我们上面的做法是:当交集好求时求并集.我们还可以使用一步补集转化:

$$\mid \bigcap_{ i = 1 }^n S_i \mid = | U | - \mid \bigcup_{ i = 1 }^n \overline{ S_i } \mid$$

这样我们同样可以在并集好求的时候求交集.

会发现容斥和二项式反演是很像的.但是不一样的是,容斥是从集合的角度考虑,更注重单个元素的贡献;二项式反演是从函数的角度考虑,更关注函数之间的转化.

Example1(不定方程非负整数解计数)

考虑不定方程$\sum_{ i = 1 }^n x_i = m$,和$n$个限制条件$x_i \leq b_i$,其中$m$和$b_i$都是非负整数,求该方程的非负整数解的数目.

首先,我们需要找出全集$U$,以及刻画$U$中元素的$P_i$(条件):

1. $U$是满足$\sum_{ i = 1 }^n x_i = m$的所有非负整数解;

2. 对于每个变量$i$,都对应一个$P_i = [ x_i \leq b_i ]$.

设所有满足$P_i$的解构成集合$S_i$,那么我们需要求解的值就是$\mid \bigcap_{ i = 1 }^n S_i \mid$.而$\mid U \mid$显然是$\binom{ m + n - 1 }{ n - 1 }$.我们有:$\mid \bigcap_{ i = 1 }^n S_i \mid = | U | - \mid \bigcup_{ i = 1 }^n \overline{ S_i } \mid$.考虑对$\mid \bigcup_{ i = 1 }^n \overline{ S_i } \mid$使用容斥原理,注意到$\overline{ S_i }$的意义是满足$x_{ i } \geq b_{ i } + 1$的解的数目.换句话说也就是部分变量有下界限制,那直接左右两边同时减去下界即可.于是枚举子集即可实现.

欸,等一下,咋想到的补集转化,又是咋想到要用容斥的捏?

我们冷静一下,首先补集转化和容斥都是一个思想:正难则反.我们要求满足条件的个数,就先想一下能不能求不满足条件的个数,然后拿总的个数减去.然后注意到不满足条件的意义是:有至少一个不满足,这样就很可以容斥了.

Example2(错排问题)

我们考虑从容斥的角度再次认识一下错排.

首先,我们需要找出全集$U$,以及刻画$U$中元素的$P_i$(条件):

1. $U$是长度为$n$的所有排列;

2. 对于每个变量$i$,都对应一个$P_i = [ p_i \ne i ]$.

注意到所求仍然是$\mid \bigcap_{ i = 1 }^n S_i \mid$.于是我们仍然试图$| \bigcap_{ k = 1 }^m \overline{ S_{ a_k } } |$.考虑其意义,也即:有$m$个位置被确定了,而其它位置没有限制,于是$| \bigcap_{ k = 1 }^m \overline{ S_{ a_k } } | = \binom{ n }{ m } ( n - m ) !$.根据容斥,自然有:$d_n = n ! - \sum_{ m = 1 }^n ( - 1 )^{ m - 1 } \binom{ n }{ m } ( n - m ) ! = n ! \sum_{ m = 0 }^n \cfrac{ ( - 1 )^m }{ m ! }$.

Example3(bzoj3622已经没有什么好害怕的了)

首先可以用dp+双指针得到$f_i$表示勒令$i$对满足条件的方案数.把$k$的定义改为恰好$k$对满足条件的显然是同强度的.

我们接下来仍然考虑容斥,首先,我们需要找出全集$U$,以及刻画$U$中元素的$P_i$(条件).

等一下,这个好像不好刻画?

我们先回归一下容斥的本质:考虑每个元素的贡献.注意到恰好$a$对的方案会被钦定$b$对的方案计算$\binom{ b }{ a }$次.我们再考虑一种方式理解容斥:我们一步一步把正确的答案消出来:简单来说,我第一步让所有恰好为$k$的方案贡献为$1$,其它的可能也有贡献,但我们忽略他们.第二步让所有恰好为$k + 1$的方案贡献为$0$,第三步以此类推.于是这个题,我们考虑也这么做:这样第一步令$ans = f_k$,第二步除去其中被多算的$k + 1$,这一步令$ans - = \binom{ k + 1 }{ k } f_{ k + 1 }$.这个时候,我们再考虑$k + 2$的贡献:它将在$f_k$时贡献$\binom{ k + 2 }{ k }$次,在$f_{ k + 1 }$时贡献$- \binom{ k + 2 }{ k + 1 } \binom{ k + 1 }{ k } = - \binom{ k + 2 }{ k } \binom{ 2 }{ 1 }$次,那它现在的贡献还有:$- \binom{ k + 2 }{ k }$次.以此类推,可以得到$ans = \sum_{ i = k }^n f_i ( - 1 )^{ i - k } \binom{ i }{ k }$.

等一下,这也太麻烦了,就不能从集合的角度分析嘛?

冷静一下,如果我们要做容斥,我们必须考虑每个元素单独的贡献,但是在这个题中,每个元素并没有单独的贡献,而是整个集合需要满足性质才能贡献.也就是说,我们无法分析每个$P_i$.而考虑集合就需要将集合分类,从而使用二项式反演.

换句话说,这个定义在集合上的函数并不满足可加性.

换句话说,我们要用容斥,就一定要刻画$P_i$,因为只有这个时候,我们才能通过分析满不满足$P_i$的解集的交并来实现.

再换句话说,大部分的所谓的容斥其实都和集合没啥关系,我们做容斥就是需要逐个考虑贡献,把它们贡献全都杀成$1 / 0$就行.

Example4(HAOI2008硬币购物)

如果直接对于每次询问暴力做,复杂度显然是$O ( 4 ns )$,无法接受.于是考虑预处理来降低单词询问复杂度.

注意到硬币数量很少,并且每个硬币的贡献可以独立计算.我们完全可以刻画$P_i = [ use_i \leq d_i ]$,从而可以用容斥做.复杂度$O ( 4 s + n 2^4 )$.

Example5

Alice和Bob在玩游戏,他们有一个$n$个点的无向完全图,设所有的边组成了集合$E$,他们想取遍$E$的所有非空子集,对某个集合$S$有一个估价$f ( S )$:考虑$n$个点与$S$中的边组成的图,我们用$m$种颜色对所有点染色,其中同一个连通块的点必须染成一种颜色,那么$f ( S )$等于这个图的染色方案数.同时,Alice喜欢奇数,所以当$| S |$为奇数时,Alice的分值加上$f ( S )$,否则Alice的分值减去$f ( S )$,求最后的分值.$( n , m \leq 10^6 )$.

一开始抄题的时候没有写染色而是直接写”设$k$为连通块个数,则$f ( S ) = m^k$.”然后发现做不了,因为$| S |$相同的$f ( S )$不尽相同,而且可能情况还蛮多的.冷静一下,注意到连通块这个性质太强了:如果我们把它放到指数上,那应该会做得很痛苦.所以我们考虑每有一个连通块就乘上一个$m$,这个看上去就简单一些.

但是这样好像还是不太好做,毕竟现在我们面对的还是一个难以转化为计数问题的图论问题,只是把问题的单位元素从图变成了连通块.那我们能不能再进一步:把单位元素换成单点呢?

考虑由于连通块要染一种颜色,那$x \leftrightarrow y \Rightarrow col_x = col_y$.注意到这是一个单位元素更小的限制条件!并且我们发现我们将与$- 1$有关的单位元素(从一开始就是点)和与$f$有关的单位元素统一起来了.这也提示我们做计数的时候,尤其是做容斥的计数的时候,最好先将单位元统一,这样后面才可能更容易做.

接下来就可以写式子了,令$F ( C )$表示在$C$情况下的染色方案,$T_{ ( i , j ) }$表示满足边$( i , j )$限制的解集:

$$ans = \sum_{ \emptyset \ne S \subseteq E } ( - 1 )^{ | S | - 1 } F ( \bigcap_{ ( i , j ) \in S } T_{ ( i , j ) } )$$

冷静一下!这个东西和容斥长得那叫一个一模一样啊.我们看看能不能逆向分析出$ans$的意义:显然是$F ( \bigcup_{ i = 1 }^{ m } P_i )$.也就是完全图中至少有两个点颜色相同的染色数.根据补集转化,我们只需求出两两点不相同的染色数即可.所以最后的答案就是$m^n - m^{ \underline{ n } }$.

Example6

求$\varphi ( n )$.

考虑这么一个事实:假设$n = \prod p_i^{ q_i }$,注意到令$P_i = [ \gcd ( i , n ) = 1 ]$,我们所求也就是$\mid \bigcap_{ i = 1 }^n S_i \mid$.于是可以用上面的方法做.另外,这里的做法引出莫比乌斯反演.

Example7(AGC058D)

直接容斥好像不太可做,我们把容斥中的条件改为有多少个极长的形如$ABCABCAB . . .$这样的串.

乍一看这个极长的条件好像巨难满足,但实际上我们冷静一下,我们只需要满足这个串长度大于等于$3$并且开头不能往前延申就可以了,后面其实是没啥必要管的.

拿组合数算一算.

Example8(AGC035F)

显然问题只在于重复计算的问题.我们先将所有状态做一个双射:对于一个网格,唯一可能被重复计算的只可能是一个拐角的$1$,我们让这种情况下的行尽可能长.

然后捏?注意到这样的话一个拐角的角一定是行了,是列就一定不合法,我们考虑把不合法的列杀了.

于是做一下容斥,答案是$\sum_{ i = 0 }^{ \min ( n , m ) } ( - 1 )^i \binom{ n }{ i } \binom{ m }{ i } i ! ( m + 1 )^{ n - i } ( n + 1 )^{ m - i }$.

Example9

给定若干个限制条件$( x , y )$,表示$a_x = y$和$a_y = x$必须满足至少一个,求排列方案数.

首先$i \rightarrow p_i$把排列转化成图,这样上面的限制条件也就是有一些无向的链和环,最后定向.一开始以为随便做做,思考一下注意到如果有长度为$2$的链,它自己成环的话是不用$\times 2$的.

这咋办.一个办法是:我们考虑容斥,先随便放进去,最后再钦定若干个自己成环.诶等一下为啥这个容斥是对的?因为系数是$\times 2$,所以一个有$1$个单独成环的状态会被随便放的情况恰好多算一次.类似可以做容斥.

当然,也可以考虑先把其它的合并,最后做长度为$2$的链,但是!一开始一定要钦定有序,最后再用组合数统一算答案.因为一开始带着顺序做很难做.

Example10([AGC036F] Square Constraints)

由题意得:$n^2 - i^2 \leq P_i^2 \leq ( 2 n )^2 - i^2$.

当一个东西有上界又有下界的时候可以想到容斥.问题转化为只有上界.假设最后所有的上界为$l_i$,那么只有上界的答案应该是什么呢?将$l$从小到大排序,答案就是$\prod_{ i = 0 }^{ 2 n - 1 } ( l_i - i )$.(注意到必须满足$l_{ 2 n - 1 } = 2 n - 1$.)

但是这个东西和容斥怎么结合起来呢?我们将限制放到二维平面上,注意到上下界的限制其实是两个$\frac{ 1 }{ 4 }$的圆弧.而通过圆弧的性质不难看出:最终的$l$分为三部分:在下半部分圆弧上的,在上半部分圆弧后面的,在上半部分圆弧前面的.而如果想知道$l$按照顺序排序,我们只需要对前两部分做归并,然后将最后一部分直接放到后面即可.于是我们考虑按照$l$的大小为顺序进行一个类似归并的东西,每次判断当前下半部分圆弧是否要往上加点即可.这样我们可以处理前两部分对答案的贡献,但问题在于第三部分对答案的贡献怎么做,我们需要找到第三部分上的点在排序后的位置.我们预先枚举容斥集合的大小即可,这样就可以快速算出这个东西,于是复杂度$O ( n^3 )$.

Example11([23省选第一轮集训day4]C带劲的旅行)

(下面将$n$和$m$反着写)

设$p = \frac{ 2 k }{ n } , q = n - p$.

首先注意到期望$= P [ len \geq 1 ] + P [ len \geq 2 ] + \cdots$.

考虑如何计算$P [ len \geq x ]$,如果我们设$a_i$表示以$i$作为开头的极长的带劲的长度大于等于$x$的序列的集合,那么最后无非是要求所有$a$的并.考虑用容斥做到求所有$a$的交.不过要注意讨论一下是不是第一个点.

Example12

给定$n , k$和$n$个点各自的颜色,对有编号无根树计数,要求相同颜色组成的连通块大小不超过$k$.$n \leq 300$.

著名结论:$n$个点$m$个连通块任意连边成树的方案数是$n^{ m - 2 } \prod s$,其中$s$是每个连通块的大小.但是,如果我们强行对每种颜色分成若干连通块,我们要防止它们之间有边.这就是我一开始没做出来的原因:要容斥的根本不是树的大小不能超过$k$,由于树的形态多变,这个是不能维护的!正确的做法是找到若干个相同颜色的大小小于等于$k$的连通块,要求它们两两无边.甚至根本就不是它们可以连边但是大小不能超过$k$,我们要容斥的东西一定要好算,简单.

然后就做完了,每次暴力合并若干个颜色相同的块,容斥系数$( - 1 )^{ 块 数 - 1 }$.

容斥是一个层层递进的东西,我们每一步都是基于上一步的限制:它本身就是一个求解集的东西.

Min-Max容斥

对于:

$$\mid \bigcup_{ i = 1 }^n S_i \mid = \sum_{ T \subseteq \{ 1 , . . . , n \} } ( - 1 )^{ | T - 1 | } \mid \bigcap_{ p \in T } S_p \mid$$

考虑一个特例:$S_i = \{ 1 , 2 , \cdots , a_i \}$,那么上面的式子导出min-max容斥(我们设$S = \{ a_1 , a_2 , \cdots , a_n \}$)(第二个式子可以把前缀改成后缀):

$$\begin{aligned} \max ( S ) & = \sum_{ T \subseteq S , T \ne \emptyset } ( - 1 )^{ | T | - 1 } \min ( T ) \\ \min ( S ) & = \sum_{ T \subseteq S , T \ne \emptyset } ( - 1 )^{ | T | - 1 } \max ( T ) \end{aligned}$$

由于是集合,这个式子在期望意义下同样成立:

$$\begin{aligned} E ( \max \{ S \} ) & = \sum_{ T \subseteq S , T \ne \emptyset } ( - 1 )^{ | T | - 1 } E ( \min \{ S \} ) \\ E ( \min \{ S \} ) & = \sum_{ T \subseteq S , T \ne \emptyset } ( - 1 )^{ | T | - 1 } E ( \max \{ S \} ) \end{aligned}$$

进一步,这个式子可不止能求min-max的转化,它可以求出集合中第k大的数字:

$$\begin{aligned} kth \max \{ S \} & = \sum_{ T \subseteq S , T \ne \emptyset } ( - 1 )^{ | T | - k } \binom{ | T | - 1 }{ k - 1 } \min \{ T \} \\ kth \min \{ S \} & = \sum_{ T \subseteq S , T \ne \emptyset } ( - 1 )^{ | T | - k } \binom{ | T | - 1 }{ k - 1 } \max \{ T \} \\ E ( kth \max \{ S \} ) & = \sum_{ T \subseteq S , T \ne \emptyset } ( - 1 )^{ | T | - k } \binom{ | T | - 1 }{ k - 1 } E ( \min \{ T \} ) \\ E ( kth \min \{ S \} ) & = \sum_{ T \subseteq S , T \ne \emptyset } ( - 1 )^{ | T | - k } \binom{ | T | - 1 }{ k - 1 } E ( \max \{ T \} ) \end{aligned}$$

原理是消掉前$k - 1$大的数字,让他们的贡献为$0$,剩下的配一下容斥系数.

Example1([23省选10连测 day6]A)

不妨设$tim_i$为$[ i , i + 1 ]$第一次被覆盖的时间,答案就是:

$$E ( \max_{ i = 1 }^{ n - 1 } \{ tim_i \} ) = \sum_{ T \subseteq \{ 1 , 2 , \cdots , n - 1 \} , T \ne \emptyset } ( - 1 )^{ | T | - 1 } E ( \min_{ j \in T } \{ tim_j \} )$$

设$f ( S )$为有多少个区间能覆盖至少一个$[ i , i + 1 ] , i \in S$,考虑$E = p_{ [ t \geq 0 ] } + p_{ [ t \geq 1 ] } + p_{ [ t \geq 2 ] } + \cdots$,于是$E ( \min_{ j \in S } \{ tim_j \} ) = \frac{ m }{ f ( S ) }$.

于是:

$$\begin{aligned} ans & = \sum_{ T \subseteq \{ 1 , 2 , \cdots , n - 1 \} , T \ne \emptyset } ( - 1 )^{ | T | - 1 } f ( T ) \\ & = \sum_{ k = 0 }^m \frac{ m }{ k } \sum_{ T \subseteq \{ 1 , 2 , \cdots , n - 1 \} , T \ne \emptyset , f ( T ) = k } ( - 1 )^{ | T | - 1 } \end{aligned}$$

注意到$f ( S )$可能不那么好求,我们求$g ( S ) = m - f ( S )$,也就是不包含任何一个$[ i , i + 1 ] , i \in S$的区间个数,我们有:

$$ans = \sum_{ k = 0 }^m \frac{ m }{ m - k } \sum_{ T \subseteq \{ 1 , 2 , \cdots , n - 1 \} , T \ne \emptyset , g ( T ) = k } ( - 1 )^{ | T | - 1 }$$

这里已经不难写出$O ( n^3 )$的dp了.

那么怎么优化呢?设$dp_{ i , j }$表示只考虑$[ 1 , i ]$时($[ i - 1 , i ]$必选),$\sum_{ g ( T ) = j } ( - 1 )^{ | T | - 1 }$的答案,不难发现每次加入一个区间$[ l , r ]$就会让$dp_{ i , j } , i < = l$对$dp_{ r , j + 1 }$的贡献乘一个$1$.

如何处理这个事情?我们用类似多项式的东西,前者相当于平移多项式系数,后者相当于标量乘法,然后拿线段树维护和,复杂度$O ( nm \log n )$.

反射容斥

一般形式:给定二维平面上两个点$S$和$T$,其中$T$在$S$的右方,给定两条线$y = a$和$y = b$,每次可以向右上或者右下走一步,求不碰线的从$S$到$T$的方案数.

我们不妨设$A$表示一定碰了一次上界的方案数,$B$表示一定碰了一次下界的方案数,$AB$表示一定碰了一次上界后碰了一次下界的方案数……

最后的答案就是随便走$- A - B + AB + BA - ABA - BAB . . .$.

考虑设步数为$n$,那显然长度最多为$\cfrac{ n }{ a - b }$.