一些计数问题

Published: by Creative Commons Licence

  • Tags:

图计数

颜色统计

题目1:给定一颗大小为$n$的树,每个顶点都有一个颜色。之后给定$m$个请求。每个请求分为两类:

  • 修改某个顶点的颜色
  • 查询某条路径上颜色为$x$的顶点数

提供一道题目

修改颜色的请求可以认为是删除一个颜色并增加一个新的颜色,即分解为两个请求。我们可以将所有请求按照颜色分组,同组按照发生顺序先后执行。

这样我们只需要处理单种颜色的增加删除,这可以视作每个顶点有一个点权,我们可以修改单点点权,并查询路径点权。这个问题就比较烂大街了,LCT或者用DFS序+差分技术都可以解决。

时间复杂度为$O((n+m)\log_2n)$。

删除叶子方法

题目1:给定一颗大小为$n$的树,每次操作你可以选择一个叶子删除。现在问对于$k=0,\ldots,n$,执行$k$次操作的可能操作序列有多少个,答案对素数$p$取模。

提供一道题目

首先考虑给定根为$1$的情况,记录$dp(i,j)$表示$i$的子树中执行$j$次操作的方案数。那么可以发现我们可以$O(n^2)$实现计数。

接下来考虑不给定根的情况,这个情况比较复杂。但是我们可以枚举最后一次删除的顶点,以他为根进行dp。这样的话时间复杂度为$O(n^3)$。

子树计数

题目1:给定一颗包含$n$个顶点的树,树根为顶点$1$,每个顶点$i$上有一个数字$a_i$。现在回答$q$个查询。第$i$个请求给定顶点$r$,以及一个整数$m$,定义顶点$r$的值为$f_r(r)=a_{r}$,定义其下子树中的任意顶点$u$的值为$f_r(u)=f_r(p_u)+a_u$,其中$p_u$表示$u$的父亲节点,要求找出以$r$为根的子树中有多少个顶点的值不小于$m$。其中$1\leq n,q\leq 5\times 10^5$,$1\leq a_i,m\leq 10^9$。

这道题需要用到差分技术。可以发现$f_r(i)=f_1(i)-f_1(r)+a_r$。因此我们只需要维护$f_1$即可。之后我们把请求挂到对应的顶点上去,之后在树上dfs。一个结点dfs后把以该结点为根的子树中的所有$f_1$值丢到一颗稀疏权值线段树中去,这样就能$O(n\log_2n)$实现合并和查询操作,总的时间复杂度为$O(n\log_2n)$。

异构树

题目1:给定$n$个顶点,问这$n$个顶点给定的无根树数目。结果模素数$p$。

根据prufer编码与树唯一对应关系可知,只需要统计它们的prufer编码数目。prufer编码的长度为$n$,其中每个元素均可以为$1$到$n$之间的任意值,因此答案为$n^{n-2}$。这个答案对于$n=1$的情况也是成立的。

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

题目2:给定$n$个顶点。问这$n$个顶点给定的有根树数目。结果模素数$p$。

题目1给出了无根树的数目为$n^{n-2}$,由于每个无根树都可以视作$n$个不同的有根树,因此有根树的数目为$n^{n-2}\times n=n^{n-1}$。

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

函数图

考虑任意函数$f:S\rightarrow S$,其中$S=[1,n]$。它的函数图如下:建立$n$个顶点,对于$1\leq i\leq n$,从$i$向$f(i)$加入一条有向边。

简单来看,可以发现函数图具有如下性质:

  • 每个顶点的出度正好为$1$。
  • 每个连通块正好有一个环。
  • 每个函数图和$S\times S$上的函数唯一对应。

题目1:给定$n$,问存在多少个不同的大小为$n$函数图。将结果对某个素数$p$取模。

可以直接统计函数数目,答案为$n^n$。

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

题目2:给定$n$,要求存在多少大小为$n$的函数图,满足图连通(将有向边视作无向边后连通)。答案对某个素数$p$取模。

在图连通的前提下,图实际上是一颗树加上一条边。当然树是无向边,而函数图是有向边,但是可以发现我们将函数图中唯一的环缩点后,并将这个顶点作为根,将树边全部从孩子指向父亲,就可以唯一恢复成函数图。因此可以发现函数图的数量和这样的树加上额外的一条边得到的图数量是相同的。

这里我们可以简单的枚举环的长度。考虑环的长度为$i$,那么缩点后共有$n-i+1$个顶点,其对应的生成树的数目为$n^{n-i-1}$,注意这里之所以底数是$n$而不是$n-i+1$,是因为我们如果缩点每次出现在prufer编码中,会使得它的度数增加$1$,我们需要考虑这条边具体连接到缩点前的哪个顶点,因此总的可能数是$n-i+i=n$。同样如果prufer中一个顶点出现次数为$x$,则其度数为$x+1$,因此我们还需要额外乘上一个$i$。并且我们还需要考虑环中的元素和其排列,因此总数为:

\[\sum_{i=1}^n{n \choose i}\times (i-1)!\times i\times n^{n-i-1}\]

上面我们可以$O(n)$计算出结果。

题目3:给定$n$,对于$k=1,2,\ldots,n$,问存在多少不同的函数图,正好有$k$个连通块。将结果对某个素数$p$取模。

提供一道题目

我们可以利用题目2计算单个连通块的技术加上DP,这样可以得到一个$O(n^3)$的算法。

但是我们实际上可以将算法优化到$O(n^2)$,方案如下。

我们先考虑只有一个连通块的情况,就是

\[\sum_{i=1}^n{n \choose i}\times (i-1)!\times i\times n^{n-i-1}\]

这里我们可以稍微修改一下流程,我们考虑在环中的元素数目为$i$,则其方案数为:

\[{n \choose i}\times i\times n^{n-i-1}\]

之后我们将选中的$i$个元素拆分成$k$个非空环,这样就能得到结果。方案数可以通过无符号第一类斯特林数得到。因此对于给定的$k$,答案为:

\[\sum_{i=1}^n{n \choose i}\times i\times n^{n-i-1}\times \left[ \begin{array}{} i\\ k \end{array} \right]\]

对于特定的$k$,可以$O(n)$算出。总的时间复杂度为$O(n^2)$。

生成树

题目1:给定$n$个顶点$m$条边的无向(有向)图,计算对应的生成树数目。答案对某个素数取模。

矩阵树定理的基础应用。

时间复杂度为$O(n^3+m)$。

欧拉路径

题目1:给定$n$个顶点$m$条边的有向图,计算对应的欧拉环路数目。答案对某个素数取模。

BEST定理的应用。

时间复杂度为$O(n^3+m)$。

题目2:给定$n$个顶点,顶点$i$到$i+1\mod n$有一条无向边$i$。给定$a_0,a_1,\ldots,a_{n-1}$,要求计算存在多少条环路,满足经过边$i$正好$a_i$次。结果对素数取模。

提供一道题目

考虑边$i$,我们记其正向经过次数为$x_i$,逆向经过次数为$y_i$。将每条边正向逆向出现次数相消后,图应该依旧满足欧拉环路的定理才有意义。此时每个顶点的入度出度相等,可以发现每条边$i$的正向或逆向经过次数均为某个数$k$。

我们可以大力枚举这个数$k$,正向和逆向各需要枚举一次。之后边$i$剩余正向和逆向经过次数为$(a_i-k)/2$。这时候图是有向图,我们可以用题目1的方式计算有向图的欧拉迹数目。每次计算的时间复杂度为$O(k^3)$。总的时间复杂度为$O(k^3\sum_{i}a_i)$。

匹配计数

题目1:给定长度为$n$的两个序列$a_1,\ldots,a_n$以及$b_1,\ldots,b_n$。如果$a_i\leq b_j$,则认为这两个数可以匹配。计算两个序列的最大匹配数目,结果对素数$p$取模。

我们可以预先对两个序列进行排序。现在考虑$dp(i,j)$表示处理完$b_1,\ldots,b_i$,记$a_t$为不大于$b_i$的最大的数,$a_1,\ldots,a_t$中有$j$个数尚未被匹配,此时的方案数。

上面的公式转移是$O(1)$的,因此时间复杂度为$O(n^2)$。

题目2:给定长度为$n$的两个序列$a_1,\ldots,a_n$以及$b_1,\ldots,b_n$。如果$a_i\leq b_j$,则认为这两个数可以匹配。计算两个序列的极大匹配数目,结果对素数$p$取模。一个匹配是极大的,当且仅当所有未匹配的数之间都不能相互匹配,比如$a=1,3$,$b=2,4$,那么$(1,4)$匹配后,剩下的两个数$3,2$无法相互匹配,因此$(1,4)$是极大匹配,但不是最大匹配。

提供一道题目

首先我们需要考虑$a$中最小的未被匹配的数,记其为$a_t$,则对于$i\lt t$,$a_i$一定被匹配。考虑$b_k$为最小的数,满足$b_k\geq a_t$,则对于$i\geq k$,$b_i$一定被匹配。满足这些条件的匹配一定是极大的。

具体计算方法是,我们可以定义$dp(i,j)$表示$b_1,\ldots,b_i$已经全部处理完了,记$a_k$为最大的数,满足$a_k\leq b_i$,其中$a_1,\ldots,a_k$中还有$j$个数需要被匹配。之后的转移和题目1类似。这里计算dp的时间复杂度为$O(n^2)$,总的时间复杂度为$O(n^3)$。

但是实际上我们可以把对$t$的选择一起放入到dp中,具体的做法是定义$dp(i,j,k)$,其中$i,j$意义类似,但是$k=1$表示已经选择了$a_t$,$k=0$表示$a_t$未选择。这样时间复杂度就可以优化到$O(n^2)$。

序列计数

相邻不同序列

题目1:有$n$个球,第$i$个球的颜色为$c_i$。要求统计有多少不同的排列,满足排列中任意两个相邻的球的颜色不同,将结果模素数$p$后输出。其中$\leq n\leq 10000$,且$1\leq c_i\leq n$

提供一道题目

记录$C_i$表示颜色为$i$的球的出现次数。首先我们可以预先认定同色球在最终序列中的出现顺序。之后记录集合$A_{i,j}$表示颜色为$i$的球,第$j$个出现的球和第$j+1$出现的球紧密相连的序列集合。则我们要求的是

\[|\cap_i\cap_{1\leq j\lt C_i}\overline{A_{i,j}}|=|S|-|\cup_i\cup_{1\leq j\lt C_i}A_{i,j}|\]

接下来就是一个简单的容斥,可以展开为:

\[\sum_{X\lt C}[(-1)^{\sum X}][\prod_i{C_i-1\choose X_i}] [\frac{(n-\sum X)!}{\prod_{i}(C_i-X_i)!}]\]

这个公式可以化为多个生成函数的乘积。其中

\[P_i=\sum_{j=0}^{C_i-1}(-1)^j{C_i-1\choose j}\frac{1}{(C_i-j)!}x^j\]

记它们的乘积为$Q=\sum_{i}q_ix^i$。则结果为$\sum_{i}q_i(n-i)!$。

上面的算法的时间复杂度为$O(n(\log_2n)^2)$。当然如果你用一般的DP也可以做到$O(n^2)$。

集合计数

分组问题

题目1:将$n$个编号的球放入$m$个带编号的篮子里,有多少种放法。

每个球有$m$种放法,且不同的球的方法是独立的,因此结果为$m^n$。

题目2:将$n$个未编号的球放入$m$个带编号的篮子里,有多少种放法。

记$x_i$表示第$i$个篮子里的球数,此时有$x_1+x_2+\ldots+x_m=n$成立。这个可以用隔板法解决,答案是${n+m-1\choose m-1}$。

题目3:将$n$个带编号的球放入$m$个未编号的篮子里,有多少种放法。

可以将篮子先编上号,可以发现此时答案是$m^n$。之后我们发现每种真实的方案对应$m!$种编号后的方案,因此答案是$\frac{m^n}{m!}$。

题目4:将$n$个带编号的球放入$m$个未编号的篮子里,且要求每个篮子不空,有多少种放法。

这实际上是第二类斯特林数,答案是$\begin{Bmatrix}n\\m\end{Bmatrix}$。

题目5:将$n$个未编号的球放入$m$个未编号的篮子里,有多少种放法。

可以用动态规划求解。记$dp(i,j,k)$表示每个篮子最多放$i$个球,共$j$个篮子,放$k$个球的方案,这个dp可以$O(n^2m)$求解。

网格计数

覆盖问题

题目1:给定一个大小为$2\times n$的网格,要求在网格上放一些矩形,使得矩形互不相交且网格被完全覆盖。求方案数,结果对素数取模。

提供一道题目

定义$A(i)$表示宽度为$2\times i$的网格覆盖方案数,且要求最右边两个网格被不同矩阵覆盖。定义$B(i)$表示宽度为$2\times i$的网格覆盖方案数,且要求最右边的两个网格是被同一个矩阵覆盖。

可以推出

\[\left\{ \begin{array}{l} B(i)=A(i-1)+B(i-1)\times 2\\ A(i)=B(i)+A(i-1)\times 2^2 \end{array} \right.\]

而答案为$B(n)+A(n)$。

唯一行计数

题目1:给定一个$n$行$m$列的网格,每个网格存在一个数字。现在要求回答$q$个询问,第$i$个询问要求仅考虑若干列(去除不被考虑的列),将每一行看成一个数值序列,问有多少个序列是唯一的。其中$1\leq n\leq 60$,$1\leq m\leq 20$,网格中数值绝对值不超过$10^9$。

提供一道问题

首先我们可以用哈希+哈希表来做,但是很复杂且常数很大。

我们可以暴力枚举每一行,考虑它在哪些情况下产生贡献。很显然它只在某些列集使得它唯一的前提下产生贡献。

考虑什么时候会唯一。我们维护一个序列$b_1,\ldots,b_m$,其中$b_i$表示哪些行在第$i$个字符与我们第一行不同,我们可以用二进制表示集合。之后我们考虑它什么时候唯一,很显然如果列集为$C_1,\ldots,C_k$的时候,它仅在$\left\{2,3,\ldots,n\right\}\subseteq b_{C_1}\lor b_{C_2}\lor \ldots \lor b_{C_k}$的时候会产生一贡献。我们可以通过位压找到所有会使得第一行唯一的列集。时间复杂度为$O(2^m)$。

由于我们会暴力枚举每一行来考虑它的贡献,因此总的时间复杂度为$O(n2^m)$。

棋盘问题

题目1:给定一个$n\times n$的网格,要求在上面放$n$个棋子,同行或同列只能放一个棋子,问放法数目,结果模素数。

每一种放法实际上对应一种置换,因此答案为$n!$。

时间复杂度为$O(n)$。

题目2:给定一个$n\times n$的网格,要求在上面放$n$个棋子,同行或同列只能放一个棋子,且对角线上不允许放棋子,问放法数目,结果模素数。

可以用容斥来解决。答案为$n!\sum_{i=0}^n(-1)^i\frac{1}{i!}$。

时间复杂度为$O(n)$。

题目3:给定一个$n\times n$的网格,要求在上面放$n$个棋子,同行或同列只能放一个棋子,且部分网格上不允许放棋子,问放法数目,结果模$2$。

考虑行列式的定义,可以发现行列式实际上就是统计有多少排列,之后乘上$1$或$-1$,而在模$2$的情况下,$-1=1$,因此此时答案就是$det(A)$,$A$为$n\times n$矩阵,允许放的位置为$1$,其它位置为$0$。

时间复杂度为$O(\frac{n^3}{32})$。

题目4:给定一个$n\times n$的网格,要求在同一条斜线上最多只能放一个棋子,要求正好放入$k$个棋子,问放法数目,结果模素数。

斜线上控制比较麻烦,将网格选择$45^o$得到一个棱形,这时候就是要求竖线和横线上不能放。

接下来可以用DP来统计,我们将行重新排列,较小的行排在前面优先放置。这样DP就不需要记录具体哪些列被放置了,而只需要记录放置了几列。

时间复杂度为$O(n\min(n,k))$,这里如果$k>2n$的时候是无解的。

题目5:给定一个$n\times n$的网格,每个网格允许放黑色棋子或者白色棋子,要求黑色棋子之间不能共行或共列,而白色棋子之间也不能共行或共列,且要求分别放$n$个黑色棋子和$n$个白色棋子,问有多少放法。结果模素数。

我们建立$n$个顶点,对于行$i$,黑色棋子出现的位置记作$a$,白色棋子出现的位置记作$b$,则我们加入一条有向边$(a,b)$。可以发现每个顶点的入度和出度均为$1$,且不存在自环。

因此问题实际上在问存在多少个置换$p$,其中$p(i)\neq i$,这个结果为$n!\sum_{i=0}^n(-1)^i\frac{1}{i!}$。之后把置换放入到网格中,我们可以对行做$n!$种重排,答案为$(n!)^2\sum_{i=0}^n(-1)^i\frac{1}{i!}$。

时间复杂度为$O(n)$。

题目6:给定一个$n\times n$的网格,每个网格允许放黑色棋子或者白色棋子,要求黑色棋子之间不能共行或共列,而白色棋子之间也不能共行或共列,且有些网格已经预先放好白色或黑色棋子了,要求放置一定数量的黑白其中,使得棋盘上$n$黑色棋子和$n$白色棋子的数目均为$n$,问有多少放法。结果模素数。

提供一道题目

记$a$为已经同时放好黑白棋子的行数,$b$为仅放好黑色棋子的行数,$c$为仅放好白色棋子的行数。$b_1$为$b$行中黑色棋子不存在同列白色棋子数,$c_1$为$c$行中白色棋子不存在同列黑色棋子数。$d$为空列数。

我们需要对$p(i)$是否等于$i$进行容斥。答案为:

\[(n-a-b-c)!\sum_{x=1\rightarrow b_1}\sum_{y=1\rightarrow d}\sum_{z=1\rightarrow c_1}(-1)^{x+y+z}{b_1\choose x}{d\choose y}{c_1\choose z}\\ {n-a-c-y-x \choose b-x}(b-x)!\\ {n-a-b-y-z\choose c-z}(c-z)!\\ (n-a-b-c-y)!\]

由于$b_1+d+c_1\leq n$,因此$b_1\cdot d\cdot c_1\leq (\frac{n}{3})^3$,时间复杂度为$O((\frac{n}{3})^3)$。

路径计数

题目1:给定一个$n\times m$的网格,其中你处于左下角$(0,0)$,目的地是右上角$(n-1,m-1)$。允许每次向上或向右移动。其中存在$k$个点称为关键点$(x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k)$,保证起点和终点不是关键点。要求计算路径中正好经过$0,1,2,\ldots,t$个关键点的路径数。其中$k\leq 1000$,$n,m\leq 10^5$,$t\leq 100$。

提供一道题目

记$dp(i,j)$表示从起点到第$i$个关键点,总共正好经过了$j$个关键点的路径数。一般的转移计算方法是需要枚举上一个关键点的位置,但是计算二者的路径时,可能会途径其它的关键点,这一点很麻烦。为了解决这个问题,我们定义$dp2(i,j)$表示从起点到第$i$个关键点,至少经过了$j$个关键点的路径数。可以发现$dp$可以通过$dp2$差分得到。

现在考虑$dp2(i,j)$的计算方式。我们可以枚举路径上经过的正好第$j-1$个关键点$p$,之后从$p$转移到$i$。可以发现这样不会重复统计,且每条路径正好只被统计一次。这里比较特殊的就是$dp2(i,0)$,它实际上等于${x_i+y_i\choose x_i}$。

数值计数

题目1:给定$n$个非负数$a_1,\ldots,a_n$,要求计算存在多少个非负整数$x$,满足$x\leq \min(a_1,\ldots,a_n)$,使得$a_1-x\oplus \ldots \oplus a_n-x=0$。其中$a_i\leq 10^{18}$。

提供一道题目

我们记录$dp(i,j)$表示仅考虑最低的$i$个二进制位,有多少方案存在,满足$a$中正好有$j$个数最低的$i$个二进制位小于$x$的最低的$i$个二进制位。答案很显然为$dp(60,0)$。

$dp(i,j)$可能产生的操作仅两种,一种是设置第$i+1$位为$0$,还有一种是设置第$i+1$位为$1$。我们这里可以使用双指针技术来加速,因此时间复杂度为$O(60n)$。