2024 北京 - count

12.12 上午：count from mazihang2022

[LNOI2022] 盒

摘自 act ii : 推土机 2.0（NOIP ver.）

首先考虑算每一个 $i\rightarrow$ 的贡献，带有一个绝对值，可以把它拆开来，变成四个有上下界的式子，最终我们只要求下面两个式子：

$$f(n,m,i,k)=\sum\limits_{j=0}^k\dbinom{i+j-1}{j-1}\dbinom{n-i+m-j-1}{n-i-1}$$

$$g(n,m,i,k)=\sum\limits_{j=0}^kj\dbinom{i+j-1}{j-1}\dbinom{n-i+m-j-1}{n-i-1}$$

$g$ 的这个系数好难受，考虑给他缩到式子里面，所以遇到类似的式子要有归一思想，最后化出来是可以转化为 $f$ 的，所以现在变成如何求 $f$。

$$\sum\limits_{j=0}^k\dbinom{j+i-1}{j}\dbinom{n-i-1+m-j}{m-j}$$

$f$ 里面有这么一个式子，长得很像范德蒙德卷积对吧。但是他有上界，没法直接套。

显然当 $k=m$ 的时候原式等价于 $\dbinom{n+m-1}{m-1}$。因为这样原式的组合意义就是有一个长度为 $n$ 的数列，枚举前 $i$ 项和后 $n-i$ 项的和的非负整数解数目。

现在 $k$ 不一定等于 $m$，怎么做呢。这个东西其实应该是没有具体的 $\mathcal O(1)$ 求法的，但是神奇的是他和这个式子是等价的：

$$\sum\limits_{j=i+1}^n\dbinom{j+k-1}{j-1}\dbinom{m-k-1+n-j}{n-j}$$

大概就是考虑原来的组合意义，就是前 $i$ 项和 $\le k$，$n$ 项总和为 $m$ 的方案数，那我们可以枚举是从前 $j$ 项开始和 $>k$，然后插板法前后算一下。

这个好处就是我们可以在 $\mathcal O(1)$ 时间内将 $i$ 或 $k$ 递增或者递减，动态维护这个式子的值，在这一题用处就很明显了，因为 $f$ 里面的参数都是单调递增的，所以就可以指针维护了！

CF1097G Vladislav and a Great Legend

观察到这个幂可以用二项式定理拆开，但是转移一项是 $\mathcal O(k^2)$ 的。另一种方案转下降幂，$\sum\limits_{S}f(S)^k = \sum\limits_{S}\sum\limits_{i=1}^n \begin{Bmatrix}k\\i\end{Bmatrix}i!\dbinom{f(S)}{i}$，交互求和顺序得到：$\sum\limits_{S}f(S)^k = \sum\limits_{i=1}^n\begin{Bmatrix}k\\i\end{Bmatrix}i!\sum\limits_{S}\dbinom{f(S)}{i}$。后面式子的组合意义就是在所有可能的虚树里面选 $i$ 条边的方案数，树上背包分析一下时间复杂度 $\mathcal O(nk)$。具体的分析就是考虑合并子树的过程中，选 $k$ 个转化为左子树选 dfn 最大的 $k$ 个，右子树选 dfn 最小的 $k$ 个，然后发现每个点只会对其周边 $\mathcal O(k)$ 级别的点做贡献，所以时间复杂度正确。

有向无环图计数

这个的理解其实刚开始我是和二项式定理完全弄混了，好好理解一番之后发现二项式定理就学的一知半解。

首先声明：二项式定理的「钦定 $g$」最后转「恰好 $f$」的那个组合数是为了去除 $\pmb g$ 的方案多算 $\pmb f$ 的次数。

好，回到这题。令 $f_i$ 表示 $i$ 个点的答案，因为是有向无环图，所以我们可以枚举度数为 $0$ 的点的个数，有以下式子：

$$f_n=\sum\limits_{i=1}^i (-1)^{i+1}\dbinom n i 2^{i(n-i)}f_{n-i}$$

这里并不是二项式反演，因为 $\dbinom n i 2^{i(n-i)}f_{n-i}$ 这个整体代表 「钦定 $\pmb g$」$i$ 个点入度为 $0$ 的方案数，反演回来还需要带一个容斥的组合数。那上面是什么意思呢？我们最后希望每个度数为 $0$ 的点集 $S$ 都被算一次，所以根据 $\sum\limits_{i=1}^n (-1)^{i+1}\dbinom n i=[n\not= 0]$ 这个经典式子，设计 $(-1)^{i+1}$ 这个容斥系数。

UOJ37 「清华集训 2014」主旋律

题目等价于强联通子图数量，直接不是很容易的，容斥一下，令 $f_S$ 表示 $S$ 点集组成强联通图的方案数，根据上面的有向无环图计数，同样的每次可以枚举所有入度为 $0$ 的强联通分量的点集并，但是不好枚举。所以我们提前预处理 $g_S,h_S$ 表示 $S$ 点集构成的强联通分量个数为奇 / 偶的容斥系数和 $f$ 之积，最后 $f$ 就可以枚举子集了，令 $\mathsf E(S,T)$ 表示集合 $S$ 连向集合 $T$ 的边的条数，为 $f_S=2^{\mathsf E(S,S)}-\sum\limits_{T\subseteq S}(g_T-h_T)2^{\mathsf E(T,S-T)+\mathsf E(S-T,S-T)}$。

注意一下当 $S=T$ 的时候要最后转移，特殊判断一下。

[ABC236Ex] Distinct Multiples

写完这题发现我原来学了个假的容斥！

非常典的容斥，每两个元素有一个相等关系 $(i,j)$，钦定一个集合 $S\subseteq \{(i,j)\mid 1\le i<j\le n\}$，系数为 $(-1)^{|S|}$，显然是过不去的。我们只关系最终图的连通性，所以我们希望求出一个连通块的系数，如果是多个连通块容斥系数直接相乘就好。令大小为 $n$ 的连通块系数为 $g_n$，由于对于没有限制的情况，总系数应该是 $\sum\limits_{i=1}^{|E|}(-1)^i\dbinom {|E|} i=[n=1]$（也就是我们希望将边容斥转化为点容斥之后，对应的系数不变），减去不联通的系数 $\sum\limits_{i=1}^{n-1}\dbinom{n-1}{i-1}g_i[n-i=1]$，为了不算重我们把最小钦定了，其他点可以随便填，所以容斥系数之和就是 $[n-i=1]$，化简得到 $g_i=-(i-1)g_{i-1}$，推出来系数就可以正常 dp 了，时间复杂度 $\mathcal O(3^n)$。

CF917D Stranger Trees

发现恰好不是很好算，容易想到先统计至少然后二项式反演一下。假如说我现在钦定了 $i$ 条边，已经形成了 $n-i$ 个连通块，容易通过 Prufer 序列的推广形式得到方案数为 $\prod\limits_{i=1}^k s_i\cdot n^{k-2}$，直接树形 dp 已经可以做到优秀的 $\mathcal O(n^3)$ 复杂度，继续考虑组合意义：$\prod\limits_{i=1}^k s_i$ 表示从每个连通块里面选一个点的方案数，于是令 $f_{u,i,0/1}$ 表示决策到子树 $u$，当前有 $i$ 个连通块，与 $u$ 连通的连通块是否选了点的答案总和，时间复杂度 $\mathcal O(n^2)$。

这里填一个 Prufer 序列那个推广结论的证明：

容易得到其 Laplacian 矩阵去掉 $k$ 行 & 列的行列式如下：

$$\begin{vmatrix} a_1(n-a_1) & -a_2a_1 & \cdots & -a_1a_{k-1} \\ -a_2a_1 & a_2(n-a_2) & \cdots & -a_2a_{k-1}\\ \vdots & \vdots& \ddots & \vdots\\ -a_{k-1}a_1 & -a_{k-1}a_2 &\cdots & a_{k-1}(n-a_{k-1}) \end{vmatrix}$$

提个系数，并把 $2\sim k-1$ 列加到第一列得到：

$$\prod\limits_{i=1}^{k-1}a_i\begin{vmatrix} a_k & -a_2 & \cdots & -a_{k-1} \\ a_k & n-a_2 & \cdots & -a_{k-1}\\ \vdots & \vdots& \ddots & \vdots\\ a_k & -a_2 &\cdots & n-a_{k-1} \end{vmatrix}$$

最后把所有行都减去第一列：

$$\prod\limits_{i=1}^{k-1}a_i\begin{vmatrix} a_k & -a_2 & \cdots & -a_{k-1} \\ 0 & n & \cdots & 0\\ \vdots & \vdots& \ddots & \vdots\\ 0 & 0 &\cdots & n \end{vmatrix}$$

答案为 $n^{k-2}\prod\limits_{i=1}^ka_i$。

P6596 How Many of Them

容易想到令 $f_{i,j}$ 表示 $i$ 个节点组成了 $j$ 个边双的方案数，最后把用割边连接 $j$ 个边双的方案数 $n^{k-2}\prod a$ 累加上去，这里里面的 $a$ 要在 dp 里更新。有 $f_{i,j}=\sum\limits_{k=1}^{i-1}f_{k,1}f_{i-k,j-1}\dbinom{i-1}{k-1}$，当 $j=1$ 的时候，直接再容斥，用所有连通图的数量减去 $f_{i,j>1}$ 就可以了，别忘了乘上 $i$ 的系数。

CF1608F MEX counting

下辈子再来卡常😄

发现如果直接做必须要记录 > mex 的数填的状态。尝试延续钦定，我们只关心有多少种数 > mex，至于是多少，需要填的时候再来用，令 $f_{i,j,k}$ 表示填到第 $i$ 个数，mex 为 $j$，其中 $k$ 种数比 mex 大且尚未钦定。最关键的转移就是 $\dfrac{k!}{(k-t+j+1)!}f_{i,j,k}\rightarrow f_{i,t,k-t+j+1}$，移个项就可以优化了。

CF1515E Phoenix and Computers

令 $f_{i,j}$ 表示填了 $i$ 个数且目前有 $j$ 段的方案数，随便转移，时间复杂度 $\mathcal O(n^2)$。

CF1782F Bracket Insertion

子问题的应用，难点在于想到可以直接增量构造。

首先把概率最后乘上。然后我们画出这个折线图，考虑一个插入 () 的操作本质是在干什么：选择一个折线上的点，令其纵坐标为 $x$，在这个位置插入纵坐标为 $\{x,x+1,x\}$ 的三个点。于是令 $f_{n,x}$ 表示操作 $n$ 次，开头纵坐标为 $x$ 的方案数，可以得到转移式（插入 ()）：

$$f_{n,x}=\sum\limits_{i=0}^{n-1}\sum\limits_{j=1}^{n-1-i}p\dbinom {n-1}i\dbinom{n-1-i}{j}f_{i,x}f_{j,x+1}f_{n-1-i-j,x}$$

这里做到了时间复杂度 $\mathcal O(n^4)$，把无关项提一下：

$$f_{n,x}=\sum\limits_{i=0}^{n-1}\dbinom {n-1}if_{i,x}\sum\limits_{j=1}^{n-1-i}p\dbinom{n-1-i}{j}f_{j,x+1}f_{n-1-i-j,x}$$

后面这堆显然可以实时处理的，时间复杂度 $\mathcal O(n^3)$。

CF1842G Tenzing and Random Operations

组合意义保平安。

把题目看做一个从左到右走的方案数，每次后缀加就是增加一个可以后面走 $v$ 次的魔法，发现我们只要关心魔法是否有没有使用过，于是我们记录在 dp 状态里就好了。

CF1264D2 Beautiful Bracket Sequence (hard version)

很久之前就做的了，大概有个关键结论就是一个括号串的深度为 $\sum\limits_{i=1}^n\min\{\sum\limits_{j=1}^i[s_j=\texttt{(}],\sum\limits_{j=i+1}^n[s_j=\texttt{)}]\}$，而且这个式子肯定会在 $\min$ 里面两个数取等的时候取到最大值，然后化出一个式子，就是一个范德蒙德卷积的形式，就可以线性算了。

[AGC017F] Zigzag

自己的漏洞真的是太多了，现在想想的确没有遇见过几道轮廓线（诸如此类还有笛卡尔树，meet in the middle 等）

首先暴力 dp 是 $\mathcal O(m4^n)$ 的，换成轮廓线就是 $\mathcal O(nm2^n)$。瓶颈在于我们要记录一个当前路径和上一条路径的距离。但是，我们记录这个本质是为了计算当前能不能往左 / 右走，所以我们把前一条路径拼接在这条路径下面肯定是不劣的，这样距离就永远都是 $0$ 了。

CF1924D Balanced Subsequences

首先有一个很傻逼的容斥，我就不讲了，时间复杂度 $\mathcal O(n^2)$，化了一下式子也没什么前途。

回想一下我们是怎么求最长合法序列的，在折线图上走，如果目前在 x 轴上而且还要向下走，那么不动。也就是我们最后如果要匹配 $k$ 对括号，那么就要向下走破 $m-k$ 次，也就是最低点的纵坐标为 $k-m$。恰好是不好算的，于是算至少，这个就是典型的折线计数了，时间复杂度 $\mathcal O(1)$。

[JLOI2015] 骗我呢

第一次学，还是挺新鲜的！名字叫反射容斥。

普通的 dp 是简单的，最后转化成了下面这个问题：从 $(0,0)$ 开始走到 $(x,y)$，只能向上或者向右，求不碰到两条线的方案数。

那我们只要用所有方案数 - 第一次经过上面线（这里简称 A）的方案数 - 第一次经过下面线（这里简称 B）的方案数。

如何求先经过 A 的方案数呢？我们先关于 A 对称一下，然后到这个点的方案数等价于最后经过的线为 …[A…A] 或者 …[A…A][B…B] 的方案数，把连续段合并在一起就是经过直线的序列以 A 和 AB 结尾方案数，但是多算了 B 开头的一些东西，再次沿着 B 对称一下，现在方案数对应的就是以 …[B…B][A…A][B…B] 和 …[B…B][A…A] 的方案数。。。

这样递归下去直到超过第一象限，答案就是对的，因为以 A 开头的方案一定是正的比负的多一次，B 开头的抵消了，这个递归复杂度是对的，应该是一个关于这个点坐标大小的复杂度？

[JOISC2020] 最古の遺跡 3

感觉不是很难。。但是卡在中间了

首先容易发现题目这个操作可以延迟的，也就是其实按照值域操作也是可以的。如 $[1,2,1,2,3,3]$，先对 $3$ 操作 $[1,2,1,2,2,3]$，再对 $2$ 操作 $[1,1,1,1,2,3]$，最后得到了 $[0,0,0,1,2,3]$。

于是我们就可以再转化一下，最终序列一定是这样得到的：目前有空集 $S$，对于 $i=2n\cdots 1$，如果目前 $\text{mex}(S)\le a_i$（以下 $\text{mex}$ 从 $1$ 开始定义），那么 $i$ 最终值为 $\text{mex}$ 并将其加入 $S$，否则 $i$ 没值。

很熟悉的想到了 CF1608F，我们能不能加入只和目前最大的 $t$ 使得所有 $1\sim t\in S$ 的 $t$ 有关，剩下的延续钦定就好了。令 $f_{i,j}$ 表示考虑了 $i\sim 2n$ 的元素，目前最大的值域连续段是 $1\sim j$，我就卡在这里了，觉得非常不好转移啊！但是写写发现就明朗了，令 $c_0$ 表示 $i+1\sim 2n$ 最终没数的位置数，$c_1$ 反之。

• 当前位置最终没数了
  • 这里有一个结论：如果存在 $S$ 中存在连续段 $1\sim t$，那么这些对应的原始数取值范围一定也是 $[1,t]$，否则如果有更大的 $t$ 也会更大。这里为了好转移，同个数区分开来，最后除掉 $2^n$ 就好了，于是转移为 $f_{i-1,j}\cdot (2j-c_0)\rightarrow f_{i,j}$。
• 当前位置最终有数
  • 第一种填法就是不会改变连续段大小，那么延续钦定就不用管系数了，$f_{i-1,j}\rightarrow f_{i,j}$。
  • 第二种填法改变了连续段大小，假如说原来连续段为 $1\sim j$，新的连续段为 $1\sim k$，首先目前总共能填的有 $2k$ 个数，需要钦定 $k-j-1$ 个数，而且不能填值域 $\le j$ 的数，所以 $i$ 能选的个数为 $2k-k+j+1-2j=k-j+1$。剩下的我们先从 $c_0-j$ 个没钦定的里面选 $k-j-1$，然后希望他们最终能变成一个长度为 $k-j-1$ 的连续段，现在没法快速计算，设这个系数为 $g_{k-j-1}$，那么有转移 $f_{i-1,j}\cdot \dbinom{c_0-j}{k-j-1}\cdot(k-j+1)\cdot g_{k-j-1}\rightarrow f_{i,k}$。

现在转化求 $g_i$，表示值域在 $[1,i]$ 的 $i$ 个数经过地震之后每个位置都不为 $0$ 的方案数，这个是同理的，有转移式 $g_n=\sum\limits_{i=0}^{n-1}(n-i+1)\dbinom{n-1}{i}g_ig_{n-i-1}$，前面系数是第一个数的填法，第二个组合数是把 $g_i$ 插到 $g_{n-i-1}$ 的方案数，时间复杂度 $\mathcal O(n^3)$。

CF1909F2 Small Permutation Problem (Hard Version)

也是很久之前做的了，大概关键在于选的时候把连续的 -1 一起看，这样就不用加一些乱七八糟的维度，然后就是平凡的枚举和转移。

[AGC024E] Sequence Growing Hard

好牛的题，这个转化方式很神！

题目等价于每次插入一个数，然后字典序递增，原本想转化成删数的，发现更不好做了。但是发现如果将相同的数缩成一段，那么每次插入只能插在比他小的数的前面，这个指引我们去建立一种两两关系。

给每个下标赋予一个二元组 $(val, t)$，表示 $a_i$ 为 $val$，是在时刻 $t$ 插入的。我们对其建树，每次把 $j$ 插到 $i$ 前面，那么就把 $j$ 的二元组挂在 $i$ 下面，这样二元组的每一维都是小根堆。然后我们就可以 dp 了！令 $f_{i,j}$ 表示当前树大小为 $i$，根节点值为 $j$ 的情况下，树形态的方案数。枚举第一棵子树（这里子树是有顺序的），则有 $f_{i,j}=\sum\limits_{t=1}^{i-1}\dbinom{i-2}{t-1}f_{n-i,k}\sum\limits_{va=j+1}^{V}f_{i,va}$，前面组合数就是已经钦定了根的 $t$ 为 $1$，枚举的子树的根的 $t$ 为 $2$，剩下把 $t$ 按顺序插进去。最后答案就是 $f_{n+1,0}$。

至于这里为什么不用考虑相同数的问题，就是如果有一段相同的数，那么应该是在其前面比他小的第一个值的一个子树的所有儿子，这里肯定是只会计算一遍的。

XYD341

Topcoder #11213 Apple Trees

12.12 下午：count+ from dengyaotriangle

[ARC118E] Avoid Permutations

套路转化贡献体，对于每一条路径我们计算其被计算的方案个数。直接算不是很好算的，但是可以容斥（现在容斥和二项式反演已经搞不清楚了，，，随便说一个），钦定一些点必须经过，然后其他随便放，所以要额外记录一维没有钦定过的 -1 个数，令 $f_{i,j,k,0/1,0/1}$ 表示目前决策到 $(i,j)$，有 $k$ 个 $-1$ 没有钦定，其中当前行上有没有障碍，当前列上有没有障碍，时间复杂度 $\mathcal O(n^3)$。

[THUWC2017] 随机二分图

很好的一道题，这个是拆贡献的典范。

转化贡献体，到每一个完美匹配上面，如果全部都是 $t=0$，那么非常好算。部分分一定方面启示了把 $t=1/2$ 的操作转化为 $t=0$。先考虑直接拆：如果对于 $t=1$，给两条边赋权 $\dfrac 1 2$，那么单独选的概率是对的，一起选的概率差 $\dfrac 1 4$，可以再补一个两条边捆绑的物品，权值为 $\dfrac 1 4$，$t=3$ 同理。然后令 $f_{S,T}$ 表示两边分别匹配了 $S,T$ 的状态，感性理解状态数不会很多的，话说怎么 gp_hash_table 怎么死循环，unordered_map / cc_hash_table 只花了 1s！