搞一点计数题放在这，看到有意思的计数就更（虽然在组合数学那已经更了好多了）。
[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)$。