题集

搞一点计数题放在这，看到有意思的计数就更（虽然在组合数学那已经更了好多了）。

[CTSC2017] 吉夫特

给定一个长度为 $n$ 的序列 $a$ ，保证 $a_i$ 互不相同。求出有多少个长度大于等于二的序列满足

\prod _{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2 = \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \binom{a_{b_{k-1}}}{a_{b_k}} \bmod 2 > 0

方案数对 $10^9+7$ 取模。

数据范围： $n\le 211985, a_i\le 233333$ 。

我们考虑这个序列的性质，即这些组合数中不能出现偶数。我们考虑如何利用这个性质。

我们把组合数的计算公式搬出来： $\dbinom{n}{m}=\frac{n!}{m!(n-m)!}$ ，为了让它为奇数，我们需要让上下阶乘的 $2$ 的个数相等。

我们考虑把阶乘分解，设 $f(x)$ 为 $x!$ 所含的 $2$ 的个数，则易得：

f(x)=\sum_{i=1}^{+\infty} \frac{x}{2^i}

我们再设 $g(x)=x$ ， $h(x)$ 为 $x$ 二进制中 $1$ 的个数，则

\begin{aligned} g(x)&=g(\frac{x}{2})+\frac{x}{2}+(x\bmod 2)\\ &=\sum _{i=1}^{+\infty} \frac{x}{2^i}+h(x) \\ &=f(x)+h(x) \end{aligned}

则 $f(x)=g(x)-h(x)=x-h(x)$ 。再根据需要让上下阶乘 $2$ 的个数相等，能得出来 $h(n)=h(m)+h(n-m)$ ，即 $n$ 二进制下 $1$ 的个数等于 $m$ 二进制下 $1$ 的个数加 $n-m$ 二进制下 $1$ 的个数。我们考虑如何满足这个条件。

考虑 $n=(\cdots 00100\cdots)_2, m=(\cdots 00010\cdots)_2$ ，那么 $n-m=(\cdots 00010\cdots)_2$ 。显然不可能 $1$ 的个数相等，因此我们必须满足 $m$ 是 $n$ 的子集。

这样就好做了。我们先把所有数存一下位置，从后往前扫，枚举 $a_i$ 的子集，看是否在 $i$ 后面，转移即可。

时间复杂度： $O(\mathrm{能过} )$ 。

[HNOI2012] 集合选数

给定一个集合 $\{1, 2, 3\cdots n \}$ ，问有多少满足下述限制的子集：如果 $x$ 在该集合中，那么 $2x, 3x$ 不能在该集合中。

数据范围： $n\le 10^5$ 。

很有意思的一道题。

我们考虑从一个数为左上角开始构造出一个矩阵，这个矩阵每个数都是它左边数的 $2$ 倍，是它上面的数的 $3$ 倍。比如以 $1$ 为例，构建出的矩阵即为：

\begin{bmatrix} 1& 2& 4& 8& \cdots&\\ 3& 6& 12& 24& \cdots&\\ 9& 18& 36& \cdots &\cdots&\\ 27& \cdots& \cdots& \cdots& \cdots&\\ \cdots &\cdots &\cdots &\cdots &\cdots \end{bmatrix}

这样，我们就把问题转化为了：在这个矩阵中选择数字，满足选择的数字不相邻。同时我们发现，每个矩阵的方案互不干扰。我们就可以每个矩阵求一遍。

不难看出，这个矩阵的大小最多为 $\log_2 n\times \log_3 n$ 。我们可以直接状压 dp，是一个比较经典的状压 dp 问题。~~可以直接用插头 dp 解决。~~

时间复杂度： $O(\mathrm{能过})$ 。

Piling Up

一开始有 $n$ 个颜色为黑白的球，但不知道黑白色分别有多少。 $m$ 次操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球，最后拿出的球按顺序排列会形成一个颜色序列，求颜色序列有多少种。

数据范围： $1 \le n \le 3000,1 \le m \le 3000$

很容易设计出状态 $f[i, j]$ 为 $i$ 次操作后有 $j$ 个黑球时的方案数，也很容易写出状态转移：

f[i, j]=f[i-1, j-1]+f[i-1, j+1]+f[i-1,j]+f[i-1,j]

即四种拿出球的顺序：黑黑、白白、黑白、白黑。答案即为 $\sum f[m][i]$ 。

但是我们发现这样会计算重复。见下图：

在这张图中，横坐标为操作数，纵坐标为盒子中黑球的数量，折线即为黑球的变化量，其中折线不能低于 x 轴，也不能高于我们规定的盒子中球的数量（也就是上图中的红线）。我们发现这样会被计算多次，我们就考虑去掉重复，只保留一条折线。我们就可以将红线向下平移一单位，保留下来的方案即为多计算的。见下图：

这样就可以避免重复计算。时间复杂度 $O(n^2)$ 。

方格染色

有一个 $n\times m$ 的网格，每个格子可以被染成红色或蓝色。要求每个 $2\times 2$ 的区域内每种颜色的个数必须是奇数。现在已经有 $k$ 个格子被染色，求有多少合法的染色方案数。

数据范围： $n, m, k\le 10^5$ 。

有意思的找规律题。我们首先可以发现，如果这个网格的第一行和第一列确定后，整个网格就能被确定。因此我们就把问题转化为了对第一行和第一列的计数。我们发现一个 $2\times 2$ 的区域中的数字异或起来必定为 $1$ ，稍微分析一下即可得到一个被染色的格子只会影响到第一行、第一列、原点构成的矩形的顶点。再找找规律就能找到这三个的异或关系。

这时我们就可以枚举原点的状态，然后把问题转化为 2-SAT，用边带权并查集即可。

城市规划

求 $n$ 个点有标号连通图的个数。

数据范围： $n\le 130000$ 。

本题可能不是那么精妙，但是是下一道题的前置。

我们设 $c_i$ 为 $i$ 个点有标号连通图个数， $\varphi(i)$ 为 $i$ 个点的图的个数，易知 $\varphi(x)=2^{\frac{x(x-1)}{2} }$ ，只需要看点与点之间的边是否在图中即可。

我们考虑容斥，求出不连通图的个数。我们可以枚举一号点所在连通块的大小，就能得到转移方程

c(n)=\varphi(n)-\sum \limits _{i=1}^{n-1}\dbinom{n-1}{i-1}c_i\varphi(n-i)

这个转移方程右半部分的含义是： $1$ 号点所在连通块的方案数为 $c_i$ ，同时我们需要选出 $i-1$ 个点和它在一个连通块中。剩下的点就不用管了，形成任意的图都可以。

考虑加速计算这个式子：

\begin{aligned} c_n&=\varphi(n)-\sum \limits _{i = 1}^{n-1}\frac{(n-1)!}{(i-1)!(n-i)!}c_i\varphi(n-i)\\ \frac{c_n}{(n-1)!} &=\frac{\varphi(n)}{(n-1)!}- \sum \limits _{i = 1}^{n-1}\frac{c_i}{(i-1)!}\frac{\varphi(n-i)}{(n-i)!} \end{aligned}

设 $\phi (x)=\frac{c(x)}{(x-1)!}$ ， $\pi (x)=\frac{g(x)}{x!}$ 。那么上面的式子就变为了

\phi(n)=\frac{g(n)}{n!}-\sum \limits_{i=1}^{n-1}\phi (i)\pi(n-i)

直接分治 FFT 即可。时间复杂度 $O(n\log^2 n)$ 。

How Many of Them

求有 $n$ 个点，割边数量不超过 $m$ 的无向连通图的数量。

数据范围： $n, m\le 50$ 。

比较 nb 的不用多项式的图论计数。

我们设 $F[i, j]$ 为 $i$ 个点， $j$ 条割边的无向连通图的数量。我们考虑去掉 $1$ 号点所在的双连通分量，那么整张图就会分为一堆连通块。我们再设 $G[i, j, k]$ 为 $i$ 个点， $j$ 条割边， $k$ 个连通块的无向图的数量。那么我们枚举 $1$ 号点所在连通分量的大小，就能对于 $0<j<i$ 得到转移方程：

F[i, j]=\sum \limits _{p=1}^{i-1}(F[p, 0]\times\dbinom{i-1}{p-1}\times \sum \limits _{q=1}^j (G[i-p,j-q,q]\times p^q))

$p$ 枚举的是 $1$ 号点所在连通分量的大小， $q$ 枚举的是 $1$ 号点所在的连通分量去掉后会剩下多少连通块，而割边也会随之减少 $q$ ，可以看下图理解：

由于边双的性质，最后一定会形成一棵树

然后 $p^q$ 的含义即为我们每个连通分量一定会选择 $1$ 号点所在的连通块中一个点连边，那么方案数即为 $p^q$ 。

再考虑求出 $F[i, 0]$ 。根据容斥，我们只需要用连通图的数量减去含割边的图的数量即可，而连通图的数量则看上一道题。因此：

F[i, 0]=c_i-\sum \limits _{j=1}^{i-1}F[i,j]

最后我们再考虑求出 $G$ 数组。我们依旧枚举 $1$ 号点所在连通块大小 $p$ ，同时我们再枚举一号点连通块割边的数量 $q$ ，我们就能得到转移方程：

G[i,j,k]=\sum\limits_{p=1}^i\sum\limits _{q=0}^j(f[p,q]\times p\times \dbinom{i-1}{p-1}\times G[i-p,j-q,k-1])

我们注意到其中多乘了一个 $p$ ，这其实代表着我们求出的是“有根双连通分量”，因为我们要在这个双连通分量中选一个点来和一开始去掉的边双连边。因此我们多乘了一个 $p$ ，而在别的情景中需要视情况而定。

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

串珠子

有 $n$ 颗珠子，所有的珠子互不相同，用整数 $1$ 到 $n$ 编号。对于第 $i$ 个珠子和第 $j$ 个珠子，可以选择不用绳子连接，或者在 $c_{i,j}$ 根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点，把绳子看作边，将所有珠子连成一个整体即为所有点构成一个连通图。特别地，珠子不能和自己连接。有多少种不同的方案将所有珠子连成一个整体。

数据范围： $n\le 16$ 。

我们回顾一下无向连通图的转移方程：

c(n)=\varphi(n)-\sum \limits _{i=1}^{n-1}\dbinom{n-1}{i-1}c_i\varphi(n-i)

我们本题可以类似的这样做。我们设 $f_s$ 为 $s$ 集合组成的无向连通图个数， $g_s$ 为 $s$ 集合组成的无向图个数。我们考虑 $s$ 中第一个 $1$ 所代表的点所在的联通块的集合，有如下转移：

f_s=g_s-\sum \limits f_tg_{\complement _s t}

而对于 $g_s$ ，我们只需枚举每条边看看是哪种状况即可。

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

Uniformly Branched Trees

求有多少种 $n$ 个点的不同构的树满足：除了度数为 $1$ 的结点外，其余结点的度数均为 $d$ 。

数据范围： $1 \le n \le 1000, 2 \le d \le 10$ 。

~~我怎么选了这么多图论计数~~

本题和上面的图论计数不同的是，本题没有标号。因此我们需要有一个明确的规则来防止计算重复。

我们首先先选定一个根，使得这棵树比较特殊。我们很容易就可以发现可以选择重心作为根，因为树的重心最多只有 $2$ 个，方便统计。而且这样它的子树大小都不超过 $\frac{n}{2}$ 。然后我们考虑如何计算方案。

我们设 $f[i, j, k]$ 为 $i$ 个节点，根有 $j$ 个儿子，且子树大小都不超过 $k$ 的方案数。当所有的子树大小都小于 $k$ 时，方案数为 $f[i-1, j, k-1]$ ，直接加上。然后我们枚举有多少子树大小等于 $t$ ，这样除去这些子树的方案数即为 $f[i-k\times t, j-t, k-1]$ ，而这些大小为 $k$ 的子树的总方案数可以看作是有 $t$ 个相同的小球，放到 $f[k, d-1, k-1]$ 个盒子里，盒子可空的方案数，直接插板法即可。因此转移方程为：

f[i, j, k]=f[i,j,k-1]+\sum \limits _{t\ge 1}(f[i-t\times k, j-t, k-1]\times \dbinom{f[k,d-1,k-1]+t-1}{t})

根据重心的定义，答案即为 $f[n, d, \frac{n}{2}]$ 。但是我们有时候会重复计算，因为重心可能会有两个，在这时如果两个重心两边的树如果不同，那么就会被算重复。我们需要减去这些重复的方案，即 $\dbinom{f[\frac{n}{2}, d-1, \frac{n}{2}-1]}{2}$ 。这样就能统计完。

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

Mr. Kitayuta’s Gift

给定一个小写字符串 $s$ 和一个正整数 $n$ 。要求在 $s$ 中插入恰好 $n$ 个小写字符使其回文的方案数，两个方案不同当且仅当它们得到的串不同，与插入顺序和位置无关。

数据范围： $|s| \le 200$ ， $n \le 10^9$ 。

首先为了防止记重复，我们填入字符肯定是从两边忘中间填。因此我们设 $f[i][l][r]$ 为只考虑最终回文串的前 $i$ 个字符和后 $i$ 个字符，且给定字符串还有 $s[l\sim r]$ 没有匹配时的方案数，注意，我们状态这里定义的是尽可能与 $s$ 进行匹配。

这样做的原因是因为，假如我们在考虑 sx...ys 这个字符串时，我们首先会在 sx...ys 外面加入 s 来成为回文串，而当我们进到里面时，我们又会在 x...y 这里重新加入一次 s，这样就会让 ssx...yss 算重。因此我们要让它尽可能与 $s$ 进行匹配。

这时我们填入的字母就有 $k=\frac{n+|s|}{2}$ （我们先只考虑偶回文串）。

状态设出来我们就可以转移了。

当 $s_l = s_r$ 时，我们的转移为：

\begin{aligned} f_{i+1,l, r}&\leftarrow f_{i, l+1, r-1}\\ f_{i+1,l, r}&\leftarrow 25\times f_{i, l, r} \end{aligned}

当 $s_l\not=s_r$ 时，我们的转移为：

\begin{aligned} f_{i+1,l, r}&\leftarrow f_{i, l+1, r}\\ f_{i+1,l, r}&\leftarrow f_{i, l, r-1}\\ f_{i+1,l, r}&\leftarrow 24\times f_{i, l, r} \end{aligned}

而当 $l>r$ 时，我们可以把它设为终点 $g_i$ ，而对于 $g_i$ 来说，两边放什么字母都无所谓了。因此转移为：

g_{i+1} \leftarrow 26\times g_i

我们当然可以暴力矩阵快速幂加速，复杂度为 $O(|s|^6\log n)$ 。

我们知道，dp 可以转化为在自动机上转移的过程，因此我们把自动机建出来，见下图：

图中绿色的点为 $s_l=s_r$ 的情况，因此走自环的方案数有 $25$ 中，红色点同理。

而我们要求的答案就是从起点出发，走到终点且路径长度为 $k$ 的方案数。

我们发现最终走向 $g_i$ 的点一定都是绿点（因为最终两边一定相等），那么我们就可以考虑把这个自动机优化一下状态。

我们发现绝大多数时候都是在走自环，我们就考虑自环如何插入到路径中。我们可以发现一条路径上有 $a$ 个红点和 $b$ 个绿点的路径和另一条有 $a$ 个红点和 $b$ 个绿点的路径是等价的，只需要让自环一一对应即可（这里能对应上是因为最终走到终点的一定是绿点）。因此我们总的方案数为 $\sum F(a, b)G(a, b)$ ，其中 $F(a, b)$ 为 $a$ 个红点和 $b$ 个绿点的路径走 $k$ 条边到终点的方案数， $G(a, b)$ 为走 $a$ 个红点和 $b$ 个绿点的路径数。

我们首先考虑求出 $G(a, b)$ 。这个其实可以直接在自动机上跑拓扑序 dp，我们设 $f_{l, r, a, b}$ 为在自动机上 $\{l, r\}$ 这个节点，经过了 $a$ 个红点和 $b$ 个绿点时的方案数。但是复杂度为 $O(|s|^4)$ 。但是我们可以发现有了红点的数量后绿点的数量也可以直接求出来。由于每个红点会使得字符串长度减一，绿点减二，因此绿点的数量为 $\left \lceil\frac{|s|-a}{2} \right \rceil$ 。复杂度可以降到 $O(|s|^3)$ 。

我们再考虑求出 $F(a, b)$ 。一个朴素的想法就是每次求 $F(a, b)$ 的时候就搞出来一条有 $a$ 个红点， $b$ 个绿点的链（我们前面已经说了是路径等价的），然后跑矩阵快速幂即可。就像下图：

但是我们发现这样要构建出来 $O(|s|^2)$ 条链，复杂度即为 $O(|s|^5\log n)$ 。不能接受。

但是我们考虑利用矩阵快速幂能求出图中任意两点走 $k$ 条路的方案数，我们可以把上面的图再次压缩一下：

这样构建出来图，每次只需要选取合适的起点和终点就可以获得和上面那张图一样的链和效果。

这样复杂度为 $O(|s|^3\log n)$ 。

而对于奇回文串的情况，我们发现最终 $f_{i, l, l +1}$ 的情况不能转移到 $g_i$ 。因此我们考虑把这些方案减去即可。我们按照上面的思路，依旧是 DAG 上 dp 和矩阵快速幂即可。

kangaroo

有一个园子，里面有 $n$ 个草丛排成一排，标号 $1\sim n$ ，有一个袋鼠，从 $s$ 出发，每次跳一步跳到一个其他的草丛，经过每个草丛恰好一次，最终到达 $t$ 。显然他会跳跃 $n-1$ 次为了不被人类发现，袋鼠每次跳跃的方向必须与前一次不同。

具体地，如果他现在在 $now$ ，他是从 $prev$ 跳跃一次到达 $now$ 的，然后他跳跃一次到达 $next$ ：

那么如果 $prev<now$ ，就必须有 $next<now$ ；
如果 $now<prev$ ，就必须有 $now<next$ 。

问从 $s$ 到 $t$ 的方案数模 $10^9+7$ 的结果。

数据范围： $n\le 2000$ 。

本题的 dp 是另一种套路，这里整理一下。

这里我们发现在状态里面设填到排列的第 $i$ 位不好转移，我们考虑换一种思路。

我们可以从小到大来填入 $1\sim n$ 。这时我们可以在状态里面设一维为填完 $i$ 时的方案数。这时我们还可以发现我们填数的过程可能会形成一堆连通块（也就是中间不能插入数字的部分）。因此我们可以把状态设为 $f_{i, j}$ 为填完 $i$ ，且当前有 $j$ 个连通块时的方案数。

我们考虑转移。因为我们已经填入的数字都是小于 $i$ 的，因此我们不需要考虑过多。转移的情况也就只有两种：新开一个连通块、合并两个连通块。这里没有在一个连通块旁边加入的转移是因为这样就不会符合题目的要求。这样直接转移即可。

而这种方法不会记重记漏的原因就是：一个排列就对应着一颗笛卡尔树。我们合并两个连通块就是用 LCA 来合并，新开一个连通块就是新加入一个点，而对于在连通块边加入点就是加入父亲节点。

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

Around the World

给定一张无向联通图，大小为 $n$ ，有 $m$ 条边，每条边有边权，保证无重边自环。同时保证，不存在一个长度 $>3$ 的简单环经过了 $1$ 号点。

求解有多少种方案删除若干条与 $1$ 号节点相连的边，使得不存在任意一条路径（不一定是简单路径）满足下列 $3$ 个条件：

其以 $1$ 号节点为起点， $1$ 号节点为终点。
此路径经过的所有边的边权异或和为 $0$ 。
其至少经过了一条边奇数次。

你需要输出这个方案数对 $10^9+7$ 取模的结果。

数据范围： $n,m\le 10^5,w\le 31$ 。

先想最大 XOR 路径中的套路：把所有的环找出来，这些就是能拿的异或值。我们先考虑一个及其暴力的dp：设 $f_{i, j}$ 为考虑前 $i$ 个连通块时，且能表示出来 $j$ 这个状态的数的可行性（ $j=2^{32}$ ）。转移时就看下一个连通块能表示出来什么然后转移即可。

状态数太多，考虑优化。我们发现异或能表示出来什么数这种东西很像线性基，我们考虑大小为 $5$ 的本质不同的线性基一共有多少。通过打表可以发现：一共有 $374$ 种。非常少，我们就可以把它们放到第二维。我们再处理出一个 $ok$ 数组，表示当前连通块是否能凑出来 $0$ 这个数。当 $ok_i=0$ 时，这个连通块直接跳过即可。

同时我们可以预处理出来所有的转移，这样不用每次转移时都做一次 $O(\log^2 w)$ 的线性基合并了。

我们再考虑 $1$ 在环中的情况。由于题目中说了只会包含在三元环中，因此一个连通块最多只会和 $1$ 有两条边，我们考虑是否两条边都走，或者就走一条边，或者全部删掉。不同之处只有两条边都走这个选择，我们这时会加上三元环的贡献，我们加上即可。因此这种情况的转移方程为：

\begin{aligned} f_{i, s}&\leftarrow f_{i-1, s}\\ f_{i, s\cup t}&\leftarrow 2\times f_{i-1, s}\\ f_{i, s\cup t\cup w}&\leftarrow f_{i-1, s}\\ \end{aligned}

时间复杂度不会算，反正能过。

仙人掌

有一张无自环无重边的无向连通图，要在图上连上一些新的边，使得加边后得到的图为一棵仙人掌。总共有多少不同的加边方案。

两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。

数据范围： $n\le 5\times 10^5, m\le 10^6$ 。

我们考虑如果原图本身就不是一颗仙人掌，那无论如何都不可能是仙人掌。而如果原图中有环，那么这个环也不能被加入的边覆盖到，因为这样就不满足每个边只在一个简单环中的要求了。

因此整张图就被这些环分成了一堆部分，每个部分都是一颗树，并且每部分分开计算，因此我们就可以只考虑树的情况。

由于仙人掌中的割边不利于我们dp，我们强制让割边都连一条重边，这样就好dp了。我们设 $f_i$ 为子树内加边的方案， $g_i$ 为往上扩展一条边的方案。为了方便转移，再设 $h_i$ 为有 $i$ 个儿子时子树内连边的方案数。

首先 $h_i$ 的递推式很容易计算，我们只需考虑最后一条边是和父亲连还是子树内再找一个来配对，因此

h_i=h_{i-1}+(i-1)h_{i-2}

我们再考虑 $f$ 和 $g$ 的转移方程。

我们记 $ch$ 为儿子的个数，每个子节点向上连边是独立的，而这些子节点又是可以互相连边的，因此 $f$ 的方程为：

f_{u}=h_{ch}\times \prod \limits _{v\in son_u} g_v

再考虑 $g$ 的方程，首先 $u$ 本身可以直接向上扩展，或者是从子节点中选出一个点向上扩展，这时剩下的点其实也不影响，也可以向上扩展到 $u$ ，或者内部自己连边，因此转移方程为：

g_u=f_u+h_{ch-1}\times ch\times \prod \limits _{v\in son_u} g_v

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

猪国杀（某次模拟赛题）

给定一个长度为 $n$ 的正整数序列，其中所有数都在 $[1, A]$ 之间随机生成。得到序列后可以选择一些数且这些数的和不大于 $m$ 。如果每次都尽可能多地获得数字，那么单次期望获得多少个数。

数据范围： $n\le 100, m\le 1000, A\le 1000$ 。

我们先把问题转化为求所有序列的可以获得个数之和 $ans$ ，那么答案即为 $\frac{ans}{A^n}$ 。

我们考虑求出 $ans$ 。我们要求的是对于所有序列，它所能选的牌数之和。我们转化为对于所有牌数 $d$ ，选的牌数为 $d$ 的序列乘上 $d$ 之和。

设 $g_{i, j, k}$ 为 $i$ 个数，且这 $i$ 个数都不超过 $j$ ，并且它们的和小于等于 $k$ 的方案数。我们考虑我们把序列排序之后的样子：

我们枚举图中的 $i, j, k, t$ ，然后再让它们插入到序列中，我们就能得到下面的式子：

ans=\sum_{i=0}^{n}\sum_{j=1}^A\sum_{k=1}^{n-i}g_{i, j-1, m-j\times k}\dbinom{n}{i}\sum_{t=k}^{n-i}\dbinom{n-i}{t}(A-j)^{n-t-i}

而这里没有乘以牌数的原因是因为：我们会在每一个放置新数的位置都对这个序列记一次数，也就达到了上面乘以牌数的效果。

而对于 $g_{i, j, k}$ 的求法，我们可以用二项式反演来求：

简单地说，我们要求的简化版为下面这个式子：

x_1+x_2+\cdots +x_n=k\ \ x_i\le r

设 $f_j$ 为恰好 $j$ 个条件不满足， $g_j$ 至少 $j$ 个不满足，二项式反演可得：

f_i=\sum _{j=i}^n(-1)^{j-i}\dbinom{j}{i}g_j

先从 $n$ 个限制选 $j$ 个不满足，让这 $j$ 个变为 $x_i>r$ 。然后再减去这 $j\times r$ ，变为 $x_i>0$ 。因为 $x_i>0$ ，所以直接变为 $k-r\times j$ 个小球放 $n$ 个盒子，盒子非空的模型：

g_j=\dbinom{n}{j}\dbinom{k-r\times j-1}{n-1}

因此 $f_i=\sum _{j=i}^n(-1)^{j-i}\dbinom{j}{i}\dbinom{n}{j}\dbinom{k-r\times j-1}{n-1}$ ， $f_0=\sum _{j=0}^n(-1)^{j}\dbinom{n}{j}\dbinom{k-r\times j-1}{n-1}$

而要求的 $g_{n, r, x}$ 为和小于等于 $x$ 的方案数，可以在前面再加个 $\sum$ 。

\begin{aligned} g_{n, r, x}&=\sum_{k=1}^{x}\sum _{j=0}^n(-1)^{j}\dbinom{n}{j}\dbinom{k-r\times j-1}{n-1}\\ &=\sum _{j=0}^n(-1)^{j}\dbinom{n}{j}\sum_{k=1}^{x}\dbinom{k-r\times j-1}{n-1}\\ &=\sum _{j=0}^n(-1)^{j}\dbinom{n}{j}\sum_{k=1-r\times j-1}^{x-r\times j-1}\dbinom{k}{n-1}\\ &=\sum _{j=i}^n(-1)^{j}\dbinom{n}{j}\sum_{k=0}^{x-r\times j-1}\dbinom{k}{n-1}\\ \end{aligned}

由于 $\sum _{i=0}^n\dbinom{i}{m}=\dbinom{n+1}{m+1}$ ，所以 $g_{n, r, x}=\sum _{j=0}^n(-1)^{j}\dbinom{n}{j}\dbinom{x-r\times j}{n}$ 。

这样我们就求出来了 $g$ 。

前面那一坨为 $0$ 时可以跳过，那么复杂度可能是 $O(n^2m\log m)$ 的，我也不会算。

Three Permutations

给定两个排列 $p, q$ ，要求统计满足 $\forall i, r_i\not= p_i, r_i \not= q_i$ 的排列 $r$ 的数量。

数据范围： $n \le 3000$ 。

题目中要求的东西和错排很相似，我们考虑容斥。设 $h_i$ 为只看其中 $i$ 条限制，这 $i$ 条限制都不满足的情况数。因此答案即为 $\sum \limits_{i=0}^{n}(-1)^ih_i$ 。

现在问题转变为了如何求这个 $h$ 。我们从 $p_i$ 向 $q_i$ 连边，这样一定会出现至少一个环。第 $i$ 个位置填 $r_i$ 就意味着第 $i$ 条边对应着第 $r_i$ 个点。

而我们考虑不满足要求的情况，就是这条边正好对应着它的起点或者终点。而没有对应的情况我们就可以直接把这条边从图中删去。

在一个大小为 $n$ 的环中，如果我们删去 $i$ 条边，我们就会剩下 $i + 1$ 个连通块，如果我们在这个环上不删去任何一条边，那么就意味着这个环上每条边都对应着自己的起点或者终点。这时有两种情况：全都对应自己的起点和全都对应自己的终点，一共两种情况。

而当出现链时，我们考虑这条链上边选择点的方案数。我们可以枚举每个点，这个点左边的边全部选起点，右边的点全部选终点，这样一条链的方案数就是这条链的大小。

设 $dp[n, m]$ 为一个大小为 $n$ 的链删去 $m$ 条边的方案数，我们可以枚举第一个点所在链的大小 $i$ ，便可推出方程 $dp_{n, m}=\sum \limits _{i=1}^{n}dp_{n-i,m-1}i$ 。这样就求出了链上的情况统计。

我们再考虑环上的统计。设 $f[n,m]$ 为一个大小为 $n$ 的环删去 $m$ 条边的方案数。根据上面的分析，我们可以得到边界条件 $f[n,0]=2$ 。我们也可以像上面一样，枚举第一个点所在的连通块的大小，我们可以得到转移方程 $f_{n, m}=\sum \limits _{i=1}^{n}i^2dp_{n-i,m-1}$ 。

我们统计了一个环的情况，我们再考虑多个环。我们设 $g[n,m]$ 为前 $n$ 个环删去 $m$ 条边的方案数。枚举最后一个环删去多少条边，我们能得到转移方程 $g_{n, m}=\sum \limits _{i=1}^{v_n}g_{n-1,m-i}f_{v_n,i}$ （ $v_n$ 为第 $n$ 个环的大小）。

我们已经求出了所有环删去一些边的方案数，这时我们再考虑回去，我们会发现，删去一条边就意味着这条边不对应它的起点或终点，也就意味着它在 $r$ 排列中合法，那么减去这些删去的边，剩下的就是不满足要求的个数 $h$ 了。也就是 $h_i=g_{cnt,n-i}$ 。

但是现在我们的复杂度还是 $O(n^3)$ 。我们考虑使用前缀和优化，就可以做到 $O(n^2)$ 。

Beautiful Bracket Sequence

给定一个含 ? 的括号序列。定义一个括号序列的权值为：删除一些字符使其成为合法的字符序列后，括号匹配的最深深度。求把 ? 替换成括号的所有方案中，括号序列的权值之和。

数据范围： $n\le 10^6$ 。

我们可以先枚举最终括号匹配的中间点，然后枚举左右的括号数来计算权值，但是我们可以发现：一个括号序列最终匹配的中间点可能不只有一个，因此我们需要一个规则来防止算重。

我们先确定一个括号序列，然后设 $a_i$ 为 $[1, i]$ 这段区间内 ( 的个数， $b_i$ 为 $[i+1, n]$ 这段区间内的 ) 的个数，那么显然，这个括号序列的权值为 $\max_{i=1}^n (\min(a_i, b_i))$ 。我们考虑找到这个决策点。

我们可以发现，当我们让 $i$ 向右扫时，如果扫到了 (，那么会让 $a_i$ 加一；扫到 ) 会让 $b_i$ 减一。因此我们可以得到： $a_i$ 单调递增， $b_i$ 单调递减。我们把 $a$ 和 $b$ 的图像画出来可能就是下面的样子：

而我们要求的答案即为下图中的绿色部分。

我们可以发现， $a_i=b_i$ 为其最优决策点，且该序列的权值为当前的 $a_i$ 。

回归到最上面的问题，我们的目的是解决计算重复。显然对于一个括号序列，满足 $a_i=b_i$ 的位置有且仅有一个，那么我们可以直接在 $a_i=b_i$ 的时候来计算答案。

我们还是枚举中间点 $p$ ，设左边的 ( 有 $x$ 个，? 有 $a$ 个，右边的 ) 有 $y$ 个，? 有 $b$ 个。并且我们让左右两边的左右括号数量相等，那么我们可以列出下面的式子：

ans_p=\sum_{i=0}^a (x+i)\dbinom{a}{i}\dbinom{b}{x+i-y}

我们用这个式子可以 $O(n^2)$ 出答案，我们考虑把这个式子再推推：

\begin{aligned} ans_p&=\sum_{i=0}^a (x+i)\dbinom{a}{i}\dbinom{b}{x+i-y}\\ &=x\sum_{i=0}^a\dbinom{a}{i}\dbinom{b}{b+y-x-i}+\sum_{i=0}^a i\dbinom{a}{i}\dbinom{b}{b+y-x-i} \end{aligned}

考虑经典结论 $m\dbinom{n}{m}=n\dbinom{n-1}{m-1}$ 以及范德蒙德卷积，我们可以得到最终的式子：

ans_p=x\dbinom{a+b}{b+y-x}+a\dbinom{a+b-1}{b+y-x-1}

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

Formalism for Formalism

给出正整数 $n$ ，所有不足 $n$ 位（十进制）的数用前导零补充。

给出 $m$ 组无序数对 $(u_i,v_i)$ ，若一个数字的相邻两位数 $x,y$ 满足 $(x,y)$ 存在于这 $m$ 组数对中，则可以交换 $x,y$ 的位置。若 $A$ 可以通过若干次（包含零次）交换得到 $B$ ，则认为 $A$ 和 $B$ 是等价的。

求出最大整数 $k$ ，使得存在一组非负整数 $x_1,x_2,\ldots,x_k(0\leq x_i<10^n)$ 满足对于任意 $1\leq i<j\leq k$ ， $x_i$ 与 $x_j$ 不等价。

数据范围： $n\le 50000$ 。

本题中要对这些数字的等价类计数，我们考虑选出代表元。可以直接钦定一个等价类中，字典序最小的数为代表元。那么我们就考虑哪些数字可能成为代表元。

我们发现如果一个数存在 $i<j$ ，使得 $a_i>a_j$ 并且 $j$ 可以交换到 $i$ 这个位置，那么这个数绝对不是字典序最小的。证明是显然的。那么我们现在的目标就是：找到有多少个数满足对于每个位置都不存在在它后面可以交换到它并且比它小的数。

我们考虑 dp。我们设 $f_{i, s}$ 为当前填到了第 $i$ 位，下一位不能填 $s$ 这个集合中的数字。转移则枚举下一位填什么。我们再预处理出来 $to_{s, i}$ 来方便转移，其含义为： $s$ 中的数字不能填，下一位填 $i$ 时会转移到什么状态。 $to$ 的预处理是平凡的。

复杂度 $O(n\times 2^{10}\times 10)$ 。

Sum of SCC

考虑一张竞赛图 $G$ ，其中有 $n$ 个节点，节点编号为 $1,2,\dots,n$ 且 $G$ 满足：对于 $G$ 中的所有边 $u\to v$ ，恰好有 $m$ 条边满足 $u<v$ 。

设 $f(G)$ 表示图 $G$ 中的强连通分量数量。请你求出所有满足条件的 $G$ 的 $f(G)$ 之和。

数据范围： $1\le n\le30$ ， $0\le m\le\frac{N(N-1)}2$ 。

我们发现对强连通分量计数很难，我们考虑选取一种基本等价的方式来对强连通分量计数。

我们发现，一个竞赛图强连通分量个数等价于将这张图分为 $A, B$ 两个可空集合，且两集合之间的连边都为 $A\to B$ 的方案数减一。这个结论比较显然。

有了这个结论就可以开始 dp 了。我们设 $f_{i, j, k}$ 为 $A$ 集合有 $i$ 个点， $B$ 集合有 $j$ 个点，当前有 $k$ 条题目中要求的边的方案数。转移就考虑放入 $A$ 还是 $B$ ，可以得到：

f_{i+1, j, k+x}\leftarrow \dbinom{i}{x} f_{i, j, k}

f_{i, j+1, k+x+i}\leftarrow \dbinom{j}{x}f_{i, j, k}

最终答案即为 $\sum_{i=0}^{n-1}f_{i, n-i, m}$ 。

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

Strongly Connected Tournament

有 $n$ 个点，这些点组成一个集合。现在把集合中两两点之间连有向边，对于 $i<j$ ， $(i, j)$ 这条边出现的概率是 $p$ ， $(j, i)$ 出现的概率是 $(1-p)$ 。一共会连 $\dbinom{n}{2}$ 条边。连一条边的代价是 $1$ 。

这些边连完后对这张竞赛图进行缩点。缩点后把每一个强连通分量中的点看作一个新的集合，重新做一遍上面的连边操作以及当前的缩点操作，直到每个连通分量大小都为 $1$ 为止。

求期望代价。

数据范围： $n\le 2000$ 。

一个竞赛图缩点后一定会有一个拓扑序最小的强连通分量，我们枚举它的大小。

我们设 $f_i$ 为 $i$ 个点定向后仍然是一个强连通分量的概率， $dp_{i, j}$ 为大小为 $i$ 的图，拓扑序最小的强连通分量大小为 $j$ 个点（不考虑强连通分量内部连边）的概率。我们一个一个加入点，可以得到 $dp$ 的转移方程：

dp_{i, j}=dp_{i-1, j-1}\times (1-p)^{i-j}+dp_{i-1, j}\times p^j

根据容斥可以得到 $f_i$ 的转移方程：

f_i=1-\sum_{j=1}^{i-1}f_jdp_{i, j}

我们再设 $g_i$ 为 $i$ 个点的图期望代价，答案即为 $g_n$ ，设 $h_i$ 为已经定向过的图重新定向至结束的期望代价。

转移依旧是枚举第一个强连通分量大小，可以得到：

g_n=f_ng_n+\sum_{i=1}^n dp_{n, i}f_i (g_i+h_{n-i}) +\dbinom{n}{2}

h_n=f_ng_n+\sum_{i=1}^{n-1}dp_{n, i}f_i(g_i+h_{n-i})

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

Slalom

一个 $n \times m$ 的网格，其中有 $k$ 个矩形障碍，保证这些障碍不重叠。求从 $(1,1)$ 走到 $(n,m)$ ，每步只能往右或往上走，不经过任何障碍的方案数。

两种方案被视为不同，当且仅当存在一个障碍，它在第一种方案里被从右侧绕过，而在第二种方案里被从左侧绕过（第一种左，第二种右同理）。

数据范围： $n, m \leq 10^6$ ， $k \leq 10^5$ 。

我们发现题目中的要求让我们很难通过普通的方式计数，我们考虑选出所有等价路径中最靠下的那一条。

我们设 $f_{i, j}$ 为走到 $(i, j)$ 的方案数，转移我们可以看下图：

我们要转移 $now$ 这个点的方案，我们考虑用 $a, b, c$ 这三条路径来更新，而和 $d$ 这条路径没有关系。因此如果我们记一个点能到达的最靠下且没有障碍物的位置是 $low$ ，那么转移方程即为

f_{i. j}=\sum_{k=low}^{j}f_{i-1, k}

显然这个式子可以上线段树来优化，我们的目标就变为了找到 $low$ 。

我们可以直接用 set 维护一下线段，做一下差分即可。

时间复杂度 $O(n\log n)$ 。

Move by Prime

给你一个长度为 $n$ 的数列 $a_i$ ，你可以进行任意次操作：将其中一个数乘上或者除以一个质数。使得最终所有数相同，并使得操作数尽可能小。现在我们想要知道 $a_i$ 的所有子序列的操作数之和是多少。

数据范围： $1 \le n \leq 3 \times 10^5, 1 \le a_i \le 3 \times 10^5$ 。

我们发现每个质因子都是独立的，我们可以对每个质因数分别考虑。我们设我们当前考虑的质因数为 $p$ ，第 $i$ 个数含有 $x_i$ 个该质因数。

如果我们只对一个序列考虑，那么显然这是一个中位数问题。设中位数为 $x$ ，那么答案即为 $\sum |x_i-x|$ 。我们把这个式子的绝对值展开可以发现 $x$ 会全部被消掉，设当前考虑的数为 $i$ ，小于它的数有 $a$ 个，大于它的数有 $b$ 个，那么当 $a<b$ 时它会贡献 $x_i$ ，否则会贡献 $-x_i$ 。

那么我们可以同时枚举 $a$ 和 $b$ ，然后用范德蒙德卷积化简。但是这里提供一种更好的方法。

我们枚举 $i-1-a+b$ ，也就是小于 $i$ 的不选的个数和大于 $i$ 的选的个数之和。这样枚举我们可以发现，当 $i-1-a+b<i-1$ 时 $a>b$ ，否则 $a<b$ 。

因此可以列出 $i$ 这个数的贡献为：

x_i\left( \sum_{j=i}^{n-1}\dbinom{n-1}{j}-\sum_{j=0}^{i-2}\dbinom{n-1}{j} \right)

我们预处理 $\dbinom{n-1}{j}$ 的前缀和即可做到 $O(1)$ 计算这个式子。再枚举约数我们即可做到 $O(n\log n)$ 。

我们再考虑优化。我们发现我们可以对 $x_i$ 相同的部分一同计算，因此我们对 $\sum_{j=i}^{n-1}\dbinom{n-1}{j}-\sum_{j=0}^{i-2}\dbinom{n-1}{j}$ 做前缀和，枚举约数时类似埃氏筛，我们就可以做到 $O(n\log \log n)$ 。

Vladislav and a Great Legend

给你一棵有 $n$ 个节点的树 $T$ ， $n$ 个节点编号为 $1$ 到 $n$ 。

对于 $T$ 中每个非空的顶点的集合 $X$ ，令 $f(X)$ 为包含 $X$ 中每个节点的最小连通子树的最小边数，即虚树的大小。

再给你一个整数 $k$ 。你需要计算对于每一个顶点的集合 $X$ ， $(f(X))^k$ 之和，即：

\sum_{X\subseteq\{1,2,\dots,n\},X\neq\varnothing}(f(X))^k

数据范围： $n\le 10^5, k\le 200$ 。

我们看到 $k$ 次方可以直接上斯特林数。因此我们要求的东西就是：

\begin{aligned} \sum_{S}f(S)^k&=\sum_S \sum_{i=0}^{k}{k\brace i}i!\dbinom{f(S)}{i}\\ &=\sum_{i=0}^k{k\brace i} i!\sum_{S}\dbinom{f(S)}{i} \end{aligned}

也就是 $\sum_S \dbinom{f(S)}{i}$ 。我们进行一个组合意义，也就是在虚树内再选出 $i$ 条边的方案数。我们就可以进行一个树形 dp。我们设 $dp_{u, i}$ 为 $u$ 子树内选 $i$ 条边的方案数，转移就进行一个树上背包，注意考虑 $u\to v$ 这条边是否被选即可。

时间复杂度 $O(nk+k^2)$ 。

Centroid Probabilities

对于所有点数为 $n$ 的树，如果其满足对于所有 $i\in [2,n]$ ，与 $i$ 相连的 $j$ 中有且只有一个点 $j$ 满足 $j<i$ ，那么我们称其为好树。

对于 $1\sim n$ 每个点求出来有多少好树满足重心为 $i$ 。

这里重心定义为删去这个点后形成的所有连通块大小均不超过 $\frac{n-1}2$ 。

数据范围： $3\le n\le 2\times 10^5$ 且 $n$ 为奇数（所以不存在树有多个重心的情况）。

我们发现重心可以定义为：其子树大小大于等于 $\frac{n+1}{2}$ 且其他点的子树大小都不大于等于 $\frac{n+1}{2}$ 的点。下面我们设 $m=\frac{n+1}{2}$ 。

我们设 $f_i$ 为 $i$ 子树大小大于等于 $m$ 的方案数。我们先选出 $j$ 个点放到子树内，然后在考虑子树内外的点的放置方式，那么我们就可以得到：

f_i=\sum_{j=m}^{n-i+1}\dbinom{n-i}{j-1}(n-j+1)!(i-1)(j-1)!

我们进行一个式子的化简：

\begin{aligned} f_i&=\sum_{j=m}^{n-i+1}\dbinom{n-i}{j-1}(n-j+1)!(i-1)(j-1)!\\ &=\sum_{j=m}^{n-i+1}\frac{(n-i)!}{(j-1)!(n-i-j+1)!}(n-j+1)!(i-1)(j-1)!\\ &=(n-i)!(i-1)\sum_{j=m}^{n-i+1}\frac{(n-j+1)!}{(n-i-j+1)!}\\ &=(n-i)!(i-1)!\sum_{j=m}^{n-i+1}\dbinom{n-j+1}{n-i-j+1}\\ &=(n-i)!(i-1)!\dbinom{n-m}{n-i-m+1}\\ &=\frac{(n-i)!(n-m)!}{(n-i-m+1)!} \end{aligned}

我们就可以 $O(1)$ 求出 $f_i$ 。我们再考虑如何让这个点成为重心。我们只需要减去重心在其子树中的方案数即可。我们发现我们挂点到某个点下面是等概率的，因此我们可以直接让方案数除去 $i$ 。因此 $ans_i=f_i-\sum_{j>i}\frac{ans_j}{i}$ 。

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

Many Good Tuple Problems

对于一对长度均为 $m$ 且元素值在 $\left[1, n\right]$ 之间的序列 $(S, T)$ ，定义其为好的当且仅当：

存在一个长度为 $n$ 的 $01$ 序列 $X$ ，使得其满足如下条件：
- 对于任意 $i \in \left[1, m\right]$ ，有 $X_{S_i} \neq X_{T_i}$ 。

给定 $n, m$ ，求在所有可能的 $n^{2m}$ 种长度均为 $m$ 且元素值在 $\left[1, n\right]$ 之间的序列对 $(A, B)$ 中，有多少对序列是好的。

数据范围： $1 \le n \le 30, 1 \le m \le 10^9$ 。

本题稍微转化题意即可发现，设 $f_{n, m}$ 为 $n$ 个点 $m$ 条边的二分图数量（无重边）， $P(n, m)$ 为 $n$ 个有标号小球放入 $m$ 个有标号盒子且盒子非空的方案数，那么最终答案即为

2^m\times \sum_{i=0}^{L(n)}P(m, i)\times B_{n, i}

其中 $L(n)=\left\lceil\frac{n}{2} \right\rceil\left\lfloor\frac{n}{2} \right\rfloor$ ，即为 $n$ 个点的二分图的最大边数。其中 $2^m$ 表示数列中每个位置 $A_i$ 和 $B_i$ 都可以调换， $P(m, i)$ 表示我们规定这些边存在于图中，让这 $m$ 个未知的边放入这些边中。

我们考虑求出 $f_{i, j}$ 。我们发现我们不能通过简单的方式求出它，因为每个连通块都会有两种染色方式，但是我们最终要的二分图与染色方式无关。因此我们考虑容斥。

先设 $h_{i, j}$ 为有 $i$ 个黑白染色的点， $j$ 条边且每条边连接的两个点颜色都不同的方案数。显然可以得到 $h$ 的计算方法：

先选出 $x$ 个点染为白色，再在黑白两部分之间选择边，可以得到：

h_{i, j}=\sum_{x=0}^{y}\dbinom{i}{x}\dbinom{x(i-x)}{j}

我们再求出染色后连通二分图的数量 $g_{i, j}$ 。我们可以考虑容斥。

我们可以枚举一号点所在连通块，那么可以得到：

g_{i, j}=h_{i, j}-\sum_{k=1}^{i-1}\sum_{l=0}^{j}g_{k, l}h_{i-k,j-l}

至于为什么要求出连通图的数量，是因为一个连通图只有两种染色方式，这方便我们求出 $f$ 的值。

我们对于 $f$ 依旧枚举 $1$ 号点所在连通块，可以得到：

f_{i, j}=\frac{g_{i, j}}{2}+\sum_{k=1}^{i-1}\sum_{l=0}^{j}f_{k, l}\times \frac{g_{i-k,j-l}}{2}

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

AGC028D

给定一个圆, 圆上均等地放着 $2n$ 个点，已有 $k$ 对点之间连好了线段，从中选择剩下 $n−k$ 对点随意连线段（每个点只连一条线段）。

两点在图 $G$ 中有边当且仅当两点在同一条线段上或两点所属于的线段相交。求所有连边方案中， $G$ 中联通块的个数和。

数据范围： $n\le 300$ 。

我们考虑最终连成的圆是什么样子的（为了方便，这里把环看作链）

我们可以发现是类似一个大块内部可能包含着一个小块，考虑在一个块的边界处计算贡献。

也就是说，我们规定 $[l, r]$ 产生贡献当且仅当 $l$ 与 $r$ 连通。那么就可以设 $f_{l, r}$ 为 $l, r$ 内部连边，且 $[l, r]$ 连通的方案数。我们再设 $g_{x}$ 为 $x$ 个点相互连边的方案数。

显然当 $x$ 为奇数时 $g_x=0$ ，当 $x$ 为偶数时 $g_{x}=1\times 3\times 5\times\cdots\times (x-1)$ 。

对于 $f$ ，可以进行一个容斥。类似图计数，可以枚举第一个断点，右边随便连，左边为一个连通块。那么可以得到转移：

f_{l, r}=g_{cnt}-\sum_{k=l}^{r-1}f_{l, k}\times g_{k+1,r}

答案即为 $\sum_{l\le r} f_{l, r}g_{other}$ 。

对于初始连的 $k$ 条边的处理是简单的，不再赘述。

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

AGC027E

给定一个只含小写字母 $\mathtt{a}, \mathtt{b}$ 的字符串 $s$ ，每次你可以执行以下两种操作：

选取 $s$ 中连续的两个字符 $\mathtt{aa}$ ，把它们删去，替换成一个字符 $\mathtt{b}$ 。
选取 $s$ 中连续的两个字符 $\mathtt{bb}$ ，把它们删去，替换成一个字符 $\mathtt{a}$ 。

求出执行若干次操作后，能够得到的本质不同的字符串 $t$ 有多少个。

数据范围： $1 \le |s| \le {10}^5$ 。

可以类似 CF1421E 的思路，把 $a$ 的权值设为 $1$ ， $b$ 的权值设为 $2$ ，那么每次操作在 $\bmod 3$ 意义下权值是不会改变的。

同时也可以用数学归纳法证明：除去 $\texttt{ababab}\cdots$ 这种情况，当一段区间的权值为 $1$ 时可以变为 $a$ ，权值为 $2$ 时可以变为 $b$ 。

接下来考虑如何计数。为了避免算重，我们可以规定让 $t$ 贪心的选择最前面的一段区间。具体的，设 $f_i$ 为 $t$ 贪心的匹配到了第 $i$ 个位置的方案。转移即可考虑找到后面第一段权值为 $1$ 或 $2$ 的区间。这里不用考虑 $a, b$ 交错的情况，因为是贪心的选择，那么我们一定会选择最开头的那一个字符，又因为 $ababab\cdots$ 的权值为 $0$ ，只有出现重复字符时才会改变权值，因此这么选择是正确的。

再考虑如何统计答案。这里给出结论：当 $[i+1,n]$ 这段区间的权值为 $0$ 且字符串不为 $a, b$ 相间时， $[i+1, n]$ 可以被缩掉。可以考虑画图理解：

首先如果 $[i+1, n]$ 不为 $a, b$ 相间，那么w可以让它和前面的一个字符合并起来。根据我们上面的结论（权值对应字符），它不会改变前一个字符，同时还会让自己这段消失。

而当后面那一段为 $a,b$ 相间时，如果最后一个字符是由一段区间缩成的，那么显然可以带上最后一段一块缩。否则这个字符为一个单个字符，那么由于最后一段权值为 $0$ 且不与前面的字符相同，可以得到字符串最后一个字符与该字符相同。那么就直接把这一段权值为 $0$ 的区间前移，最后一个字符改到最后即可。至于前移的区间就可以交给前面的字符了，由于字符串不为 $a,b$ 相间，那么前面一定会得到一种终止情况。

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

AGC024E

给定 $n,k,m$ ，问有多少个序列组 $(A_0,A_1,…,A_n)$ 满足：

序列 $A_i$ 的元素个数为 $i$ 。
所有元素都在 $[1,k]$ 内。
$\forall i\in[0,n)$ ， $A_i$ 是 $A_{i+1}$ 的子序列且 $A_i$ 的字典序小于 $A_{i+1}$ 。

数据范围： $n, k\le 300$ 。

我们可以把子序列这个条件看作是每次在序列中插入一个数。可以发现第一个插入的数是比较特殊的（不受任何字典序限制），我们设其为 $x$ ，那么我们可以找出在插入过程中最靠左的那一条 $x$ 。如图：

首先由于找出来的是最靠左的一条 $x$ 的链，那么所有的 $a$ 都不等于 $x$ 。其次由于字典序的限制，所有的 $a$ 都必须大于 $x$ （否则当在左边插入时会把一个 $a$ 顶到上面 $x$ 的位置），同时还要保证 $a$ 这些的字典序不会减小。而对于 $b$ ，可以发现其与 $x$ 并无联系，只需满足字典序不变小即可。

那么就可以进行一个 dp 了。设 $f_{i, j}$ 为填 $i$ 层，其中填的数都大于等于 $j$ 的方案数。转移就枚举在左边插入多少次，同时再枚举一个 $x$ 即可。

f_{i, j}=\sum_{t=0}^{i-1}\sum_{x=j}^{k}f_{t, x+1}\times f_{i-t-1, j}\times \dbinom{i-1}{t}

然后随便前缀和优化一下就行。时间复杂度 $O(n^3)$ 。

AGC022F

数轴上有 $n$ 个点，第 $i$ 个点的坐标为 $(100^{100})^i$ 。

进行 $n-1$ 次操作，每次操作选择两点 $A$ 和 $B$ ，将 $A$ 移动到 $A$ 关于 $B$ 的对称的位置并删去 $B$ 。求最后剩下的一个数有多少种可能的取值。

数据范围： $n\le 50$ 。

首先可以发现 $100^{100}$ 远大于 $2^n$ ，因此最终的坐标可以看作 $x_1,x_2\cdots$ 的线性组合。考虑如果 $A$ 跳过 $B$ ，那么我们就让 $B$ 成为 $A$ 的儿子。最终根节点即为最后剩下的数，可以被表示为 $\sum c_i\times 2^{dep_i}\times x_i$ ，其中 $c_i\in \{-1, 1 \}$ 。

考虑一个点的 $c$ 将会被什么改变：在它挂到叶子之前它的父亲挂了几个叶子、它父亲的 $c$ 、以及这个节点儿子个数的奇偶性。假设当前节点 $u$ 的符号为 $\mathrm{sign}$ ，那么当它有奇数个儿子时，它会多出一个符号为 $-\mathrm{sign}$ 的的儿子，剩下的儿子一半是 $\mathrm{sign}$ ，一半是 $-\mathrm{sign}$ 。

至于最终位置中深度的问题，我们可以按层 dp。同时为了考虑到符号问题，我们还要在状态中记录一维有多少有奇数个儿子的点。因此设 $f_{i, j}$ 为已经放了 $i$ 个点，最后一层中有 $j$ 个点钦定有奇数个儿子。枚举下一层放 $k$ 个点，先让这 $j$ 个点的儿子中放一个，然后剩下的点的符号是对半分的。因此当前有 $\frac{k-j}{2}$ 个符号和父亲相同的点以及 $\frac{k-j}{2}$ 个符号和父亲不同的点。再考虑下下层的影响，我们钦定有 $p$ 个点与其父亲不同，那么需要至少让 $|\frac{k-j}{2}-p|$ 个点拥有奇数个儿子。

其实也可以让 $|\frac{k-j}{2}-p|+2w$ 个点拥有奇数个儿子。但是我们只关心儿子是否和父亲符号相同，同时钦定更多有奇数个儿子的点只会让下一层的限制变多。因此取到最小值时就包含了所有的情况。

所以转移为：

f_{i+k, |\frac{k-j}{2}-p|}\leftarrow f_{i, j}\times \dbinom{n-i}{k}\times \dbinom{k}{p}

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

CF468E

给定一个 $n\times n$ 的矩阵，初始时矩阵的每个元素都为 $1$ 。

又给出 $k$ 个三元组 $(x,y,z)$ ，表示将矩阵的 $(x,y)$ 位置变成 $z$ 。

你需要求出完成这些变换之后矩阵的积和式。。

积和式的定义：

per(A)=\sum_{\pi}\prod_{i=1}^na_{i,\pi(i)}

其中 $\pi$ 取遍全部 $1\sim n$ 共 $n!$ 个排列。

数据范围： $n\le 10^5, k\le 50$ 。

考虑积和式的图论意义：定义一个完美匹配 $S$ 的权值为 $val(S)=\prod_{e\in S} w_e$ ，那么积和式就表示所有完美匹配的权值之和。先把边权不为 $1$ 的边拆为一条 $w-1$ 的边以及一条权值为 $1$ 的边，由于边权为 $1$ 的边不会对权值有影响，那么只需要求出所有的匹配，假设一个匹配中选择了 $x$ 条边，权值为 $v$ ，那么这个匹配的贡献即为 $(n-x)!\times v$ （剩下的 $1$ 随便选）。

现在的目标就是求出所有匹配的权值和。首先可以对每个连通块分别考虑，然后做背包即可。对于一个连通块，我们可以状压一侧点是否被选，同时枚举另一侧的点去连边来计算权值和。这个做法可以被一个一边有 $25$ 个点，另一边有 $26$ 个点的二分图卡掉。时间复杂度最差为 $O(n^22^\frac{n}{2})$ （ $n$ 为点数）。

另一种做法：可以求出这个连通块的一颗生成树，然后状压非树边是否被选，然后进行一个树上背包即可。时间复杂度 $O(n^22^{m-n})$ （ $m$ 为边数）。

可以对这两个算法结合一下，当 $m>\frac{3n}{2}$ 时使用第一种做法，否则使用第二种做法，那么复杂度为 $O(n^22^{\frac{n}{3}})$ 。

gym103371I

有一个大小为 $n \times m$ 的大网格，其中每个网格单元要么是有色的，要么是无色的。

crimson000 想在一些未着色的单元格中放入一些彩色纸。crimson000 选择两个整数 $w, h$ ，其中 $1 \le w \le m, 1 \le h \le n$ 。然后，crimson000 用宽度为 $w$ 和高度为 $h$ 的彩色纸覆盖网格，满足以下条件。

彩色纸应恰好覆盖网格单元，并且不超出网格。
彩色纸无法旋转。
一个单元格可以覆盖不止一张彩纸。
每个未着色的单元格必须至少覆盖一张彩色纸。
任何彩色纸都不能覆盖有色格子。

根据彩色纸宽度和高度的选择，crimson000 可能无法覆盖满足上述条件的网格。请计算可以覆盖整张网格并满足上述条件的可能纸张尺寸的数量。

数据范围： $n, m\le 3000$ 。

我们定义一个格子合法为：有一个方格纸可以覆盖到这个点。

这里直接给出性质：一个彩色纸能够覆盖网格当且仅当所有有色格子周围的格子全部合法。证明如下：

假设所有有色格子周围的格子都合法，但是有某个周围没有障碍的格子不合法（合法记为 O，不合法记为 X，障碍记为 #），那么找到这个不合法格子的连通块，一定会有一个合法的格子与这个连通块相邻，假设其在连通块上方，那么将这个格子所在的彩色纸往下推一格，由于下面的格子不合法，那么新扩展的这一行一定是形如 XO...O# 的，但是可以发现在 # 旁边的 O 所在的彩色纸是可以覆盖到这个不合法的格子的，于是得证。

那么就可以从每个障碍物上下左右开始扫，这里举向右扫的例子：枚举矩形长度，然后用上下的障碍物来卡住这个矩形的高度 $h'$ 。那么在 $w\in[len+1,n], h\in [h',m]$ 的矩形都是不合法的。

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

CF1601F

有一个数列 $a$ 是一个 $1\sim n$ 的排列，且所有的数都按照字典序排序，求 $(\sum_{i=1}^{n}((i-a_i)\bmod 998244353))\bmod 10^9+7$ ，注意这里的 $x\bmod y$ 的结果为正数。

数据范围： $n\le 10^{12}$ 。

先把式子转化一下：设 $b_i$ 为 $i$ 的字典序排名，那么式子转化为求：

(\sum_{i=1}^{n}((b_i-i)\bmod 998244353))\bmod 10^9+7

看到 $n\le 10^{12}$ ，可以考虑折半搜索。一个显然的性质是：设 $x=p\times 10^6+q$ ，那么 $b_x=b_{p\times 10^6}+b_q$ 。因此 $b_i-i$ 即为 $(b_{p\times 10^6}-p\times 10^6)+(b_q-q)$ 。考虑先预处理搜索出右边的部分之和，然后对左半部分进行搜索即可。

同时为了防止算重，我们可以在左半部分正好顶到上界时统计答案，具体细节比较多。

时间复杂度 $O(\sqrt n\log n)$ 。

AGC021F

现有一个 $n$ 行 $m$ 列的、仅包含黑白格的表格，左上为 $(1, 1)$ ，右下为 $(n, m)$ 。对于一个表格，设长度为 $n$ 的数列 $A$ ，长度为 $m$ 的数列 $B$ 、 $C$ 分别表示：

$A_i$ 表示第 $i$ 行第一个黑格的列号。若不存在则为 $m+1$ 。
$B_i$ 表示第 $i$ 列第一个黑格的行号。若不存在则为 $n+1$ 。
$C_i$ 表示第 $i$ 列最后一个黑格的行号。若不存在则为 $0$ 。

求出所有的 $2^{nm}$ 种表格中，不同的数列三元组 $(A,B,C)$ 的个数对 $998244353$ 取模的结果。

数据范围： $1 \leq n \leq 8 \times 10^3$ ， $1 \leq m \leq 200$ 。

设 $f_{i, j}$ 为考虑前 $j$ 列，当前已经有 $i$ 行中有过黑格子所能生成的序列方案数。那么最终答案即为 $\sum_{i=0}^{n}\dbinom{n}{i}f_{i,m}$ 。

显然初始状态为 $f_{i, 1}=1$ ，因为这时每一行都必须染黑。考虑从 $f_{k, j-1}$ 转移到 $f_{i, j}$ ，也就是在第 $j$ 列放入 $i-k$ 个之前没有放过的位置。

进行一个分类讨论：

当 $i=k$ 时，这些行之前都被放过，那么 $A$ 数组是不会变的，只需考虑 $B, C$ 数组即可。因此有三种情况：这一列不放、放一个（ $B_j=C_j$ ），以及放大于等于两个（ $B_j<C_j$ ），因此转移系数为 $1+\dbinom{i}{1}+\dbinom{i}{2}$ 。
当 $i>k$ $i > k$ 时，这种情况比较复杂。首先新多出来的 $i-k$ $i - k$ 行是一定要放黑格子的，同时为了让 $A$ $A$ 不相同，可以先把原来 $k$ $k$ 行也都拆出来，然后在 $i$ $i$ 行中选择 $i-k$ $i - k$ 行在第 $j$ $j$ 列放黑格子，然后剩下的列再按顺序放回去。但这样只解决了 $A$ $A$ 的问题，由于之前放过黑格子的列这一列其实也还可以放，因此 $B,C$ $B, C$ 可能是由原来的列贡献的。因此还需要再分讨。
- 当最大值和最小值都由这新增的 $i-k$ 行贡献时，转移系数即为上文中所说的 $\dbinom{i}{i-k}$ 。
- 当最值其中之一为原有的行贡献时，可以考虑构建一个双射：选择出 $i-k+1$ 行，就钦定最下面（最上面）的一行为原有的一行。可以发现这确实是一个双射，由于有最大值最小值，转移系数为 $2\dbinom{i}{i-k+1}$ 。
- 当最值都为原有的行贡献时，同上构建双射即可，转移系数为 $\dbinom{i}{i-k+2}$ 。
因此这种情况的转移系数为 $\dbinom{i}{i-k}+\dbinom{i}{i-k+1}+\dbinom{i}{i-k+2}$ ，用组合数递推式可以化简为 $\dbinom{i+2}{i-k+2}$ 。

因此转移为 $f_{i,j}=f_{i,j-1}\times \left(1+\dbinom{i}{1}+\dbinom{i}{2}\right)+\sum_{k=0}^{i-1}f_{k,j-1}\times \dbinom{i+2}{i-k+2}$ 。

时间复杂度为 $O(n^2m)$ ，把右边的求和用 NTT 优化即可做到 $O(nm\log n)$ 。

AGC017F

给定一个 $n$ 层的三角形图，第 $i$ 层有 $i$ 个节点。第 $i$ 层的节点，从左到右依次标号为 $(i, 1), (i, 2), \ldots , (i, i)$ 。

你需要从 $(1, 1)$ 往下画 $m$ 条折线。对于每条折线的每一个小段，你可以从 $(i, j)$ 画到 $(i + 1, j)$ 或者 $(i + 1, j + 1)$ 。同时你还必须保证第 $i$ 条折线的任何一个位置必须不能处在第 $i - 1$ 条折线的左侧，它们必须按照从左到右的顺序排列。

有 $k$ 条限制，每条限制形如 $(A_i, B_i, C_i)$ ，表示第 $A_i$ 条折线处于位置 $(B_i, j)$ 时，下一小段必须走向 $(B_i + 1, j + C_i)$ ，也就是当 $C_i = 0$ 时向左，当 $C_i = 1$ 时向右。求不同的折线画法的方案数。

数据范围： $n,m\le 20$ 。

首先显然的做法是状压线的左右走向，然后每次枚举上一条线以及这一条线的走法，复杂度为 $O(4^n\mathrm{poly}(n,m))$ 。

可以考虑进行一个轮廓线 dp，每次仅转移折线走的一步。具体的，我们设 $f_{i, j, s, d}$ 为转移了前 $i$ 条折线，当前这条折线转移了前 $j$ 层，目前折线的走法为 $s$ 的前 $j$ 位，上一次的走法为 $s$ 的后 $n-j$ 位，当前与上一次的折线相差距离为 $d$ ，转移显然，复杂度 $O(n^2m2^n)$ 。

考虑优化状态，其实根本没有必要记录 $d$ 这一维，而可以选择在转移的过程中动态维护分界线。可以规定一个假想的分界线，当前这条折线的所有走法都是贴合这条折线的。为了维护这条分界线，可以进行一个分类讨论。

分界线向右

此时只需要向右走，无需改变分界线形状。
分界线向左且当前选择向左走

同上。
分界线向左且当前选择向右走

这时需要画图来直观理解。

图中黑色细线为原本的分界线，此时向右转移，分界线变为红色。设向右走为 $1$ ，向左走为 $0$ ，那么新分界线的状态即为去掉当前状态后 $n-j$ 位中最低位的 $1$ 。于是就可以进行转移。

对于 $k$ 条限制的处理是简单的，不再赘述。

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

Luogu 4590

给定长度为 $k$ 的字符串 $s$ ，对于每个 $i$ ，求有多少个长度为 $n$ 的字符串 $t$ 满足：

$t$ 与 $s$ 的最长公共子序列长度为 $i$ 。
$t$ 中不能包含 $\texttt{NOI}$ 子串。
$t$ 的字符集只有 $\texttt{N,O,I}$ 。

数据范围： $n\leq1000,k\leq15$ 。

考虑 dp，首先不出现 $\texttt{NOI}$ 的限制是好处理的，直接在状态中加入一个和 $\texttt{NOI}$ 匹配长度的维度即可。

一个朴素的想法是设 $f_{i, j, l}$ 为填了前 $i$ 个位置，与 $s$ 的最长公共子序列为 $j$ ，与 $\texttt{NOI}$ 匹配长度为 $l$ 的字符串数量，但是可以发现最长公共子序列的转移其实是错误的，我们这里实际是在贪心的匹配，而不是在使用 dp 求最长公共子序列，因此是错误的。

为了正确的求出最长公共子序列，可以考虑直接把一整个 dp 数组放到状态里来转移。设 $g_{i, j}$ 为 $t$ 的前 $i$ 个字符和 $s$ 的前 $j$ 个字符的最长公共子序列，可以发现第二维只有 $15$ 个数，但是仍然放不进状态里。不过由于 $g_i$ 的差分数组都不超过 $1$ ，因此可以状压差分。

最终设状态为 $f_{i,G_i,l}$ 表示前 $i$ 个位置填了，当前和 $s$ 的最长公共子序列的 dp 数组为 $G_i$ ，与 $\texttt{NOI}$ 的匹配长度为 $l$ 的方案，转移分讨即可。

时间复杂度 $O(nk2^k)$ 。

LOJ 6089

crimson000 有一个大小为 $n$ 的背包，并且有 $n$ 种物品。对于第 $i$ 种物品，共有 $i$ 个可以使用，并且对于每一个 $i$ 物品，体积均为 $i$ 。求 crimson000 把该背包装满的方案数为多少。

定义两种不同的方案为：当且仅当至少存在一种物品的使用数量不同。

数据范围： $n\le 10^5$ 。

可以发现：体积大于 $\sqrt n$ 的物品绝对不可能被选完。因此体积大于 $\sqrt n$ 的物品可以构成一个完全背包。

由此可以进行根号分治。对于小于 $\sqrt n$ 的物品，进行普通的多重背包以及前缀和优化即可。

对于大于等于 $\sqrt n$ 的物品，可以进行这样两种操作：加入一个体积为 $\sqrt n$ 的物品、所有加入的物品的体积都加一。可以发现这样两种操作后形成的选择序列是一一对应的。

最后把前后两部分卷积合并即可。

时间复杂度 $O(n\sqrt n)$ 。

Luogu 6624

给定一个 $n$ 个顶点 $m$ 条边（点和边都从 $1$ 开始编号）的无向图 $G$ ，保证图中无重边和无自环。每一条边有一个正整数边权 $w_i$ ，对于一棵 $G$ 的生成树 $T$ ，定义 $T$ 的价值为： $T$ 所包含的边的边权的最大公约数乘以边权之和，即：

val(T)=\left(\sum\limits_{i=1}^{n-1} w_{e_i}\right) \times \gcd(w_{e_1},w_{e_2},\dots,w_{e_{n-1}})

其中 $e_1,e_2,\dots,e_{n-1}$ 为 $T$ 包含的边的编号。

求出 $G$ 的所有生成树 $T$ 的价值之和。

数据范围： $n\le 50$ 。

莫反的步骤显然，掠过。

考虑如何求出 $\sum_{T\in Tree} \sum_{i=1}^{n-1}w_i$ 。可以每条边附一个边权为 $1+w_ix$ ，其中 $x$ 为形式变元。这样相乘会得到： $(1+w_ix)(1+w_jx)\equiv 1+(w_i+w_j)x\pmod {x^2}$ 。这样就可以用矩阵树定理求出边权之和了。

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

可以扩展到 $k$ 次方和，具体见这里。

CF578F

在一个 $n \times m$ 的网格中，每个格子里都有一个呈 \ 或 / 状的镜子。

一个合法的网格需要满足从任意一个边界段垂直射进网格中，光线会从相邻的边界段射出，同时网格中的每一段都被至少一条光线穿透。

现在网格中有 $k$ 个位置的镜子形状不确定，求有多少种合法的网格。

数据范围： $n,m \le 100$ ， $k \le 200$ 。

将点黑白染色，那么一个镜子可以看作一条连接两个黑点或者两个白点的边。

题目中的条件转化一下：

每个位置都被照射到过一次：镜子不能成环。
都从相邻位置照射出去：某类点生成的图是一个连通图。这点证明需要画图理解，这里略过。

然后矩阵树定理即可，由于黑点白点不能同时连通，因此两次求完加起来即可。

时间复杂度 $O(k^3)$ 。

gym102978A

给定 $n,m,k,r,c,v$ 求满足下述条件的大小为 $n\times m$ ，矩阵里面元素值域为 $[1,k]$ 的矩阵个数。

每行元素单调不降。
每列元素单调不降。
$a_{r,c}=v$ 。

数据范围： $n,m\le 200,k\le 100$ 。

先考虑没有 $a_{r, c}=v$ 的限制怎么做，可以考虑把每一次值域的分界线从 $(n, 0)$ 画到 $(0, m)$ ，那么可以发现分界线是不会互相越过的，可以考虑 LGV 引理。但是由于路径可以相交，还需要平移一下，将第 $i$ 条折线平移到 $(n+i,i)\to (i,m+i)$ 。就可以使用 LGV 引理求方案了。

现在有了 $a_{r, c}=v$ 的限制，这规定点 $p=(r+v-2,c+v-2)$ ，也就是规定的单元格的左上角上面必须有 $v-1$ 条折线经过它。注意这里不能经过 $p$ 点，因为平移后会多出 $k-1$ 行 $k-1$ 列，强制钦定擦除掉一条折线右下角的第一个和它形状相同的列，得到的就是原来的折线分布。

可以设形式变元 $x$ ，那么经过点 $p$ 之上的边权可以设为 $x$ ，那么最终得到的权值是一个多项式，其 $x^{v-1}$ 的系数即为答案。

由于多项式次数最高只有 $k-1$ ，可以暴力直接拉格朗日插出来整个多项式。

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

CF960G

给你三个正整数 $n$ ， $a$ ， $b$ ，定义 $A$ 为一个排列中是前缀最大值的数的个数，定义 $B$ 为一个排列中是后缀最大值的数的个数，求长度为 $n$ 的排列中满足 $A = a$ 且 $B = b$ 的排列个数。

数据范围： $n \le 10^5$ 。

$n$ 肯定是特殊的，它放了之后左边看不见右边，右边也看不见左边。因此以 $n$ 为分界线。

考虑一个前缀最大值段（也就是一个前缀最大值到下一个前缀最大值之前），假设长度为 $x$ ，那么这一段的排列方式有 $(x-1)!$ 种，固定最大值放最前面然后后面随便排即可。

这个方案和第一类斯特林数是相同的，又由于两边一共有 $a+b-2$ 个最大值段，还要乘一个组合数，因此最终答案为： ${n-1\brack a+b-2}\times \dbinom{a+b-2}{a-1}$ 。

第一类斯特林数求法略过。

BZOJ4671

定义两个结点数相同的图 $G_1$ 与图 $G_2$ 的异或为一个新的图 $G$ ，其中如果 $(u,v)$ 在 $G_1$ 与 $G_2$ 中的出现次数之和为 $1$ ，那么边 $(u,v)$ 在 $G$ 中，否则这条边不在 $G$ 中。

现在给定 $s$ 个结点数相同的图 $G_{1\sim s}$ ， $S={G_1,G_2,\cdots,G_s}$ ，请问 $S$ 有多少个子集的异或为一个连通图？

数据范围： $n\le 10, s\le 60$ 。

设 $f_i$ 为分成 $i$ 个集合，集合之间互不连边，内部随意的方案数， $g_i$ 为分成 $i$ 个集合，集合之间互不连边，内部连通的方案数。可以得到：

f_m=\sum_{i=m}^{n}{i\brace m}g_i

根据斯特林反演可得：

g_m=\sum_{i=m}^n (-1)^{i-m}{i\brack m}f_i

所求即为 $g_1$ 。

考虑求 $f_i$ 。可以对点进行集合划分，那么有的边就直接确定了，解异或方程组即可。

复杂度是贝尔数。

Luogu 10060

你有一棵 $n$ 个点的无根树，节点的编号为 $1, 2, \ldots, n$ 。定义树上两点之间的距离 $\operatorname{dis}(i, j)$ 为树上 $i$ 点到 $j$ 点的简单路径上的边数。

现在有 $k$ 个关键点 $a_1, a_2, \ldots, a_k$ ，对于每个点，我们想求出距离它最近的关键点是哪个点。也就是对于一个点 $v$ ，令 $f(v)$ 表示令 $\operatorname{dis}(v, a_i)$ 最小的 $i$ ，如果有多个 $i$ 满足条件，那么我们会选择其中最小的 $i$ 。

现在，我们给出了 $f(1), f(2), \ldots, f(n)$ ，问有多少组可能的 $(a_1, a_2, \ldots, a_k)$ 满足条件。由于答案可能很大，输出对 $998244353$ 取模的结果。

数据范围： $2 \le k \le n \le 3 \times {10}^3$ ， $1 \le f(i) \le k$ 。

下文记 $a_u$ 为题目中的 $f(u)$ 。

显然相同颜色的点会形成一个连通块，考虑这个连通块的关键点放在哪里即可。

设 $f_{i, j,0/1}$ 表示 $i$ 距离和它同色的关键点距离为 $j$ 时其子树的方案数， $0/1$ 表示 $i$ 的儿子中是否存在一个点距离关键点距离为 $j-1$ 。显然如果关键点在 $i$ 子树内时最后一维为 $1$ ，否则关键点不在 $i$ 子树中。

转移可以分第三维为 $0/1$ 两种情况。

当第三维为 $0$ 时，让子树中同色的全部第二维为 $j+1$ 然后乘起来，对于不同色的可以分两种情况讨论，记这个不同色的儿子为 $v$ ，当前点为 $u$ 。当 $a_u<a_v$ 时，可以取 $f_{v, j,1}$ 和 $f_{v, j-1,1}$ ，因为这两种情况不会让 $v$ 变为和 $u$ 同色，也不会让 $u$ 变得和 $v$ 同色。对于 $a_u>a_v$ 的情况同理，选择 $f_{v,j,1}$ 和 $f_{v, j+1,1}$
当第三维为 $1$ 时，枚举哪个儿子选择 $j-1$ ，同时记录上面讨论情况的前缀积和后缀积即可转移。

时间复杂度 $O(n^2)$ ，细节比较多。

计数杂题

未完待续，持续更新