一些计数问题

Published: January 15, 2021 by Daltao

• Categories:
• algorithm 101

• Tags:

• 图计数
  • 树
    • 颜色统计
    • 删除叶子方法
    • 子树计数
    • 异构树
  • 森林
  • 函数图
  • 生成树
  • 欧拉路径
  • 匹配计数
  • 不相交路径计数
• 序列计数
  • 相邻不同序列
  • 奇偶性计数
  • 赋值方案
  • 0和计数
  • 置换群下去重计数
  • 带比较计数
  • 不允许相邻计数
  • 包含特定子串的字符串数统计
  • 带禁止的置换计数
  • 本质不同非空子串
  • 本质不同子序列
• 集合计数
  • 分组问题
  • 子集计数
  • 多重集合计数
• 网格计数
  • 子矩形计数
  • 覆盖问题
  • 棋盘问题
  • 路径计数
• 数论
  • 位运算
  • 模运算
• 几何计数
  • 矩形计数
• Ad hoc
• 概率计数
• 线性递推计数
• 数论计数

图计数

树

颜色统计

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

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

提供一道题目。

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

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

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

题目2：给定一颗大小为$n$的树，每个顶点都有一个颜色。定义$f_r(u)$表示以$r$为根的时候，$u$为根的子树中不同颜色数。之后处理$q$个请求，每个请求给定$u$和$v$，要求输出$f_u(v)$。其中$1\leq n,m \leq 10^6$，且强制在线。

先假定根为$1$，我们可以用dsu on tree技术，快速统计出$f_1(1),\ldots,f_1(n)$。

之后考虑计算$f_u(v)$，如果$u$在$v$的子树外，那么显然$f_u(v)=f_1(v)$。否则假设$u$在$v$的某个孩子$x$的子树中，这时候$f_u(v)=f_x(v)$。我们可以用欧拉序加二分快速确定$x$。这时候$v$子树中的颜色数，等价于$f_1(1)-g(x)$，其中$g(x)$表示有多少不同颜色，仅出现在$x$为根的子树中。

要计算函数$g$，我们可以通过欧拉序+LCA的技术确定每个颜色所在顶点的最小dfn和最大dfn序，之后找到它们的最低公共祖先$l$，并将$l$以及所有它的祖先的$g$属性全部增加$1$。

总的时间复杂度为$O((n+q)\log_2n)$。

题目3：给定一颗大小为$n$的树，每个顶点都有一个颜色。定义$f_r(u)$表示以$r$为根的时候，$u$为根的子树中不同颜色数。要求输出$n$个整数，第$i$个整数值为$\sum_{j=1}^nf_i(j)$。其中$1\leq n\leq 10^6$

提供一道题目。

考虑离线请求，在树上dfs的同时，维护当前的总和（即如果当前访问的顶点为$u$，则目前总和$\sum_{j=1}^nf_u(j)$）。初始的时候总和已经计算好了。之后考虑从顶点$u$进入它的孩子$v$带来的影响。很显然对于$i\neq u,v$，有$f_u(i)=f_v(i)$成立，只有$f_u(u)$需要切换为$f_v(u)$，以及$f_u(v)$切换为$f_v(v)$，其差量正好为$f_v(u)-f_u(v)$。

可以发现这个过程最多计算了$O(n)$个不同的$f_u(v)$，通过题目$2$的方式我们可以$O(n\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)$。

森林

题目1：计算存在多少包含$n$个顶点的无向无环图，其中$1\leq n\leq 10^5$，结果对素数取模。

提供一道题目。

记$T(k)$表示包含$k$个顶点的树的数目，通过prufer编码我们知道$T(k)=k^{k-2}$。令$F(k)$表示拥有$k$个顶点的森林数目。很显然有

$$\begin{aligned} F(k)=&\sum_{i=1}^k F(k-i)T(i){k-1\choose i-1}\\ =& (k-1)!\sum_{i=1}^k \frac{F(k-i)}{(k-i)!}\frac{T(i)}{(i-1)!} \end{aligned}$$

可以发现这是一个卷积递推的一个DP公式，我们可以用分治+FFT将时间复杂度优化到$O(n(\log_2n)^2)$。

函数图

考虑任意函数$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\pmod 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)$。

不相交路径计数

要解决不相交路径计数，需要用到一个神器：Lindström–Gessel–Viennot引理，不懂的先自行了解。

题目1：给定一个$n\times m$网格图，其中单元格中或者为空白，或者为一个障碍物，所有合法路径都不允许经过存在障碍物的单元格。记$P$表示所有从左上角到右下角的所有合法路径的集合，考虑存在多少个二元组$(p_1,p_2)$，满足$p_1,p_2\in P$，且两条路径仅经过两个公共网格（起点和终点），结果模素数$p$。其中$2\leq n,m\leq 1000$。

我们实际上要统计从起点$A=((2,1),(1,2))$到终点$B=((n,m-1),(n-1,m))$的不相交路径数，这时候仅可能存在的置换为$\pi$，因此我们通过Lindström–Gessel–Viennot引理可以直接计算出不相交路径数。

序列计数

相邻不同序列

题目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$序列，其中每个元素为$1$到$m$，且数值$i$的出现次数$c_i$满足$c_i=b_i\pmod 2$。其中$1\leq m\leq 5000$，$1\leq n\leq 10^9$。

我们要求的结果为：

$$\sum_{c_1+\ldots+c_m=n\land c_i=b_i\pmod 2}\frac{n!}{c_1!\ldots c_m!}$$

我们记

$$f_n(x_1,\ldots,x_m)=\sum_{c_1+\ldots+c_m=n\land c_i=b_i\pmod 2}\frac{n!}{c_1!\ldots c_m!}x_1^{c_1}\ldots x_m^{c_m}$$

那么我们要求的结果为$f(1,\ldots,1)$。记

$$\begin{aligned} g(x)&=\sum_{n\geq 0}\frac{f_n(x_1,\ldots,x_m)}{n!}x^n\\ &=\sum_{n\geq 0}\sum_{c_1+\ldots+c_m=n\land c_i=b_i\pmod 2}\frac{(x_1x)^{c_1}}{c_1!}\ldots \frac{(x_mx)^{c_m}}{c_m!}\\ &=\prod_{i=1}^m\sum_{c_i=b_i\pmod 2}\frac{(x_ix)^{c_i}}{c_i!}\\ &=\prod_{i=1}^m\frac{\exp(x_ix)+(-1)^{b_i}\exp(-x_ix)}{2}\\ \end{aligned}$$

把$x_1=x_2=\ldots=x_m=1$代入得到：

$$g(x)=\prod_{i=1}^m\frac{\exp(x)+(-1)^{b_i}\exp(-x)}{2}\\$$

上面的公式可以视作$e^x$的多项式，即$g(x)=\sum_{i=-m}^m d_i \exp(ix)$。计算出所有系数的时间复杂度为$O(m^2)$。

之后我们计算的$f_n(1,\ldots,1)$实际上是$\frac{x^n}{n!}$的系数。考虑到$\exp(x)=\sum_{i=0}\frac{x^i}{i!}$，因此我们的答案为：

$$\sum_{i=-m}^md_i\times i^n$$

总的时间复杂度为$O(m^2+m\log_2n)$。

题目2：提供一个$R$面筛子，其中有$a_i$面写着数字$i$，其中$1\leq i\leq m$。维护一个序列，初始为空，重复下面操作，直到序列长度达到$n$。

• 投掷筛子，将筛子上的数字追加到序列尾部。

检查序列中第$i$个元素出现的次数$c_i$，是否满足$c_i=b_i$。如果满足，则称序列是好的。问序列是好的的概率。其中$1\leq m\leq R\leq 5000$，且$1\leq n\leq 10^9$。

这题和题目1实际上是相同的，只不过我们要求的是$\frac{1}{R^n}f_n(a_1,a_2,\ldots,a_m)$。时间复杂度为$O(R^2+R\log_2n)$。

题目3：提供一个$R$面筛子，其中有$a_i$面写着数字$i$，其中$1\leq i\leq m$。维护一个序列，初始为空，重复下面操作，直到序列长度达到$n$。

• 投掷筛子，将筛子上的数字追加到序列尾部。

检查序列中第$i$个元素出现的次数$c_i$，是否满足$c_i=b_i$。如果满足，则称序列是好的。如果序列不是好的，则清空序列，并重新调用流程，直到得到好序列为止。记$w_i$表示数字$i$的权重，定义序列的权重为$\sum_{i=1}^mc_iw_i$，要求计算序列权重的数学期望。其中$1\leq m\leq R\leq 5000$，且$1\leq n\leq 10^9$。

提供一道题目。

得到的好序列的方案数为$f_n(a_1,\ldots,a_n)$。

记

$$h_n(x_1,\ldots,x_m)=\sum_{c_1+\ldots+c_m=n\land c_i=b_i\pmod 2}\frac{n!}{c_1!\ldots c_m!}x_1^{c_1w_1}a_1^{c_1}\ldots x_m^{c_mw_m}a_m^{c_m}$$

可以发现我们的好序列的所有方案总权为

$$(\sum_{i=1}^mx_i\frac{\partial h_n}{\partial x_m})(1,\ldots,1)$$

我们用类似的方式得到：

$$\begin{aligned} p(x)&=\sum_{n\geq 0}\frac{h_n(x_1,\ldots,x_m)}{n!}x^n\\ &=\prod_{i=1}^n\frac{\exp(a_ix_i^{w_i}x)+(-1)^{b_i}\exp(-a_ix_i^{w_i}x)}{2} \end{aligned}$$

之后我们求$\sum_{i=1}^mx_i\frac{\partial p_n}{\partial x_m}$即可。这个东西可以通过动态规划计算，记$dp(i,j,0/1)$表示前$i$个多项式，$\exp(jx)$的系数，第三个参数指定是否已经对一个变量进行偏微分了。这个部分可以$O(R^2)$计算。

之后总权除上总方案数得到平均数即可。总的时间复杂度为$O(R^2+R\log_2m)$。

赋值方案

题目1：计算有多少个长度为$n$的序列$x_1,\ldots,x_n$，满足$0\leq x_i< m$，且$\sum_{i=1}^n x_i\leq S$。其中$1\leq n,m,S\leq 10^6$，结果对素数取模。

我们可以用容斥来计数，定义$A_i$表示$x_i>S$这个条件，那么我们要求的就是$|\bigcap_{i=1}^n \overline{A_i}|$。通过容斥可以展开为

$$\begin{aligned} &\sum_{I\subseteq N} (-1)^{|I|}\bigcap_{i\in I}A_i\\ =&\sum_{I\subseteq N} (-1)^{|I|}p(S-m|I|,n) \end{aligned}$$

其中$p(i,j)$表示存在多少种方案将$i$划分为$j$个带编号的未知数的和，其等价于${i+j-1\choose j-1}$。

可以发现上面的公式中仅$I$的大小发挥作用，因此我们可以转而枚举$I$的大小。

$$\sum_{0\leq i\leq n} (-1)^{i}{n\choose i}p(S-mi,n)$$

这样我们就得到了$O(n+S+m)$的做法。

题目2：给定序列$a_1,\ldots,a_n$，计算有多少长度为$n$的序列$b_1,\ldots,b_n$，满足$b_i\geq 0$且$\sum_{i=1}^na_ib_i=S$。其中$1\leq a_i,S$，且$n,S,\sum_{i=1}^n a_n\leq 10^5$，结果对素数取模。

我们要求的是$g=f_1\cdots f_n$的$x^S$项的系数，其中$f_i(x)=\sum_{j=0}^{\infty}(x^{a_i})^j=\frac{1}{1-x^{a_i}}$。

计算乘积得到$g(x)=\frac{1}{\prod_{i=1}^n(1-x^{a_i})}$。我们只需要通过分治算法求出分母，之后对分母取逆即可。时间复杂度为$O(m\log_2m\log_2n)$，这里$m=\sum_{i=1}^na_i$。

题目3：给定序列$a_1,\ldots,a_n$，计算有多少长度为$n$的序列$b_1,\ldots,b_n$，满足$b_i\geq 0$且$\sum_{i=1}^na_ib_i=S$。其中$1\leq a_i,n\leq 10$，且$1\leq S\leq 10^{18}$，结果对素数取模。

在$S$较小的时候，容易想到用DP求解，其中$dp(i,j)$表示仅考虑$x_1,\ldots,x_j$，存在多少方案满足$\sum_{t=1}^ja_tx_t=i$。可以发现要计算$dp(i,?)$，只需要知道$dp(i-10,?),\ldots,dp(i-1,?)$即可，并且它们的转移关系是线性的。其中总共涉及最多$10n$个状态，因此我们只需要维护一个长度为$10n$的向量$v_0$，以及转移关系$A$。答案为$v_S=A^Sv_0$。

这里可以采用矩阵快速幂进行计算，时间复杂度为$O((10n)^3\log_2m)$。

0和计数

题目1：给定$n$个$1$和$-1$，要求将它们组成一个长度为$2n$的序列，且其中恰好有$k$个非空连续子序列，和正好为$0$。要求统计组成的不同序列数目。其中$1\leq n\leq 30$。

提供一道题目。

记得到的序列为$a_1,\ldots,a_{2n}$，而令$s_i=\sum_{j=1}^ia_j$。得到一个新的序列$s_0,s_1,\ldots,s_{2n}$。那么我们实际上是要找到有多少$i<j$，满足$s_i=s_j$。如果存在$t$个数的值均为$x$，那么它对结果的贡献为$t\choose 2$。

现在考虑$dp(size,cc,pair)$表示仅考虑长度为$size$的序列，其中有$cc$个连通块，共存在$pair$对下标拥有相同值。

我们考虑状态$(size,cc,pair)$的转移，下一层如果新增$x$个元素，那么很显然需要$x\geq cc+1$，这时候所有连通块都合并为一块。之后考虑另外$x-(cc+1)$个新的元素插入带来的变化，每次插入一个新元素，都会使得连通块增加$1$。因此新的转移状态为$(size+x,x-(cc+1)+1,pair+{x\choose 2})$，而转移的权重为${x-1\choose cc-2}$（共$cc+1$个槽，即$y_1+\ldots+y_{cc+1}=x$且$y_i\geq 1$）。

注意我们目前只算了$0$以及更上面的层次，而对于下层，$(size,cc,pair)$适配的状态为$(2n+1-size,cc-1,k-pair)$。

总的计算时间复杂度为$O(n^5)$，空间复杂度为$O(n^4)$。

置换群下去重计数

这类型的问题一般需要用到burnside和polya定理，请提前了解。

题目1：给一个六面的筛子，要求在每个筛子面上设置一个非负数，第$i$面上写的为$x_i$，要求满足$\sum_{i=1}^6x_i=S$。两种方案相同，当且仅当可以通过旋转筛子得到相同的结果。要求计算方案数。其中$0\leq S\leq 10^{18}$，结果对素数取模。

提供一道题目。

根据burnside定理可知，我们要计算的是

$$\frac{1}{|G|}\sum_{f\in G}|\left\{c\mid f(c)=c\right\}|$$

其中$G$为旋转操作带来的置换群，其中实际上只有$24$个元素。因此我们将问题转换为存在多少个$c$，在$f$作用下结果不变。这等价于计算$\sum_{i}a_ib_i=S$，这个我们可以通过矩阵快速幂求解，总的时间复杂度为$O(24\times 6^6\log_2m)$。

带比较计数

题目1：给定非负整数$k$，以及两个长度为$n$的序列$a_1,\ldots,a_n$和$b_1,\ldots,b_n$。其中$a_1,\ldots,a_n,b_1,\ldots,b_n$是$1,\ldots,2n$的一个置换。且要求满足$b_i< \max_{1\leq j\leq \min(n,i+k)} a_j$。其中$0\leq k < n\leq 10^6$。统计可能的方案数，并对素数取模。

提供一道题目。

由定义可以很容易得出$2n\in a$。

我们考虑考虑所有排列等概率出现的情况下条件满足的概率，之后乘上$(2n)!$即是答案。

记$x_i$表示$b_i< \max_{1\leq j\leq \min(n,i+k)} a_j$成立的集合，那么我们要求的是$\mathrm{Pr}(x_1\cap x_2\cap \ldots\cap x_n)=\mathrm{Pr}(x_1)\mathrm{Pr}(x_2\mid x_1)\cdots \mathrm{Pr}(x_n\mid x_1\cap \ldots \cap x_{n-1})$。注意这里我们不需要考虑$2n\in a$这个条件，因为当所有情况都满足的时候，这个条件是可以被推出的。

考虑$\mathrm{Pr}(x_i\mid \bigcap_{j=1}^{i-1}x_j)$，其不成立当且仅当$b_i$是$b_1,\ldots,b_i,a_1,\ldots,a_{\min(n,i+k)}$中的最大值，考虑到是随机排列，因此不成立的概率为$\frac{1}{i+\min(n,i+k)}$，而成立的概率为$1-\frac{1}{i+\min(n,i+k)}$。

因此我们可以得出答案为$\prod_{i=1}^n(1-\frac{1}{i+\min(n,i+k)})=\prod_{i=1}^{n-k} \frac{2i+k-1}{2i+k}\prod_{i=n-k+1}^n \frac{i+n-1}{i+n}$。

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

不允许相邻计数

题目1：回答$q$个请求，每个请求给定$n$和$k$和$d$，要求统计有多少个长度为$n$的01序列，其中元素和为$k$，且任意连续的$d$个元素之和都不能超过$1$。其中$1\leq q,n,k,d\leq 10^6$。

记$f(n,k,d)$为答案。

可以把每个$1$理解为占用$d$个位置的块，之后我们把$n$延长$d-1$（允许我们将第$i$个元素设置为$1$），现在的问题变成了，有$n+d-1-dk$和$0$块和$k$个$1$块，有多少种组合方式，很显然答案为$f(n,k,d)={n+d-1-dk+k\choose k}$。

预处理后，每个请求都可以$O(1)$回答。

题目2：回答$q$个请求，每个请求给定$n$和$k$和$d$，要求统计有多少个长度为$n$的01环（第一个元素和最后一个元素相邻），其中元素和为$k$，且任意连续的$d$个元素之和都不能超过$1$。其中$1\leq q,n,k,d\leq 10^6$。

类似题目1，可以发现第1到第d个元素中最多有一个$1$，分两种情况处理：

• 1到d中有一个1，这时候方案数为$d\times f(n-(2d-1),k-1,d)$。
• 1到d中没有1，这时候方案数为$f(n-d,k,d)$。

因此可以发现答案为$g(n,k,d)=d\times f(n-(2d-1),k-1,d)+f(n-d,k,d)$的01环（第一个元素和最后一个元素相邻），其中元素和为$k$，且任意连续的$d$个元素之和都不能超过$1$。

题目3：给定一个长度为$n$的序列$a_1,\ldots,a_n$，之后考虑所有可能的长度为$n$的01环$b$（第一个元素和最后一个元素相邻），其中元素和为$k$，且任意连续的$d$个元素之和都不能超过$1$。记$b$的权重为$\sum_{i=1}^na_ib_i$。要求计算所有满足条件的01环的权重之和。其中$1\leq n,k,d\leq 10^6$。

我们记$c_i$表示第$i$个元素在所有满足条件的01环中为1的次数。很显然有$c_1=c_2=\ldots=c_n$，而所有方案的总和为$k g(n,k,d)$。因此$c_i=k g(n,k,d)/n$。答案为$\sum_{i=1}^n c_ia_i$。

题目4：给定一个长度为$n$的序列$a_1,\ldots,a_n$，之后考虑所有可能的长度为$n$的01序列$b$，其中元素和为$k$，且任意连续的$2$个元素之和都不能超过$1$。记$b$的权重为$\sum_{i=1}^na_ib_i$。要求计算所有满足条件的01序列的权重之和。其中$1\leq n,k\leq 10^6$。

提供一道题目。

类似题目3，同样定义$c_i$。

我们可以把问题转换成01环版本来求解。考虑所有满足01环的同时可以展开为一个01序列，而01序列的不一定能展开为01环，分两种情况考虑：

• 能转换为01环的，共有$g(n,k,2)$种，我们将贡献$c_1,\ldots, c_n$共$kg(n,k,2)/n$。
• 另外一种情况，这时候第1个元素和第n个元素都被设置为1。这时候对$c_1$和$c_n$的贡献均为$f(n-4,k-2,2)$。而对于$c_2,\ldots,c_{n-1}$的贡献，我们可以发现这时候问题变成一个长度为$n-4$的01序列，其中元素和为$k-2$，且任意连续的$2$个元素之和都不能超过$1$。可以注意到问题的规模缩小了，我们可以递归解决问题。

每次递归流程的时间复杂度为$O(1)$，递归的深度为$n/2$，因此时间复杂度为$O(n)$。

题目4：给定一个长度为$n$的序列$a_1,\ldots,a_n$，之后考虑所有可能的长度为$n$的01序列$b$，其中元素和为$k$，且任意连续的$d$个元素之和都不能超过$1$。记$b$的权重为$\sum_{i=1}^na_ib_i$。要求计算所有满足条件的01序列的权重之和。其中$1\leq n,k,d \leq 10^6$。

提供一道题目。

不会。

包含特定子串的字符串数统计

题目1：提供大小为$C$的字符集，提供一个长度为$n$的串$T$，统计有多少长度为$m$的字符串$S$，使得$S$中含有$T$。

这里讲多种做法。

一种比较简单的方是通过统计有多少不含$T$的串。简单的方法是用AC自动机，定义$dp(i,j)$表示构建长度为$i$的串，状态为$j$的方案数。这给出了$O(Cnm)$的时间复杂度。

可以发现上面的转移是线性的，因此我们实际上可以做到$O(Cn^2+n\log_2m)$，或者$O(Cn+n^3\log_2m)$，取决于你使用BM递推还是快速矩阵幂。

但是上面几种方法，在$n=O(m)$的情况下，都会达到$O(n^2)$的级别或更高。

其实还有$O(m\log_2n)$的做法。具体思路就是用kmp求出所有的border。之后考虑用容斥来找有多少字符串$S$包含$T$。具体的方案是令$dp(i,k)$表示$T$在$S$的上一次出现的位置是$i$，$T$的出现次数的为$k$。考虑用的是容斥，因此只需要知道出现次数的奇偶性即可，因此$k$只需要取值$0,1$。

但是计算dp的时候，$i$不一定会转移到$i+n$或更后面的位置，因为$T$连续两次出现的位置可能有重叠部分。我们需要用border来处理这个问题。用kmp求出所有border。这样就可以给出时间复杂度为$O(nm)$。

当然这个距离我们要的结果还有点远。由于border的关系会形成$O(\log_2n)$个等差数列，因此我们实际上可以仅考虑这$O(\log_2n)$个等差数列，每个状态的贡献都是某个区间，并且步长是固定的，通过一些前缀和技术可以快速计算转移。时间复杂度为$O(m\log_2n)$。

带禁止的置换计数

题目1：给定$n$的一个置换$a$，计算存在多少$n$的置换$p$，要求$\forall i$，$p_i\neq a_i$。结果模素数输出。

这个问题是容斥的经典应用。记$A_i$表示所有置换集合$p$，满足$p_i\neq a_i$。结果为：

$$\begin{aligned} &|\bigcap_{i=1}^nA_i|\\ =& |U|-|\bigcup_{i=1}^n\overline{A_i}|\\ =& \sum_{I\subseteq N}(-1)^{|I|} \bigcap_{i\in I}A_i\\ =& \sum_{I\subseteq N}(-1)^{|I|} (n-|I|)!\\ =& \sum_{i=0}^n (-1)^{i} (n-i)! {n\choose i}\\ =& n! \sum_{i=0}^n (-1)^{i} \frac{1}{i!} \end{aligned}$$

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

题目2：给定$n$的一个置换$a$，$b$，计算存在多少$n$的置换$p$，要求$\forall i$，$p_i\neq a_i$且$p_i\neq b_i$。结果模素数输出。

提供一道题目。

我们依旧可以通过容斥来计算结果。我们可以DP计算违背的约束的数量，以及可行解数目。但是我们需要保证DP的过程中不会选择重复值，这个是关键，否则就不是一个有效的置换。下面我们讨论如何避免这个问题。

我们考虑建立$n$个顶点，之后对于$i=1..n$，加入边$(p_i,q_i)$。可以发现一个$p$的位置和一条边有关。同时可以发现每个顶点的度数均为$2$，因此得到的图是若干个简单环。

可以发现每个环我们可以独立统计，考虑一个长度为$k$的环，顺时针进行编号，我们可以记录$dp(i,j,k,t)$表示考虑前$i$个元素，$j$表示第一个元素是否被选择为逆时针元素，$k$表示第$i$个元素是否被选择为顺时针元素，总共有$k$个元素违背约束。算法的时间复杂度为$O(k^2)$。

多个环的合并类似于背包合并。总的时间复杂度为$O(n^2)$。

本质不同非空子串

题目1：给定一个序列$a_1,\ldots,a_n$，问有多少本质不同的子串。

后缀自动机或者后缀数组可以做到$O(n)$。

题目2：给定一个序列$a_1,\ldots,a_n$，之后回答$q$个请求，每个请求给定$l,r$，要求计算$a_l,a_{l+1},\ldots,a_r$中有多少本质不同的子序列数目。

后缀自动机上维护线段树。如果不允许离线，就是用持久化线段树，否则使用差分技术。时间复杂度为$O((n\log_2n+q)\log_2n)$，空间复杂度为$O(n\log_2n\log_2n+q)$或$O(n\log_2n+q)$。

本质不同子序列

题目1：给定一个序列$a_1,\ldots,a_n$。问有多少本质不同的非空子序列。结果对素数取模。

首先我们可以进行离散化。之后认为$a_i\leq n$。难点在于唯一性。

我们可以用贪心法保证序列的唯一性。具体就是如果我们目前的子序列尾部为第$i$个字符，且$a_j$不属于$a_{i+1},\ldots,a_{j-1}$，那么子序列的下一个结尾可能为$a_j$。这样做的时间复杂度为$O(n^2)$。

我们可以逆着做，具体就是从后向前DP，记$x_i$表示以第$i$个字符作为开始的本质不同子序列数目。我们可以从后向前计算$x_i$，同时维护$y_j$，以字符$j$开始的本质不同子序列数。计算$x_i$的时候有$x_i=1+\sum y_{a_i}$，之后将$y_{a_i}$更新为$x_i$，这样就可以做到$O(n)$。

题目2：给定一个序列$a_1,\ldots,a_n$。之后回答$q$个请求，每个请求给定$l,r$，问$a_l,a_{l+1},\ldots,a_r$有多少本质不同的非空子序列。结果对素数取模。

提供一道题目。

第一种做法是每次重新计算，时间复杂度为$O(nq)$。

下面讲一种$O(r^2(n+q))$的做法，$r$表示字符集大小。首先需要理解题目1中$O(n)$做法的转移，仔细观察会发现它每次转移实际上都是一个线性变换，并且是一个可逆的线性变换。这意味着我们可以预处理线性变换的后缀和$A$和后缀逆$B$。那么$l,r$之间的转移实际上等于$A_lB^{r+1}$，于是乎我们可以$O(r^3)$回答每个请求，但是注意到如果我们按照$A_l(B^{r+1}v)$的顺序计算，则每个请求可以$O(r^2)$回答。

对于预处理后缀和和后缀逆，这需要$O(r^2n)$的空间复杂度。而对于时间复杂度，看上去是$O(r^3n)$，但是可以发现每步操作对应的线性变换和逆变换，都是稀疏矩阵，其中只有$O(r)$个非空元素。因此我们可以把时间复杂度优化到$O(r^2n)$。总的时间复杂度为$O(r^2(n+q))$。

集合计数

分组问题

题目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：给定包含$n$个元素的集合$S$，要求计算存在多少个$S$的子集族$A$，满足每个元素都出现在至少两个$A$的元素中。结果对素数$p$取模。

提供一道题目。

令$X_i$表示所有满足元素$i$出现在最多一个元素中的子集族组成的集合。那么我们实际上要统计$|\bigcap_{i=1}^n \overline{X_i}|$。我们可以用容斥统计这个数量：

$$\begin{aligned} |\bigcap_{i=1}^n \overline{X_i}|&=|S|-|\bigcup_{i=1}^nX_i|\\ &=\sum_{I\subseteq N}(-1)^{|I|}|\bigcap_{i\in I}X_i| \end{aligned}$$

其中

$$\begin{aligned} |\bigcap_{i\in I}X_i|&=\sum_{k=0}^{|I|}{|I|\choose k}\sum_{r=0}^{|I|}\begin{Bmatrix}k\\r\end{Bmatrix}2^{r(n-|I|)}\sum_{m=0}^{2^{n-|I|}}{2^{n-|I|}\choose m}\\ &=2^{2^{n-|I|}}\sum_{r=0}^{|I|}2^{r(n-|I|)}\sum_{k=0}^{|I|}{|I|\choose k}\begin{Bmatrix}k\\r\end{Bmatrix}\\ &=2^{2^{n-|I|}}\sum_{r=0}^{|I|}2^{r(n-|I|)}\big ((r+1)\begin{Bmatrix}|I|\\r+1\end{Bmatrix}+\begin{Bmatrix}|I|\\r\end{Bmatrix}\big) \end{aligned}$$

合并两个公式得到：

$$|\bigcap_{i=1}^n \overline{X_i}|=\sum_{i=0}^n(-1)^{i}{n\choose i}2^{2^{n-i}}\sum_{r=0}^{i}2^{r(n-i)}\big ((r+1)\begin{Bmatrix}i\\r+1\end{Bmatrix}+\begin{Bmatrix}i\\r\end{Bmatrix}\big)$$

上面的公式通过预处理，可以$O(\sqrt{p}+n^2)$计算得到。

题目2：考虑给定$n$个元素$a_1,\ldots,a_n$，记$S=\sum_{i=1}^na_i$。要求计算其中有多少个子序列（不要求连续）的元素和正好为$0,1,2,\ldots,S$。其中$1\leq a_i$且$S\leq 10^5$。结果对素数$M$取模。

提供一道题目。

考虑它的生成函数。

$$\begin{aligned} F(x)&=\sum_{k=0}^Sx^k\sum_{0\leq c_1,c_2,\ldots,c_n\leq 1\land \sum_{i=1}^nc_ia_i=k}1 \\ &=\sum_{k=0}^S\sum_{0\leq c_1,c_2,\ldots,c_n\leq 1\land \sum_{i=1}^nc_ia_i=k}x^{c_1a_1}x^{c_2a_2}\cdots x^{c_na_n}\\ &=\sum_{0\leq c_1,c_2,\ldots,c_n\leq 1}x^{c_1a_1}x^{c_2a_2}\cdots x^{c_na_n}\\ &=\prod_{i=1}^n x^{a_i}+1 \end{aligned}$$

之后分治+FFT即可，时间复杂度为$O(S\log_2S\log_2n)$。

实际上我们可以把结果优化到$O(n+S\log_2S)$。具体的想法来自与A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum这篇论文。

我们可以先记$G(x)=\ln F(x)$。那么很显然有$F(x)=\exp(G(x))$。之后我们只需要能快速求出$G(x)$即可。

首先已知$\ln(1+x)=\sum_{i=1}^{\infty}\frac{(-1)^{i-1}x^i}{i}$

$$\begin{aligned} G(x)&=\ln \prod_{i=1}^n x^{a_i}+1\\ &=\sum_{i=1}^n \ln (x^{a_i}+1)\\ &=\sum_{i=1}^n \sum_{j=1}^{\infty} \frac{(-1)^{j-1}x^{j\cdot a_i}}{j} \end{aligned}$$

由于$S$是有限的，我们只需要考虑$G(x)$的前$S+1$项的即可。记$c(i)$表示$i$在$a$中出现的次数。那么公式可以简化为：

$$\begin{aligned} \sum_{i=1}^S \sum_{j=1}^{\lfloor S/i \rfloor} \frac{c(i)\cdot (-1)^{j-1}x^{j\cdot a_i}}{j} \end{aligned}$$

上面的过程可以$O(n+S\ln S)$处理，之后的$\exp(G(x))$可以$O(S\ln S)$计算，总的时间复杂度为$O(n+S\ln S)$。

题目3：给定$n$种不同颜色，第$i$种颜色共有$a_i$个球，记$m=\sum_{i=0}^na_i$。现在问对于$q=1,\ldots,m$，有多少种不同的大小为$q$的多重集合。结果对素数$p$取模。其中$1\leq n\leq m\leq 3\times 10^5$，且$1\leq a_i$。

我们要求的是$f_1,\ldots,f_n$的乘积，其中$f_i=\sum_{i=0}^{a_i}x^i$。简单的可以推出$f_i=\frac{x^{a_i+1}-1}{x-1}$。我们可以用题目2中提到的方法将所有生成函数的分子和分母独立乘起来，之后取逆分母，做多项式卷积即可。时间复杂度为$O((n+m)\log_2(n+m))$。

多重集合计数

题目1：考虑所有仅包含非负整数的多重集合，有多少大小为$k$的多重集合，它的和为$n$，记结果为$f(n,k)$。给定$N$，对于所有$1\leq n\leq N$，$1\leq k\leq N$，输出$f(n,k)$。其中$1\leq N\leq 5000$。

提供一道题目。

我们可以用动态规划解决这个问题。用一般的动态规划的话时间复杂度会恶化到$O(N^3)$。这里我们可以换一个动态规划的思路。

问题等价于存在多少子序列$x_1,\ldots,x_k$，满足$x_1\leq x_2\leq \ldots \leq x_k$，且$\sum_{i=1}^nx_i=n$。

上面提到的问题依旧不好解决。我们可以考虑$x_i$序列的差分形式$d_1,\ldots,d_k$，其中$d_i=x_i-x_{i-1}$（这里认为$x_0=0$）。可以发现$x_i$每增加$1$，整体和会增加$k-i$。所以这提供了一个dp的思路，令$dp(i,j)$表示仅考虑$d_1,\ldots, d_i$，其贡献和为$j$的方案数。但是这里会发现有一个我们不想要的变量$n$存在，这使得这个dp方案的时间复杂度同样为$O(N^3)$。一个非常简单的思路是，我们可以认为$dp(i,j)$表示仅考虑最后的$i$个差分变量，它们的贡献和为$j$的方案数，这种情况下可以发现$n$不见了，因为最后第$i$个差分变量每增加一，对结果的贡献始终是$i$。

这样我们可以实现$O(N^2)$的一个算法。$f(i,j)=dp(j,i)$。

网格计数

子矩形计数

题目1：给定一个大小为$n\times m$的01网格，要求计算有多少个$k$个位置形成的集合，满足每个位置中写的数字都是$1$，且记$l$为最左的位置的横坐标，$r$为最右的位置的横坐标，$b$为最下的位置的纵坐标，$t$为最上的位置的纵坐标，满足$r-l<w$且$t-b<h$。其中$1\leq w,h,n,m\leq 10^3$。

我们可以枚举$l$和$b$，之后统计有多少$k$位置集合。我们只需要考虑以$(l,b)$为左下角的大小为$w\times h$的矩形中的数值和$S$，那么答案为${S \choose k}$。但是这里存在重复统计，因此我们必须通过容斥计算，记$S_1$表示以$(l,b)$为左下角的大小为$w\times h$的矩形中的数值和，$S_2$表示以$(l+1,b)$为左下角的大小为$w-1\times h$的矩形中的数值和，$S_3$表示以$(l,b+1)$为左下角的大小为$w\times h-1$的矩形中的数值和，$S_4$表示以$(l+1,b+1)$为左下角的大小为$w-1\times h-1$的矩形中的数值和。那么答案为$S_1-S_2-S_3+S_4$。

时间复杂度为$O(4nm)$。

覆盖问题

题目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\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=0\rightarrow b_1}\sum_{y=0\rightarrow d}\sum_{z=0\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)$。

模运算

题目1：计算$\sum_{i=0}^n[a+\lfloor \frac{i}{b} \rfloor = c+\lfloor \frac{i}{d} \rfloor]$，其中$1\leq n\leq 10^9$，且$b,d>0$。

提供一道题目。

不失一般性可以假设$a\leq c$。如果$b>c$，那么很显然答案一定是$0$。如果$a=c$且$b=c$，那么答案很显然是$n+1$。如果$a<c$且$b=c$，那么答案同样是$0$。

令$f(i)=a+\lfloor \frac{i}{b} \rfloor$，$g(i)=c+\lfloor \frac{i}{d} \rfloor$。可以发现$f$的增长速度快于$g$，我们可以找到最小的$x$，满足$f(x)=g(x)$。可以发现此时一定有$b|x$，我们可以借此对$x$二分来找到这个位置。同理我们找到最小的$y$，满足$f(y)=g(y)+1$，以及最小的$z$满足$f(z)=g(z)+2$。很显然有$x<y<z$成立。

下面我们赖考虑如何计算上面的公式。$f(i)=g(i)$成立仅可能当$x\leq i<z$，且此时一定有且对于$x\leq i<y$，均有$-1\leq f(i)-g(i)\leq 0$，而对于$y\leq i<z$，有$0\leq f(i)-g(i)\leq 1$。

要统计有多少位置$f(i)=g(i)$，等价于统计有多少位置$f(i)-g(i)=0$。由于当$x\leq i<y$的时候，$g(i)-f(i)$仅可能取值$1$和$0$，每个$1$代表一个不匹配位置。因此我们可以得到匹配位置数为$(y-x)-(\sum_{i=x}^{y-1}g(i)-\sum_{i=x}^{y-1}f(i))$，而由于$\sum_{i=x}^{y-1}g(i)$和$\sum_{i=x}^{y-1}f(i)$均可以通过类欧几里德函数进行快速计算，因此我们可以$O(\log_2M)$找到结果，其中$M$表示精度。对于$y\leq i<z$的时候同理。

总的时间复杂度为$O(\log_2M)$。

题目2：给定$n$个互不相同的正整数$a_1,\ldots,a_n$。记$f(k)=\sum_{1\leq i<k} a_i\pmod{a_k}+a_k\pmod{a_i}$。要求输出$f(1),\ldots,f(n)$。其中$1\leq a_i,n \leq 10^6$。

提供一道题目。

首先我们要知道取模的定义是啥，$x\pmod y=x-y\times \lfloor\frac{x}{y}\rfloor$，要解决这个问题我们需要用到这个公式。

分两部分处理，第一部分是处理$\sum_{1\leq i<k} a_i\pmod{a_k}$部分。对于$xa_k\leq a_i<(x+1)a_k$，它对我们结果的贡献为$a_i-xa_k$。因此我们需要知道在每个区间$[xa_k,(x+1)a_k)$，有多少个$a_i$出现，换言之我们要有能力查询区间和。同时我们在处理完$a_k$后，还需要把$a_k$的信息更新上去，换言之需要支持更新。我们可以直接用树状数组来维护这些信息。由于每个数都不同，而所有数的倍数是$O(10^6\log_2 10^6)$级别的。因此这部分的时间复杂度为$O(10^6(\log_210^6)^2)$。

再考虑第二部分，$\sum_{1\leq i<k} a_k\pmod{a_i}$。继续用上面的公式可以发现对于$xa_i\leq a_k<(x+1)a_i$，它对我们结果的贡献为$a_k-xa_i$。我们可以同时维护一个数据结构，在处理完一个数$a_k$后，将它的所有倍数区间信息更新到这个结构上。而查询只需要单点查询即可。这也可以通过后缀数组做到。这部分的时间复杂度为$O(10^6(\log_210^6)^2)$。

总的时间复杂度为$O(10^6(\log_210^6)^2)$。

几何计数

矩形计数

题目1：提供$n$个不同的二维点$p_1,p_2,\ldots,p_n$，要求有多少个下标$a<b<c<d$，满足$p_a,p_b,p_c,p_d$作为四个点可以确定一个正方形，且正方形四边与坐标轴平行。其中$1\leq n\leq 10^5$。

我们先将点分成两类，如果一个点，与它拥有相同横坐标的点超过$\sqrt{n}$个，那么记作二类点，否则为一类点。之后将一类点按照横坐标分组，二类点按照纵坐标分组。可以发现得到的分组的大小都不会超过$\sqrt{n}$。

之后我们可以暴力枚举同一个分组中的两个点，另外两个点的位置仅两种选择，我们直接查询这两个点是否出现即可。这里可以用哈希表来存储点。

但是如果四个点都是同一类点，就会出现重复统计的情况，这里可以简单的在每次考虑完某个分组之后，就将分组中的点从哈希表中全部删除即可。

总的时间复杂度为$O(n\sqrt{n})$，当然你需要一个足够快的哈希表才行。事实上我们每次暴力枚举最多找到一个合法的正方形，而枚举的上限为$O(n\sqrt{n})$，因此可以证明这也是正方形数的一个上限。

题目2：提供$n$个不同的二维点$p_1,p_2,\ldots,p_n$，$p_i=(x_i,y_i)$。要求判断是否存在一组下标$a<b<c<d$，满足$p_a,p_b,p_c,p_d$作为四个点可以确定一个矩形，且矩形四边与坐标轴平行。其中$1\leq n\leq 10^6$且$0\leq x_i,y_i\leq 3000$，且所有点两两不同。

我们可以将所有点按照$x$坐标分组，之后暴力枚举两组来判断每组是否都存在相同的两个$y$坐标点。这个过程时间复杂度为$O(3000^3)$。我们可以用bitset优化这个过程，优化后的时间复杂度为$(3000^3/32)$。

但是由于我们只需要判断是否存在至少一组下标，因此我们可以枚举每一列中的所有点对，考虑点对为$(x_i,y_i)$和$(x_j,y_j)$，我们将$(y_i,y_j)$状态记录下来。如果已经记录过相同的状态，我们就可以报告找到，否则标记这个状态出现过了。可以发现每个状态最多被标记一次，而总的状态数仅为$O(3000^2)$，因此总的时间复杂度为$O(3000^2+n)$。

题目3：考虑在二维坐标系以$(0,0)$，$(w,0)$，$(w,h)$，$(0,h)$确定的矩形区域内，选择四个不同格点（横坐标和纵坐标均为整数），形成一个矩形的方案数。注意这里不要求矩形的边界和坐标轴平行。其中$1\leq w,h\leq 10^3$。

提供一道题目。

我的做法和标解不同，拥有更好的时间复杂度。

与坐标轴平行的非常好统计，任意选两行两列，取它们的交点即可。这部分的贡献为${w+1\choose 2}{h+1\choose 2}$。

下面说一下怎么统计与坐标轴不平行的矩形数。考虑任意一个不平行矩形，我们找到面积最小的包含它的平行的矩形，这时候矩形的左下角和右上角均为边长分别为$a,b$的三角形，而左上角和右下角均为边长分别为$c,d$的三角形。且满足$\frac{a}{b}=\frac{c}{d}$，换言之$ad=bc$，且外部的平行的矩形的大小为$(a+d)\times (b+c)$。

上面我们大致刻画了一下一个非平行矩形的特性。实际上如果我们能找到一组$ad=bc$，那么可以唯一确定一个平行矩形，以及它内部包含的一个非平行矩形。这样的平行矩形在我们的允许范围内可以出现$(h-a-d+1)(w-b-c+1)$次。稍微修改一下公式：

$$\begin{aligned} &\sum_{1\leq a,b,c,d}[h\geq a+d][w\geq b+c][ad=bc](h-a-d+1)(w-b-c+1)\\ =&\sum_{1\leq n}(\sum_{a|n}[h\geq a+\frac{n}{a}](h-a-\frac{n}{a}+1))(\sum_{b|n}[w\geq b+\frac{n}{b}](w-b-\frac{n}{b}+1))\\ =&\sum_{1\leq n}f(n)g(n) \end{aligned}$$

我们可以分别计算$f$和$g$。计算的方法也很简单，枚举$a$，并枚举所有$a$的倍数进行贡献即可。由于$1\leq ab\leq hw$。因此总的时间复杂度为$O(hw\log_2 hw)$。

Ad hoc

题目1：给定一个无限长的一维网格，其中有一个棋子。以及一个长度为$n$的字符串$S$，$S$中仅包含$3$类字符$A,B,?$。之后游戏由$A,B$二人进行。流程如下。

1. 读取并删除$S$最前面的字符$c$。
   • 如果$c$是$A$，那么$A$行动。$A$可以选择一个空网格，放置一个挡板。如果这时候棋子附近的两个网格都存在挡板，那么$A$获胜。
   • 否则$c$是$B$，那么$B$行动。$B$可以移动棋子到一个附近的空网格中，或保持不动。
2. 如果$S$为空，则$B$获胜，否则回到步骤$1$。

其中$1\leq n\leq 10^6$。记$k$表示$?$的数量，那么允许你将$?$替换为$A$或$B$，问总共$2^k$种替换的情况下，有多少种情况$A$能获胜。

提供一道题目。

我们可以考虑这样一个问题，有一个二元组$(a,b)$，之后如果下一个操作人为$A$，则二元组被替换为$(\min(\lceil a/2\rceil,b),1)$，否则$B$操作，二元组被替换为$(a,b+1)$。当$a=1$的时候$A$就获得胜利。这个问题等价于原问题。

可以发现在$B$获胜的情况下，$S$中最多只允许出现$O(\log_2 n)$个$A$。我们记$m$为$A$的出现次数，$b_i$表示在第$i$次$A$出现后以及第$i+1$次$A$出现前，$B$允许操作次数。这样我们得到另外一个序列$b_1,\ldots,b_{m-1}$。

可以发现$A$第2次操作后，二元组的第一个元素为$b_1+1$；第3次操作后，二元组的第一个元素为$\min(\lceil (b_1+1)/2\rceil,b_2+1)$；第4次操作后，二元组的第一个元素为$\min(\lceil (b_1+1)/2^2\rceil,\lceil (b_2+1)/2^1\rceil,b_3+1)$。而最后一次操作后，结果为$\min_{i=1}^{m-1}\lceil (b_i+1)/2^{m-i}\rceil$，而要让$B$获胜，这个值必须大于$1$。

我们可以倒着进行DP，记$dp(i,j)$表示确定从$i$往后的所有未知数且$S_i$被设置为$A$，且$A$已经操作了$j$次。可以发现DP可以$O(n\log_2n)$完成。

概率计数

题目1：给定字符集$C$，以及给定$n$个长度为$m$的互不相同的字符串$s_1,\ldots,s_n$。之后要求考虑这样一个问题，初始有一个空串，之后不断随机选择一个字符加入到空串尾部。记$x_i$表示$n$个字符串中首次出现位置最小的是第$i$个字符串的概率。要求输出$x_1,\ldots,x_n$。其中$1\leq n,m\leq 300$。

提供一道题目。

这道题的一般做法是建立AC自动机。之后根据转移关系搞出转移矩阵$A$，之后高斯消元求解即可。这样做的时间复杂度为$O(n^3m^3)$。

这样比较慢，有一种很难理解的做法。就是加入一个新的变量$x_0$。之后则有：

$$\left\{ \begin{array}{lcr} \sum_{i=1}^nx_i&=&1\\ x_i+\sum_{j=1}^n\sum_{k=1}^{m-1}[pref(s_i,k)=suf(s_j,k)]\frac{x_j}{C^{m-k}}-\frac{x_0}{C^m}&=&0 \end{array} \right.$$

对上面这$n+1$个式子进行高斯消元就可以得出解了。当然我也不太明白这个公式是啥意思。

线性递推计数

题目1：给定线性递推关系，对于所有$i\geq k$，有$F_i=\sum_{j=1}^kF_{i-j}a_j$，以及$F_0,\ldots,F_{k-1}$。要求计算$F_n$，其中$1\leq n\leq 10^{18}$，$1\leq k\leq 10^5$。

BM算法+FFT，可以做到$O(k\log_2k\log_2n)$。

题目2：给定线性递推关系，对于所有$i\geq k$，有$F_i=\sum_{j=1}^kF_{i-j}a_j$，以及$F_0,\ldots,F_{k-1}$。要求计算$F_0,\ldots,F_n$，其中$1\leq n\leq 10^{6}$，$1\leq k\leq 10^5$。

令$\overline{F}=\sum_{i=0}^{\infty}F_ix^i$，令$\overline{A}=\sum_{i=1}^na_ix^i$，那么可以发现$\overline{G}=\overline{F}*\overline{A}-\overline{F}$仅有$x^0,\ldots,x^{k-1}$项的系数非$0$。因此我们可以在模$x^k$意义下计算出$\overline{G}$。

之后可以发现有：

$$\overline{F}=\frac{\overline{G}}{\overline{A}-1}$$

我们可以用多项式求逆快速算出$\overline{F}$的前$n+1$项。总的时间复杂度为$O(n\log_2n)$。

数论计数

题目1：处理$q$个请求，每个请求给定$n,m$，要求计算$\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=1]$，其中$1\leq q\leq 10^3$，且$1\leq n,m\leq 10^6$。

不妨认为$n\geq m$，直接用莫比乌斯函数可以得出：

$$\ \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=1]\\ =&\sum_{i=1}^n\sum_{j=1}^m \sum_{d|gcd(i,j)} \mu(d)\\ =&\sum_{d=1}^m \mu(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\\ =&\sum_{d=1}^m \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \end{aligned}$$

考虑到$\lfloor \frac{n}{d} \rfloor$和$\lfloor \frac{m}{d} \rfloor$分别只有$O(2\sqrt{n})$和$O(2\sqrt{m})$种可能取值，因此我们可以用数论分块，通过预处理$\mu$函数的前缀和，预处理的时间复杂度为$O(10^6)$，之后每个请求可以$O(\sqrt{n}+\sqrt{m})$完成。

题目2：处理$q$个请求，每个请求给定$n,m$，要求计算$\sum_{i=1}^n\sum_{j=1}^m gcd(i,j)$，其中$1\leq q\leq 10^3$，且$1\leq n,m\leq 10^6$。

不妨认为$n\geq m$，类似题目1，展开后得到：

$$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m gcd(i,j)\\ =&\sum_{g=1}^m g \sum_{i=1}^{\lfloor \frac{n}{g} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{g} \rfloor} [gcd(i,j)=1]\\ =&\sum_{g=1}^m g \sum_{i=1}^{\lfloor \frac{n}{g} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{g} \rfloor} \sum_{d|gcd(i,j)} \mu(d)\\ =&\sum_{g=1}^m g \sum_{d=1}^{\lfloor \frac{m}{d} \rfloor} \mu(d) \sum_{i=1}^{\lfloor \frac{n}{gd} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{gd} \rfloor} \\ =&\sum_{g=1}^m g \sum_{d=1}^{\lfloor \frac{m}{d} \rfloor} \mu(d) \lfloor \frac{n}{gd} \rfloor \lfloor \frac{m}{gd} \rfloor \\ =&\sum_{gd=1}^m \sum_{g|gd} g\mu(\frac{gd}{g}) \lfloor \frac{n}{gd} \rfloor \lfloor \frac{m}{gd} \rfloor \\ \end{aligned}$$

我们令$f(gd)=\sum_{g|gd} g\mu(\frac{gd}{g})$，很显然我们可以通过枚举所有可能的$g$和$d$来贡献$gd$，这样预处理$f$的时间复杂度为$O(10^6\ln 10^6)$。

之后上面的公示化成了：

$$\sum_{gd=1}^m f(gd) \lfloor \frac{n}{gd} \rfloor \lfloor \frac{m}{gd} \rfloor$$

只要预处理$f(gd)$的和，对$n$和$m$做数论分块，这样一个请求的处理时间仅为$O(\sqrt{n}+\sqrt{m})$。