计数题小结

A

一个$n\times m$的网格，每步只能向下或者向右走。有 k 个被 ban 掉的点，不能经过。问左上走到右下的方案数。$n,m\le 10^6,k\le 10^3$。

考虑容斥。设$f_i$表示经过第$i$个 banned 点，在这之前不走 banned 点，之后随便走的方案数。

求$f_i$也可以对前半部分使用容斥，即第一次走到第$k$个 banned 点，在这之前不走 banned 点，然后随便走，走到第$i$个 banned 点，然后随便走的方案数。这样用经过$i$的总方案数减就能求$f_i$。

总复杂度$O(k^2)$。

B

BZOJ 2287

有$n$个体积为$w_i$的物品，对于每一个$x$，求出没有第$x$个物品的情况下剩下$n-1$个物品填满容积为$x$的背包的方案数。

整体的生成函数是

$$\prod_{i=1}^n(1+x^{w_i})$$

那么我们要求的就是

$$\frac{\prod_{i=1}^n(1+x^{w_i})}{(1+x^{w_k})}$$

可以直接大除法，从低位往高位除。

从它的组合意义去理解的话，设$f$表示所有物品的方案数背包，而$g$表示缺失第$k$个物品的方案数背包。则显然有$f_i=g_i+g_{i-w_k}$。现在我们知道$f$，要求$g$，于是直接$g_i=f_i-g_{i-a_k}$即可。

大除法也可以看成是从小到大的 DP 转移。

代码

C

SRM 684 Medium

一个长度为 n 的序列，满足每个元素都是 [1,k] 内的整数, 且对于相邻的两个元素$a=S_i ,b=S_{i+1}$, 有$a\le b$或$a \bmod b \ne 0$。求这样的序列的个数模$10^9+7$。$n,k\le 50000$。

考虑容斥，转化为无限制减去$a>b,b|a$。这可以 DP，$f_i$表示长度为$i$的序列的方案数，则转移的时候枚举$[j+1,i]$这一段是整除序列，然后$j,j+1$是无限制关系。由于$[j+1,i]$的长度是$O(\log_2k)$的，因此预处理一下，直接转移就行了。

二项式反演

$$f_n=\sum\binom{n}{x}g_x\\ \Leftrightarrow g_n=\sum\binom{n}{x}(-1)^xf_x$$

几道计数题

Exercise 1

给一棵有根树$T=(V,E)$，求拓扑序方案数。

设$f(u)$表示$T_u$的拓扑序方案数。那么我们可以发现，它的儿子之间的顺序是无所谓的。于是这就是一个多重集的排列问题。$|T_u|$表示子树 u 的大小。于是

$$f(u)=\frac{(|T_u|-1)!}{\prod_{(u\to v)\in E}|T_v|!}\prod_{(u\to v)\in E}f(v)\\ Ans=n!\prod_{u=1}^n\frac{1}{|T_u|}$$

算概率去理解。

注：$|T_u|-1$相当于 u 的儿子子树大小之和。

Exercise 2

带标号无向连通图计数。

设带标号的无向图个数为$h$，无向不连通图个数为$g$，无向连通图个数为$f$。

$$h(n)=2^{\frac{n(n+1)}{2}}\\ f(n)=h(n)-g(n)$$

现在考虑求$g(n)$。枚举 1 所在的连通块即可。枚举连通块大小，点的标号，剩下的点的连法可得

$$g(n)=\sum_{i=1}^{n-1}\binom{n-1}{i-1}f(i)h(n-i)$$

如果你把 f 代换成 g 就发现，其实这只是一个关于 g 的递归式。所以为了减小常数可以只算 g 和 h，最后就能得到 f

Exercise 3

一个串并联网络具有如下特征：

1. 有一个起点和终点，至少一条边
2. 把两个网络的起点终点首位相接得到是仍是串并联网络
3. 把两个网络的起点终点并起来得到的仍是串并联网络
4. 并联时不考虑并联线路之间的顺序（即他们都是相同的）

现在给定边的数量，问串并联网络的个数。

这是一道小清新的题。事实上你发现，一个串并联网络具有树形结构。一个串联的整体下有若干个并联的线路，一个并联的整体下有若干个串联的线路。因此这就是一个树的结构，且奇偶层分别为串联和并联的结点。于是你根本不用管串联并联的问题，直接对树计数然后答案乘 2 即可。

一个串联或者并联结构至少有两条线路。因此我们要求的是每个内部结点的儿子数大于 1的树的个数。设$f(n)$表示叶子结点总数为 n 的树的个数。

由于你不考虑兄弟结点间的顺序，因此就要有一个单调性的限制。于是再定义$g(i,j)$表示叶结点数为 i，根结点的每颗子树最多包含 j 个叶子的树的方案数。显然，可以枚举包含 j 个叶子的子树数量求 g。假设有 k 个子树包含 j 个叶子，于是就相当于在$f(j)$个方案中选 k 个，可重复。这就是一个不定方程非负整数解的问题，答案为$\dbinom{f(j)+k-1}{f(j)-1}=\dbinom{f(j)+k-1}{k}$：

$$g(i,j)=\sum_{k=0}^{\left\lfloor\frac{i}{j}\right\rfloor}g(i-kj,j-1)\binom{f(j)+k-1}{k}\\$$

因为儿子数大于 1，因此

$$f(i)=g(i,i-1)$$