容斥原理

容斥是门学问。

1.定义

集合 $U$ 中的元素有 $n$ 种不同的属性，而第 $i$ 种属性称为 $P_i$，拥有属性 $P_i$ 的元素构成的集合为 $S_i$，那么：

$$\begin{align} \bigcup_{i=1}^n S_i=& \sum_i |S_i|-\sum_{i<j} |S_i\bigcap S_j|+\sum_{i<j<k}|S_i\bigcap S_j\bigcap S_k|-\dots\\ &+(-1)^{m-1}\sum_{a_i<a_{i+1}}\bigcap_{i=1}^m S_{a_i}+\dots+(-1)^{n-1}|S_1\cap S_2\cap \dots S_n| \end{align}$$

即：

$$\begin{align} \bigcup_{i=1}^n S_i=\sum_{m=1}^{n}(-1)^{m-1}\sum_{a_i<a_{i+1}}\bigcap_{i=1}^m S_{a_i} \end{align}$$

对于证明，我们需要证明每个元素恰好出现一次，把所有出现该元素的集合拿出来，来算其出现次数。设其出现的集合个数为 $m$：

$$\begin{align} cnt&=\binom{m}{1}-\binom{m}{2}+\binom{m}{3}-\dots +(-1)^{m-1}\binom{m}{m}\\ &=\binom{m}{0}-\sum_{i=0}^{m}\binom {m}{i}\\ &=1-(1+(-1))^m=1 \end{align}$$

另外，集合的并可以用全集减去补集的并得到，即：

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

对右边容斥即可。

2.容斥原理一般化

容斥原理是解决计数问题的利器，对于两个集合的函数 $f(S),g(S)$，若：

$$\begin{align} f(S)=\sum_{T\subseteq S}g(T) \end{align}$$

那么有：

$$\begin{align} g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|} f(T) \end{align}$$

同样的对于

$$\begin{align} f(T)=\sum_{T\subseteq S}g(S) \end{align}$$

那么有：

$$\begin{align} g(T)=\sum_{T\subseteq S}(-1)^{|S|-|T|} f(S) \end{align}$$

我们发现上述的 $f(S),g(S)$，可以对应为 “至多/至少” 与 “恰好”。

3.min-max 容斥

对于集合 $S,T$ 且 $T\subseteq S$，那么有：

$$\begin{align} \max_{i\in S}a_i=\sum_{T\subseteq S}(-1)^{|T|+1}\min_{i\in S}a_i\\ \min_{i\in S}a_i=\sum_{T\subseteq S}(-1)^{|T|+1}\max_{i\in S}a_i \end{align}$$

更加重要的是，这个式子在期望意义下也是成立的，即：

$$\begin{align} E(\max_{i\in S}a_i)=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min_{i\in S}a_i)\\ E(\min_{i\in S}a_i)=\sum_{T\subseteq S}(-1)^{|T|+1}E(\max_{i\in S}a_i) \end{align}$$

这就比较好了，因为对于 $(13)$ 式子中，大多数情况下 $\displaystyle E(\min_{a_i\in S}a_i)$ 是相对好求的。

还有更强的：

$$\begin{align} \text{kth}\max_{ i\in S}a_i=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min_{i\in T} a_i\\ \text{kth}\min_{ i\in S}a_i=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\max_{i\in T} a_i \end{align}$$

同样对于期望意义下也是成立的：

$$\begin{align} E(\text{kth}\max_{ i\in S}a_i)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}E(\min_{i\in T} a_i)\\ E(\text{kth}\min_{ i\in S}a_i)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}E(\max_{i\in T} a_i) \end{align}$$

长得很像二项式反演！其实确实可以从二项式反演的角度证明以上等式。

4.例题

1.AGC005D ~K Perm Counting

是个错位排列的扩展。我们尝试用类似的做法解决。设 $f(n)$ 表示钦定 $n$ 个元素满足 $|p_i-i|= k$ 的方案数，相当于求恰好有 $0 $ 个元素满足 $|p_i-i|= k$，利用式子 $(11)$ ，容斥得到答案为：

$$\sum_{i=0}^n (-1)^i (n-i)!f(i)$$

$f(n)$ 怎么求？钦定 $n$ 个元素满足 $p_i=i\pm k$，显然只有 $\bmod 2k$ 的同余类之间才会产生冲突。于是把每个同余类单独拿出来，需要在 $n$ 个点中选 $m$ 个点。将排列转化为二分图上的匹配。我们根据上面的限制对于每个同余类建出来的图是形如一条链的，问题就变为 $n$ 条匹配选 $m$ 条有多少种方案。相当于要求不能有匹配相邻。我们只要选择一条匹配则其后面的一条一定不能选，通过组合数得到方案数为 $\displaystyle \binom{n-m+1}{m}$。再使用背包进行合并不同同余类即可。这样暴力做是 $\mathcal O(n^2)$ 的，足以通过。但其实这个过程我们完全可以用生成函数来做，直接求其卷积即可，时间复杂度就为 $\mathcal O(n\log n)$。

此处为暴力 $\mathcal O(n^2)$ 代码。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10,mod=924844033;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,k;
int fac[N],ifac[N];
int f[N],g[N];
inline int adj(int x){return x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
inline int C(int n,int m)
{
    if(m>n||m<0)return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline void prework(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n]);
    for(int i=n-1;~i;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
int main()
{
    read(n,k);
    prework(n<<1);
    f[0]=1;
    for(int t=1;t<=min(n,k<<1);t++)
    {
        int m=(t>k)+((n-t)/k);
        for(int i=n;~i;i--)
            for(int j=1;j<=min(i,m);j++)
            {
                int res=C(m-j+1,j);
                f[i]=adj(f[i]+1ll*f[i-j]*res%mod);
            }
    }
    int ans=0;
    for(int i=0;i<=n;i++)
        ans=adj(ans+(i&1?mod-1ll*f[i]*fac[n-i]%mod:1ll*f[i]*fac[n-i]%mod));
    printf("%d\n",ans);
    return 0;
}