组合数学-526互联

一、加乘原理

加法原理

一件事，有 $n$ 类方法可以实现它，第 $i$ 类方法有 $a[i]$ 种方法实现，那么总共有 $\sum_{i=1}^na[i]$ 种方法实现。

乘法原理

一件事，有 $n$ 个步骤可以实现它，第 $i$ 个步骤有 $a[i]$ 种方法实现，那么总共有 $\prod_{i=1}^na[i]$ 种方法实现。

二、排列数与组合数

排列数

从 $n$ 个不同的数中任选 $m$ 个数，按照一定顺序排成一列的方案数，记作$ A_n^m $，计算公式为：

\[A_n^m=\frac{n!}{m!(n-m)!} \]

组合数

从 $n$ 个不同的数中任选 $m$ 个数组成一个集合的方案数，记作$ C_n^m $，计算公式为：

\[C_n^m=\frac{n!}{(n-m)!} \]

也可以记为：

\[\tbinom{n}{m} \]

读作：$n$ 选 $m$

三、组合数的性质

性质一

\[C_n^m=C_n^{n-m} \]

证明:从 $n$ 个数中选 $m$ 个相当于不选 $n-m$ 个。

性质二

\[C_n^{m}=C_{n-1}^{m-1}+C_{n-1}^m \]

证明：对于最后一个元素，如果不选它，那么在剩下的 $n-1$ 个元素中选 $m$ 个元素；否则再剩下的 $n-1$ 个元素中选 $m-1$ 个元素。

这是组合数的递推公式。

性质三

\[\sum_{i=0}^mC_{m}^i=2^m \]

证明：根据二项式定理：

\[(x+y)^n=\sum_{i=0}^{n}C_{n}^ix^iy^{n-i} \]

显然，$\sum_{i=0}^mC_{m}^i=(1+1)^m=2^m$

性质四

\[\sum_{i=0}^{m}(-1)^iC_{m}^i=0 \]

证明：若 $m$ 为奇数，则由性质一可知正确

若 $m$ 为偶数，利用性质二的递推公式，则

$\sum_{i=0}^{m}(-1)^iC_{m}^i$

$=\sum_{i=0}^{m}(-1)^i(C_{m-1}^i+C_{m-1}^{i-1})$

$=C_{m-1}^{0}-C_{m-1}^{0}-C_{m-1}^{1}+C_{m-1}^{1}+C_{m-1}^{2}-...+C_{m-1}^{m-1}=0$

P3197 [HNOI2008] 越狱

运用“正难则反”思想，问题可以转化为“所有状态减去任意相邻犯人宗教都不同的状态”。

先考虑所有状态。每个人信仰的宗教有 $m$ 种可能，且相互无影响，那么 $n$ 个人就有 $m^n$ 种可能。

再考虑任意相邻的犯人宗教不同的状态。只考虑第一个人，他信仰的宗教有 $m$ 种可能。如果增加一个犯人，那么他信仰的宗教不能与前面相同，有 $m-1$ 种可能。一共有 $m\times (m-1)^{n-1}$ 。

综上，答案就是 $m^n-m\times (m-1)^{n-1}$ 。

P2822 [NOIP2016 提高组] 组合数问题

利用性质二递推求得组合数，然后再对 $k$ 取模，如果模数为 $0$ 说明能被 $k$ 整除。然后再做一个二维前缀和，询问的时候直接 $0(1)$ 输出即可。

P1350 车的放置

将原图分为三个矩形，分别是左上角，左下角，右下角的矩形。

然后先考虑对于 $n\times m$ 的矩形，放 $k$ 个不互相攻击的车的方案数。每放一个车，矩形就少了一行，一列能放车的位置，再去重，答案就是

\[\frac{A_n^k\times A_m^k}{k!} \]

再考虑原题的答案。假设左下角的矩形放了 $i$ 个车，左上角的矩形放了 $j$ 个车，那么右下角的矩形放了 $k-i-j$ 个车。对于左下角的矩形，它的车会使得左上角的矩形能放车的位置少了 $i$ 列，右下角的矩形能放车的位置少了 $i$ 行。因此，最终答案是：

\[\sum_{i=0}^k\sum_{j=0}^{k-i}\frac{A_a^i\space A_d^i\space A_{a-i}^j\space A_b^j\space A_c^{k-j-i}\space A_{d-i}^{k-i-j}}{i!\space j!\space (k-i-j)!} \]

P3166 [CQOI2014] 数三角形

$solution 1$

问题可以转化为：任选三个点的方案数 $-$ 三点共线的方案数。

任选三点的方案数： $n\times m$ 的方格共有 $(n+1)\times (m+1)$ 个点，所以方案数为 $C_{(n+1)\times (m+1)}^{3}$ 。

三点共线的方案数：

先考虑平行于 $x$ 轴或 $y$ 轴的方案数，显然为 $C_{n+1}^{3}\times (m+1)+C_{m+1}^3\times (n+1)$ 。

再考虑剩下的方案数。三点所在的直线斜率可正可负，但斜率为正的方案数与斜率为负的方案数相等，所以先只考虑斜率为正的方案数，再乘以 $2$ 。

引理：对于两个点，如果它们的横坐标差为 $i$ ，纵坐标差为 $j$ ，那么它们确定的线段上格点（包括两个端点）的数量为 $gcd(i,j)+1$

而我们要求的是三点共线的方案数，相当于求固定两个点时，中间的第三个点的数量，所以应该是 $gcd(i,j)-1$ 。因此每次枚举横坐标差，纵坐标差，答案就是：

\[\sum_{i=1}^n\sum_{j=1}^m(n-i+1)\times (m-j+1)\times (gcd(i,j)-1) \]

乘以 $(n-i+1)\times (m-j+1)$ 的含义是，横坐标差为 $i$ ，纵坐标差为 $j$ 的点对共有这么多个。

时间复杂度： $O(nm)$ ，足以通过本题。

$solution 2$

但这还不够！

看到 $gcd(i,j)$ ，可以考虑用欧拉反演优化。

\[\sum_{i=1}^n\sum_{j=1}^m(n-i+1)\times (m-j+1)\times (gcd(i,j)-1) \]

\[=\sum_{i=1}^n\sum_{j=1}^m(n-i+1)\times (m-j+1)\times (\sum_{k|gcd(i,j)}\phi(k)-1) \]

\[=-\frac {n(n+1)m(m+1)}{4}+\sum_{d=1}^{min(n,m)}\phi(d)\times[\lfloor\frac {n}{d}\rfloor (n+1)-\frac {d\lfloor\frac {n}{d}\rfloor(\lfloor\frac {n}{d}\rfloor+1)}{2}][\lfloor\frac {m}{d}\rfloor (m+1)-\frac {d\lfloor\frac {m}{d}\rfloor(\lfloor\frac {m}{d}\rfloor+1)}{2}] \]

时间复杂度 $O(min(n,m))$ ，通过本题绰绰有余。

$code:$

int work(int d){
    return ((m/d)*(m+1)-d*((m/d)*(m/d+1)/2))*((n/d)*(n+1)-d*((n/d)*(n/d+1)/2));
}
signed main(){
    pre_work();
    scanf("%lld%lld",&n,&m);
    for(int d=1;d<=min(n,m);++d)
        ans=(ans+(phi[d]*work(d)));
    ans-=(n*(n+1)/2)*(m*(m+1)/2);
    ans=ans*2;
    ans=(ans+((n+1)*c(m+1,3)+(m+1)*c(n+1,3)));
    ans=(c((n+1)*(m+1),3)-ans);
    printf("%lld\n",ans);
    return 0;
}

四、容斥原理

设 $S_1,S_2,S_3...$ 为有限集合，$|S|$表示集合大小，则

\[|\cup_{i=1}^nS_i|=\sum_{i=1}^n|S_i|-\sum_{1<=i<j<=n}^n|S_i\cap S_j|+\sum_{1<=i<j<k<=n}^n|S_i\cap S_j\cap S_k|+...+(-1)^{n-1}|S_1\cap S_2\cap ...\cap S_n| \]

P1450 硬币购物

问题可以转化为：选任意多的硬币购买的方案数 $-$ 不符题意的方案数

对于前半部分，只需要预处理一个完全背包即可。

对于后半部分，先状态压缩枚举哪些硬币用的次数超过限制，然后可以强制让它们选 $d[i]+1$ 个，来代表它们是超过限制的，而此时还需要凑 $s-\sum(d[i]+1)\times c[i]$ 的钱，还需要凑的钱任意凑即可。

$code:$

while(n--){
	scanf("%lld%lld%lld%lld%lld",&d[1],&d[2],&d[3],&d[4],&s);
	ans=0;
	for(int i=0;i<(1<<4);++i){
		int tmp=i,num=1,cnt=0,sum=0;
		while(tmp){
			if(tmp&1) ++cnt,sum+=(1+d[num])*c[num];
			tmp>>=1;++num;
		}
		if(s-sum>=0){
			if(cnt&1) ans-=f[s-sum];
			else ans+=f[s-sum];
		} 
	}
	printf("%lld\n",ans);
}

五、二项式反演

形式 $0$：

\[f(n)=\sum_{i=0}^n(-1)^iC_n^ig(i)\iff g(n)=\sum_{i=0}^n(-1)^iC_n^if(i) \]

形式 $1$：

\[f(n)=\sum_{i=0}^nC_n^ig(i)\iff g(n)=\sum_{i=0}^n(-1)^{n-i}C_n^if(i) \]

形式 $2$：

\[f(n)=\sum_{i=n}^mC_i^ng(i)\iff g(n)=\sum_{i=n}^m(-1)^{i-n}C_i^nf(i) \]

其中形式1与形式2较为常用。形式1常用于“至多”与“恰好”的相互转化，形式2常用与“至少”与“恰好”的相互转化。

P6478 [NOI Online #2 提高组] 游戏

题目中要求的“恰好”，直接求较难，可以转化为“至少”。令 $g(k)$ 表示“恰好有 $k$ 次非平局”的方案数，$f(k)$ 表示“钦定 $k$ 次非平局”（也就是至少有 $k$ 次非平局）的方案数。根据二项式反演的形式二，有：

\[f(k)=\sum_{i=k}^mC_i^kg(i)\iff g(k)=\sum_{i=k}^m(-1)^{i-k}C_i^kf(i) \]

因此，只需要求出 $f$ ，就能求出 $g$ 。

求 $f$ 可以用树形 $DP$ 。令 $dp[i][j]$ 表示，以 $i$ 为根的子树中，至少有 $j$ 次非平局的方案数。

如果只考虑子树，那么有状态转移方程：

\[dp[i][j]=\sum_{k1+k2+...+kn=j}dp[son_1][k_1]\times dp[son_2][k_2]...\times dp[son_n][k_n] \]

用树形背包即可。

然后再考虑第 $i$ 个点的贡献。设 $A[i],B[i]$ 分别表示以 $i$ 为根的子树内，属于小 $A$ 和小 $B$ 的点的个数。假设节点 $i$ 属于小 $A$ ，则有状态转移方程：

\[dp[i][j]=dp[i][j]+dp[i][j-1]\times max\{B[i]-(j-1),0\} \]

含义是，小 $A$ 用一次 $i$ 节点，小 $B$ 用一次 $i$ 子树内的节点，构成一次非平局。因为已经有了 $j-1$ 次非平局，所以 $B[i]$ 要减去 $(j-1)$ ，并检查它减完以后是否大于 $0$ 。注意这个转移需要倒序转移，因为转移时用的是转移前的 $dp[i][j-1]$ 。

求出 $dp$ 以后，有 $f[k]=dp[1][k]\times (m-k)!$ ，含义是钦定了 $k$ 局非平局以后，剩下的 $m-k$ 局自由组合。

$code:$

void dfs(int x,int fa){//预处理出a[i]和b[i]
    a[x]=(s[x-1]=='0');
    b[x]=1-a[x];
    for(int i=head[x];i;i=nxt[i])
        if(ver[i]!=fa){
            dfs(ver[i],x);
            a[x]+=a[ver[i]];b[x]+=b[ver[i]];
        }
}
void solve(int x,int fa){//DP部分
    f[x][0]=1;siz[x]=0;//siz[x]不是子树大小，而是状态转移的上界
    for(int i=head[x];i;i=nxt[i])
        if(ver[i]!=fa){
            solve(ver[i],x);
            for(int j=0;j<=siz[x]+siz[ver[i]];++j)
                g[j]=f[x][j],f[x][j]=0;
            for(int j=0;j<=siz[x];++j)
                for(int k=0;k<=siz[ver[i]];++k)
                    f[x][j+k]=(f[x][j+k]+(g[j]*f[ver[i]][k]%mod))%mod;
            siz[x]+=siz[ver[i]];

        }
    int tmp=((s[x-1]=='0')?b[x]:a[x]);
    for(int i=siz[x];i>=0;--i)
        f[x][i+1]=(f[x][i+1]+(f[x][i]*max(0ll,tmp-i)%mod))%mod;
    if(f[x][siz[x]+1])
        ++siz[x];
}

六、斯特林数

P5395 第二类斯特林数·行

求 $n$ 个不同元素放入 $m$ 个相同集合（非空）的方案数。

首先考虑把 $n$ 个不同元素放入 $m$ 个不同集合（可以有空集）的方案数。每个元素有 $m$ 种放法，所以方案数为 $m^n$ 。

上述问题可以看成“至多有 $m$ 个空集”的情况，而斯特林数是“恰好有0个空集”的情况。因此，有

\[m^n=\sum_{i=0}^m\begin{Bmatrix} n \\i \end{Bmatrix}i!C_m^i \]

其中，$i!$是指这 $m$ 个集合的全排列，将相同的集合转化为不同的集合。

根据二项式反演的形式一，有：

\[\begin{Bmatrix} n \\m \end{Bmatrix}m!=\sum_{i=0}^m\frac{i^n(-1)^{m-i}m!}{i!(m-i)!} \]

也就是：

\[\begin{Bmatrix} n \\m \end{Bmatrix}=\sum_{i=0}^m\frac{i^n(-1)^{m-i}}{i!(m-i)!} \]

然后令$F(x)=\sum_{i=0}^n\frac{i^n}{i!}$，$G(x)=\sum_{i=0}^n\frac{(-1)^i}{i!}$，于是$\begin{Bmatrix} n \\m \end{Bmatrix}$的值就是$F*G$的第$m$项的系数。$NTT$计算多项式乘法即可。

$code:$

signed main(){
    scanf("%lld",&n);
    inv[0]=1;
    for(int i=1;i<=n;++i)
        inv[i]=inv[i-1]*fpow(i,mod-2)%mod;
    int w=1;
    for(int i=0;i<=n;++i){
        a[i]=fpow(i,n)*inv[i]%mod;
        b[i]=(w*inv[i]+mod)%mod;
        w*=-1;
    }
    mul(a,b,n);//多项式乘法
    for(int i=0;i<=n;++i)
        printf("%lld ",a[i]);
    printf("\n");
    return 0;
}