计数习题总结

SetAndSet

给出一个长度为$n$的非负整数序列$a$，要求将$a$中的元素染红或染蓝，使得：

1. 至少有一个红色元素；
2. 至少有一个蓝色元素；
3. 红色元素的按位与等于蓝色元素的按位与。

问有多少种合法的染色方案。

$n\le 50,a_i<2^{20}$。

容斥

考虑二进制下第$x$位。如果所有数的第$x$位都是 1，那么就可以不管这一位。否则，这一位为$0$的数不能全部分在一个集合。

考虑容斥，容斥哪些位的$0$分在同一集合。那么转化为无限制减去全部分在同一集合，用并查集统计有多少个连通块，容斥贡献就是$2^{cnt}-2$，减 2 是因为要非空。

使用 DFS 写容斥可以少一个$20$，时间复杂度$O(2^{20}n)$。

代码

Endless Spin

给出$n$个球排成一排。初始时每个球都是白的。每次从$\frac{n(n+1)}{2}$个区间中等概率选择一个区间，把里面的求染黑。问期望多少次可以把所有球染黑。

$n\le 50$。

期望 容斥 DP

设随机变量$x_i$表示第$i$个球被染黑的时间，且$S=\{x_1,\cdots,x_n\}$。那么答案可以表示为

$$E(\max S)=\sum_{T\subseteq S}E(\min T)(-1)^{|T|-1}\\$$

对于集合$T$，我们需要求出，选到至少一个球的期望时间。期望是概率的倒数，转化为选到至少一个球的概率。那么假设对于集合$T$的元素，有$A$个区间可以让我们至少选到一个元素，那么概率就为$\Pr(T)=\frac{2A}{n(n+1)}$，因此期望为$\frac{1}{\Pr(T)}$。

那么如果我们求出

$$F(k)\sum_{T\in S,|T|=k}\frac{1}{\Pr(T)}$$

答案就为

$$\sum_{k=1}^{|S|}F(k)(-1)^{k}$$

考虑“至少选到一个”不好求，我们转化为，求一个都选不到。设$f(i,j,k)$表示考虑前$i$个点，有恰好$j$个区间，最后一个被选的点到第$i$个点的距离为$k$，使得这$j$个区间选不到白点的方案数（可以理解为这个概率的出现次数），再记一个$bit$表示这个部分的容斥系数：

$$f(i,j,k,bit) \to f(i+1,j,0,\neg bit)\\ f(i,j,k,bit) \to f(i+1,j+k+1,k+1,bit)$$

那么答案为

$$\sum_{A=0}^{\frac{1}{2}n(n+1)-1}\sum_{k=0}^n\frac{1}{1-\frac{2A}{n(n+1)}}\cdot f(n,A,k,bit)(-1)^{bit}$$

高精度用 python 打表即可。

时间复杂度$O(n^4)$。

代码

代码 python

CTS2019 随机立方体

有一个$n\times m\times l$的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标至少有一维相同的其他格子（三个方向的格子的集合）里的数都要大的话，我们就称它是极大的。

现在将$1,2,\cdots,nml$随机填入到$n\times m\times l$个格子中，使得每个数恰出现一次，求恰有$k$个极大的数的概率，对$998244353$取模。

$n,m,l\le 5\times 10^6,k\le 100$。

二项式反演 概率 组合数 线性求逆元

设$g(k)$表示恰有$k$个的概率。那么设$f(k)$表示至少有$k$个的概率。那么每个$g(i)$就被$f(k)$计算了$\dbinom{i}{k}$次，根据二项式反演，得到

$$\begin{aligned} f(k)&=\sum_{i=k}^n\binom{i}{k}g(i)\\ g(k)&=\sum_{i=k}^n\binom{i}{k}f(i)(-1)^{i-k} \end{aligned}$$

考虑求$f(k)$。显然我们可以钦定$k$个最大值，那么不妨设这$k$个最大值的位置分别在$(i,i,i),i\in[1,k]$的地方。并且我们要求$a_{i,i,i}\le a_{i+1,i+1,i+1},i\in[1,k)$。然后这$k$个数是各自的 3 个方向上切面的最大值。容易发现，这形成了一个树形结构（可以看二维的情况模拟得到），那么我们的问题等价于，给一棵树的每个结点分配一个标号，使得每个点是子树最大值的概率。答案即为每个子树的大小之和。由于这棵树的形态特殊，因此实际上可以得到概率为

$$\prod_{i=1}^k\frac{1}{nml-(n-i)(m-i)(l-i)}$$

然后考虑这$k$个最大值的位置（刚才我们是钦定的位置，没有讨论过），那么第一个有$nml$种选择，第二个有$(n-1)(m-1)(l-1)$种选择，以此类推。则总方案数为$n^{\underline{k}}m^{\underline{k}}l^{\underline{k}}$。因此得到

$$f(k)=n^{\underline{k}}m^{\underline{k}}l^{\underline{k}}\prod_{i=1}^k\frac{1}{nml-(n-i)(m-i)(l-i)}$$

显然$f$是可以递推的：

$$\begin{aligned} f(i)&=f(i-1)(n-i+1)(m-i+1)(l-i+1)a_i\\ a_i&=\frac{1}{nml-(n-i)(m-i)(l-i)} \end{aligned}$$

那么我们线性求$a_i$的逆元即可（注意，线性求逆元在$a_i$含有 0 的时候有 bug，但是本题中不会出现这种情况），时间复杂度$O(n)$。

代码

Square Constraints

设

$$\begin{aligned} f(i)&=\left\lfloor \sqrt{n^2-i^2-1} \right\rfloor+1\\ g(i)&=\min\left(\left\lfloor \sqrt{4n^2-i^2} \right\rfloor+1,2n\right) \end{aligned}$$

原题目的限制可以表示为

$$\forall i\in[0,2n),f(i)\le P_i< g(i)$$

考虑容斥下界。那么我们就枚举这$2n$个数中有$k$个数$< f(i)$。假设我们确定了$k$个数$x_1,\cdots,x_k(x_i\in[0,n))$，这个$k$个数的限制是$P_{x_i}<f(x_i)$，所有数的限制是$P_i<g(i)$（注意到$f(i)\le g(i)$，$g$是包含了$f$的），求这样的方案数。那么我们把每个数的限制从小到大排序，形成一个长度为$2n$的数组$h$，那么答案为

$$\prod_{i=0}^{2n-1}(h_i-i)$$

但是这$k$个数是不确定的。我们考虑把$f(i),i\in[0,n)$和$g(i),i\in[0,2n)$放在一起升序排序得到序列$A$，并且我们把$f(i)$标记为a，把$g(i),i\in[0,n)$标记为b，把$g(i),i\in[n,2n)$标记为c。那么$A$的标记数组$B$一定长成aaccac...bbbbb的形式，即a、c全在前面，b在后面的形式。

相当于我们从这$3n$个数中选择$2n$个出来，满足对于$i\in[n,2n)$的部分我们选择$g(i)$（即所有的c必选），然后我们选择$k$个$f(x_i)$（相当于选择$k$个a），然后剩下的选$g(i)$（相当于选择b）。

由于$f(i),g(i)$都是非递增的，因此相当于你选了第$i$个a就不能选第$i$个b。因此我们就转化为了求出，选$k$个数的限制为$<f(i)$的容斥贡献和。这个可以 DP 做，设$F(i,j)$表示在考虑前$i$个数以及对应的前若干个b，我们选$j$个a的容斥贡献和。设$b_i$表示当$B_i=a$时它对应的b的位置，方便转移。那么贡献和就是$F(2n,k)$。

代码

Two Histograms

对于一个方案，如果存在$k_i,l_j$使得$k_i=j-1,l_j=i$，那么我们就把它变成$k_i=j,l_j=i-1$。如果不存在，就是一个“合法”的方案。

我们只需要统计出所有“合法”的方案就是答案。证明见官题。

考虑容斥，则答案为

$$\sum_{i=0}^n\binom{n}{i}\binom{m}{i}i!(m+1)^{n-i}(n+1)^{m-i}(-1)^i$$

代码

HamiltonianPaths

有一个$k$个点的无向简单图，你把它复制$n-1$次变成一个$nk$个点的图，然后求补图的哈密尔顿路径（有向）的数目。

$k\le 14,n\le 5\times 10^4$。

设原图上的边为不合法的边，我们要求不能经过不合法的边。考虑容斥，问题转化为，钦定经过$k$条不合法的边，其他点无限制，问哈密尔顿路径的数目，这样的容斥贡献是$(-1)^k$。

我们先不考虑复制的操作，考虑在原图及其补图上求出经过$k$条不合法的边的哈密尔顿的路径数的容斥贡献和。

更具体地，设$f(S,x)$表示在原图上，点集$S$以$x$结尾的哈密尔顿路径数，乘上容斥系数，这个可以 DP 求出：

$$f(S\cup \{y\},y)=\sum_{(x,y)\in E}(-1)f(S,x)$$

那么设$F(S)$表示在原图上点集$S$的哈密尔顿路径数，即$F(S)=\sum_{x\in S}f(S,x)$。

于是，我们设$g(S,x)$表示在原图上点集$S$被分成$x$条路径的方案数（单点算一条路径），显然可以枚举第一个点 / 最后一个点所在的子集$T$，用$F(T)$转移：

$$g(S,x)=\sum_{T}F(T)g(S\setminus T,x-1)$$

那么，我们就求出了把原图划分为$x$条不合法的路径的方案数的容斥贡献和$G(x)=g(U,x)$。考虑复制了$n-1$遍，能否求出新图的$G$？

答案是可以。注意到复制$n-1$遍的$G$即为$G^n(x)$，因此做$n$次 FFT 即可（用快速幂）。

求出了这个$G^n(x)$，那么答案就为$\sum G^n(i)i!$，表示你把这$i$条不合法路径用$i-1$条合法的边（合法的边就是补图上的边）连起来，连成一个哈密尔顿通路的方案数，显然这$i$条路径的顺序可以任意安排，因此有$i!$种方案。至于容斥系数在一开始的时候就计算过了，因此不用乘$(-1)^k$。

时间复杂度$O(nk\log_2n)$。

代码

ZJOI2016 小星星

我们把双射放缩为一个函数$p(i)\in[1,n]$，那么我们希望$p(1),\cdots,p(n)$中，$1,\cdots,n$都出现过。

考虑容斥，我们枚举哪些值没有出现（即我们允许多个点对应一个点）。没有出现，我们就直接在图上删掉这个点。于是考虑 DP，设$f(u,v)$表示考虑$u$的子树，且$u$和原图上的$v$对应，问有多少种对应方案。转移时枚举每个儿子的对应方案：

$$f(u,v)=\prod_{x\in Son(u)}\sum_{(v,y)\in E}f(x,y)$$

DP 的复杂度是$O(n^3)$的，加上枚举的复杂度，总复杂度$O(n^32^n)$。

代码

Fireflies

设

$$M=\left\lfloor\frac{1}{2}\sum_{i=1}^n(p_i+1)\right\rfloor$$

问题可以通过一堆定理转化为，求$\sum_{i=1}^nx_i=M$且$1\le x_i\le p_i$的解的方案数。

考虑容斥，转化为枚举$S\in[n]$集合内的元素不满足限制，则可以得到

$$\sum_{S\in[n]}(-1)^{|S|}\max\left(0,\binom{M-1-\sum_{x\in S}p_x}{n-1}\right)\\ =\sum_{S\in[n]}(-1)^{|S|}\binom{\max(0,M-1-\sum_{x\in S}p_x)}{n-1}$$

直接做的复杂度为$2^n$，不能接受。考虑 meet-in-middle。

根据范德蒙德卷积

$$\binom{a+b}{n}=\sum_{i=0}^n\binom{a}{i}\binom{b}{n-i}$$

那么我们把$U$拆成两个集合$A,B$，可以得到

$$\binom{M-1-\sum_{x\in S}p_x}{n-1}= \sum_{i=0}^{n-1}\binom{M-1-\sum_{x\in S\cap A}p_x}{n-1-i} \binom{-\sum_{x\in S\cap B}p_x}{i}$$

因此，设$S\in2^A,T\in 2^B$，那么上式可以等价地表示为

$$\binom{M-1-\sum_{x\in S\cup T}p_x}{n-1}= \sum_{i=0}^{n-1}\binom{M-1-\sum_{x\in S}p_x}{n-1-i} \binom{-\sum_{x\in T}p_x}{i}$$

那么原式即为

$$\sum_{S\in 2^A,T\in 2^B}(-1)^{|S\cup T|} \sum_{i=0}^{n-1}\binom{M-1-\sum_{x\in S}p_x}{n-1-i} \binom{-\sum_{x\in T}p_x}{i}\\ =\sum_{S\in 2^A,T\in 2^B} \sum_{i=0}^{n-1}(-1)^{|S|}\binom{M-1-\sum_{x\in S}p_x}{n-1-i} (-1)^{|T|}\binom{-\sum_{x\in T}p_x}{i}$$

设出函数来简化问题

$$\begin{aligned} f(S,i)&=(-1)^{|S|}\binom{M-1-\sum_{x\in S}p_x}{n-1-i} & (S\in 2^A)\\ g(T,i)&=(-1)^{|T|}\binom{-\sum_{x\in T}p_x}{i} & (T\in 2^B) \end{aligned}$$

注意$f(\varnothing,n-1)=g(\varnothing,0)=1$。那么原式进一步简化为

$$\sum_{S\in 2^A,T\in 2^B}\sum_{i=0}^{n-1}f(S,i)g(S,i) =\sum_{i=0}^{n-1}\sum_{S\in 2^A}f(S,i)\sum_{T\in 2^B}g(S,i)$$

那么我们在求和的过程中，只需要保证$M-1-\sum_{x\in S}p_x-\sum_{x\in T}p_x\ge 0$即可。这个可以排序后双指针实现，再加上前缀和优化，就可以$O(2^{n/2}n)$合并答案。$f$，$g$可以各自递推求出：

$$\begin{aligned} f(S,i)&=f(S,i+1)\frac{M-1-\sum_{x\in S}p_x-(n-2-i)}{n-1-i}\\ g(T,i)&=g(T,i-1)\frac{-\sum_{x\in T}p_x-(i-1)}{i} \end{aligned}$$

注意，使用下降幂计算组合数，上部是可以为负数的：

$$\binom{n}{m}=\frac{n^{\underline{m}}}{m!}$$

注意，范德蒙德卷积是可以做负数的。

总复杂度$O(2^{n/2}n)$。

代码