结论

生成函数相关

结论

$$ \begin{aligned} \sum_{n\ge 0}\binom{c+n}{c}z^n&=\dfrac{1}{\left(1-z\right)^{c+1}} \\ \sum_{n\ge 0} n^mz^n&=\sum_{k}\left\{\begin{matrix}m\\k\end{matrix}\right\}\dfrac{k!z^k}{\left(1-z\right)^{k+1}} \\ e^{e^z-1}&=\sum_{n\ge 0}Bell_nz^n \\ \dfrac{z}{e^z-1}&=\sum_{n\ge 0}B_nz^n \\ \sum_{n\ge 0} \dfrac{1}{n+1}\binom{2n}{n}z^n&=\dfrac{1-\sqrt{1-4z}}{2z} \\ \end{aligned} $$

方法

$$ \begin{aligned} \mathcal{A}=\operatorname{\mathcal{Sequence}}\left(\mathcal{B}\right)&\rightarrow A\left(z\right)=\dfrac{1}{1-B\left(z\right)}\\ \mathcal{A}=\operatorname{\mathcal{Multiset}}\left(\mathcal{B}\right)& \rightarrow A\left(z\right)=\left\{\begin{matrix}\displaystyle\prod_{n\ge 1}\left(1-z^n\right)^{-B_n}\\\displaystyle \exp\left(\sum_{k=1}^{\infty}\dfrac{1}{k}B\left(z^k\right)\right)\end{matrix}\right. \\ \mathcal{A}=\operatorname{\mathcal{PowerSet}}\left(\mathcal{B}\right)& \rightarrow A\left(z\right)=\left\{\begin{matrix}\displaystyle\prod_{n\ge 1}\left(1+z^n\right)^{B_n}\\\displaystyle \exp\left(\sum_{k=1}^{\infty}\dfrac{\left(-1\right)^{k-1}}{k}B\left(z^k\right)\right)\end{matrix}\right. \end{aligned} $$

$\mathcal{Powerset}$ 即为对一类对象的无顺序 $01$ 背包，$\mathcal{Multiset}$ 即为对一类对象的多重背包，$\mathcal{Sequence}$，顾名思义，是序列化构造，即若干个对象排成一行。

$\mathcal{Multiset}$ 证明：

$$ \begin{aligned} A\left(z\right)&=\prod_{n\ge 1}\left(1-z^n\right)^{-B_n} \\ &=\exp\left(\sum_{n\ge 1} -B_n\ln\left(1-z^n\right)\right) \\ &=\exp\left(\sum_{n\ge 1}B_n\sum_{k\ge 1}\dfrac{1}{k}z^{nk}\right) \\ &=\exp\left(\sum_{k=1}^{\infty}\dfrac{1}{k}B\left(z^k\right)\right) \end{aligned} $$

$\mathcal{PowerSet}$ 同理

例：付公主的背包
有 $n$ 件物品，求组成重量为 $\left[1,m\right]$ 的物品的方案数

裸题，用上面式子求出 $\exp$ 前的每项系数然后直接 $\exp$ 即可，复杂度调和级数加求 $\exp$ 复杂度，$\mathcal{O}\left(n\log_2n\right)$

例：好图计数
归纳定义“好的”无向简单图：
单点
每个连通块都是好图
好的图的补图
求无标号无向简单图的个数 $1\le n\le 23333$，模数 $p$ 满足 $2^{29}<p<2^{30}$ 且为素数

首先，不存在 $n\ge 2$ 个点的好图使得自身和自身的补图都是连通的

那么 $n\ge 2$ 个点的只有一个连通块的补图和 $\ge 2$ 个连通块的补图的数量是相等的

设 $F\left(z\right)$ 是只有一个连通块的好图的生成函数

那么 $F\left(z\right)=\mathcal{Multiset}\left(F\left(z\right)\right)-1$

由于 $\exp$ 可以用组合意义 $\mathcal{O}\left(n^2\right)$ 做，而且这个做法是半在线的，那么就可以半在线的解决原问题了。

常用组合恒等式

$$ \begin{aligned} x^n&=\sum_{k}\left\{\begin{matrix}n\\k\end{matrix}\right\}x^{\underline{k}}=\sum_{k}\left\{\begin{matrix}n\\k\end{matrix}\right\}\left(-1\right)^{n-k}x^{\overline{k}} \\ x^{\underline{n}}&=\sum_k\left[\begin{matrix}n\\k\end{matrix}\right]\left(-1\right)^{n-k}x^k\\ x^{\overline{n}}&=\sum_k\left[\begin{matrix}n\\k\end{matrix}\right]x^k \\ \left\{\begin{matrix}n\\m\end{matrix}\right\}&=\dfrac{1}{m!}\sum_{k}\binom{m}{k}\left(-1\right)^{m-k}k^n \\ \sum_{k\le n}\binom{m+k}{k}&=\binom{m+n+1}{n} \\ \sum_{0\le k\le n}\binom{k}{m}&=\binom{n+1}{m+1} \\ \sum_{k}\binom{n}{k}\binom{m}{t-k}&=\binom{n+m}{t} \\ \sum_{k}\binom{q-k}{m}\binom{p+k}{n}&=\left[z^{p+q-m-n}\right]\dfrac{1}{\left(1-z\right)^{m+1}}\cdot\dfrac{1}{\left(1-z\right)^{n+1}}\\ &=\binom{p+q+1}{m+n+1} \end{aligned} $$

常用反演

二项式反演

$$ \sum_{m\le n}\binom{n}{m}\left(-1\right)^{n-m}\left(\sum_{k\le m}\binom{m}{k}f\left(k\right)\right)=f\left(n\right) $$

子集反演

$$ \sum_{T\subseteq S}\left(-1\right)^{\left|S\right|-\left|T\right|}\sum_{V\subseteq T}f\left(V\right)=f\left(S\right) $$

常用容斥

容斥的本质就是对于每种状态分配一个系数，使得最后的结果中每个状态被计算了正确的次数

段长 $\le k$

$$ \begin{aligned} \dfrac{1}{1-F\left(z\right)}&=\sum_{i=0}^{k-1}z^i=\dfrac{z^k-1}{z-1}\\ F\left(z\right)&=\dfrac{z^k-z}{z^k-1} \end{aligned} $$

例：LOJ P3395 「2020-2021 集训队作业」Yet Another Permutation Problem
给定 $n$，对于 $1\le k\le n$ ，求有多少个排列的极长的上升子串的最大长度大于等于 $k$，$n\le 2000$，对 $m$ 取模，保证素数

容斥系数的 $OGF$ 是 $\frac{z^k-z}{z^k-1}$ ，那么假设 $EGF$ 是 $G\left(z\right)$，那么答案就是 $\left[\frac{z^n}{n!}\right]\frac{1}{1-G\left(z\right)}$，由于 $G\left(z\right)$ 非零系数的位置和 $F\left(z\right)$ 一样，只有 $\frac{n}{k}$ 个，所以可以 $\mathcal{O}\left(\frac{n^2}{k}\right)$ 递推计算，总复杂度调和级数 $\mathcal{O}\left(n^2\ln n\right)$

例：GYM 103505C The revenge of GrandPaPà
给定 $n$，对于 $1\le k\le n$ ，求有多少个排列的极长的值域连续的上升子串的最大长度恰为 $k$，$n\le 2000$，使用科技可以做 $n\le 10^5$，且要求对答案 $\bmod p$ ，$p$ 不一定是个素数

首先我们对答案做一个前缀和，求出最大长度小于 $k$ 的数量，那么根据式子，容斥系数仅在 $1+i\cdot k$ 处有非零系数 $1$ 和在 $k+i\cdot k$ 处有非零系数 $-1$，所以我们考虑枚举 $-1$ 的个数和总共加了多少个 $k$ ，即 $\sum i$，这样就可以得出 $1$ 的个数

$$ \sum_{i\ge 0}\sum_{j\ge 0}\left(-1\right)^i\binom{n-\left(i+j\right)k+i}{i}\binom{j+n-\left(i+j\right)k+i-1}{j} $$

复杂度：$\sum_{k=1}^n\left(\frac{n}{k}\right)^2=\mathcal{O}\left(n^2\right)$，此时单次计算是 $\mathcal{O}\left(\left(\frac{n}{k}\right)^2\right)$ 的

科技做法：

设 $F$ 是 $\sum_{i\ge 0}i!z^i$ 那么求的就是 $\left[z^n\right]F\left(P\left(z\right)\right)$

考虑到 $F$ 是 $d-finite$ 的，满足 $\left(1-z\right)F-z^2F^{\prime}-1=0$

设 $G=F\left(P\left(z\right)\right)$，那么 $F^{\prime}=\dfrac{G^{\prime}}{P^{\prime}}$

$$ \left(1-P\right)F-P^2\dfrac{G^{\prime}}{P^{\prime}}-1=0 $$

将整个等式乘以 $P^{\prime}\cdot \left(1-z^m\right)^3$ 就可以整式递推了，恰好不需要逆元

Sage 代码验证：

_prec=40
R.<z> = PowerSeriesRing(QQ,default_prec=_prec)
m=int(input())
P=(z-z^m)/(1-z^m)
def F(x):
    ret=0
    for i in range(_prec):
        ret+=factorial(i)*(x^i)
    return ret
    G=F(P)
p1=1-z-m*z^(m-1)+(2*m-1)*z^m-(m-1)*z^(m+1)
# p1=(1-P)*diff(P,z)*((1-z^m)^3)
p2=z^2-2*z^(m+1)+z^(2*m)-z^(m+2)+2*z^(2*m+1)-z^(3*m)
# p2=P^2*((1-z^m)^3)
p3=1-m*z^(m-1)+(m-2)*z^m+m*z^(2*m-1)-(m-1)*z^(2*m)
# p3=diff(P,z)*((1-z^m)^3)
print(G*p1-p2*diff(G,z)-p3)

此时我们进行根号分治就是 $\mathcal{O}\left(n\sqrt{n}\right)$ 了。

子集容斥

$$ \begin{aligned} \exp\left(F\left(z\right)-1\right)&=1+z\\ F\left(z\right)&=\ln\left(1+z\right)+1=1+\sum_{i\ge 1}\dfrac{\left(-1\right)^{i-1}}{i}z^i \end{aligned} $$

例：ABC236Ex Distinct Multiplies
给定 $n$ 个正整数 $D_i$ 和 $M$，求有多组互不相同的 $A_i$ 使得 $\forall 1\le i\le n,D_i\mid A_i,A_i\le M$，答案 $\bmod 998244353$，$1\le n\le 16,1\le D_i,M\le 10^{18}$

枚举 $A_i$ 相同的连通块进行容斥，答案就是 $ \left\lfloor\frac{M}{\operatorname{lcm}\left(S\right)}\right\rfloor $

$kth\min-\max$ 容斥：

$$ \max_{k}\left(S\right)=\sum_{T\subseteq S}\binom{\left|T\right|-1}{k-1}\min_{k}\left(T\right) $$

例：PKUWC2018 猎人杀
给定 $n$ 和长为 $n$ 的序列 $w_i$，有 $n$ 个猎人，每次按 $w_i$ 带权随机干掉一个猎人，求 $1$ 最后被干掉的概率

首先有结论：如果每次可以杀死的猎人是全集，不断杀直到杀死一个未死的猎人，最后的概率不变
那么我们考虑 $1\sim n$全部死亡的期望步数 $f_1$ 和 $2\sim n$ 全部死亡的期望步数 $f_2$
那么 $1 $ 在 $2\sim n$ 之后死的情况就是 $1\sim n$ 全部死亡的步数大于 $2\sim n$ 全部死亡的步数的情况，这时两者的差的期望就是不断挑一个猎人杀死直到1死亡的期望步数，即 $\dfrac{1}{p_1}$
那么 $1$ 最后死的概率就是 $\dfrac{f_1-f_2}{\frac{1}{p_1}}$
考虑 $\min-\max$ 容斥求出 $f_1,f_2$

$$ f_1=\sum_{T\subseteq \left[n\right],T\neq \emptyset}\left(-1\right)^{\left|T\right|-1}\dfrac{1}{\sum_{i\in T}p_i} $$

由于 $\sum_{i\in T}p_i$ 只有可能是 $\dfrac{1}{\sum w_i},\dfrac{2}{\sum w_i}\dots \dfrac{\sum w_i}{\sum w_i}$，分治NTT背包算出所有的项即可

计数旋转不同构的环的个数：

令 $G_n,F_{m,n}$ 分别表示长度为 $n$ ，长为 $m$ 最短循环节为 $n$ 且旋转不同构的环的方案数

则 $F_{m,n}=G_n-\sum_{d\mid n,d< n}d\cdot F_{m,d}$

集合幂级数

集合幂级数把集合作为幂级数上指标，可以方便的处理集合交集合并集合不交并等问题

当定义乘法为无交并，求多项式复合集合幂级数时，则是利用了这个多项式在复合集合幂级数的占位多项式时，每一项均会在集合有交时溢出，因此是正确的

对于特殊的多项式，可以求导 $\mathcal{O}\left(n^2\right)$ 完成单次复合，例如 $\exp,\ln$

对于一般多项式，只能对幂级数进行牛顿迭代

例：UOJ94 胡策的统计
对于图的所有生成子图，求连通块个数的阶乘之和 $\left|V\right|\le 20$

假设连通块的集合幂级数是 $f_{S}$，原图的生成子图的集合幂级数是 $g_S$，那么 $g_S=\sum_{i\ge 0}\dfrac{f_S^i}{i!}=\exp\left(f_S\right)$，因为一个集合的集合会被统计大小的阶乘次

那么随后假设答案的集合幂级数是 $h_S$，那么 $h_S=\sum_{i\ge 0} f_S^i=\dfrac{1}{1-f_S}$，即答案就是对原图的生成子图的集合幂级数复合 $\dfrac{1}{1-\ln}$

直接容斥的话，我们假设钦定了 $i$ 个连通块之间互不连边

那么容斥系数满足 $\displaystyle\sum_{k\le i}\left\{\begin{matrix}i\\k\end{matrix}\right\}f_k=i!$

$\mathcal{O}\left(n^2\right)$ 递推然后 $\mathcal{O}\left(n^22^n\right)$ 复合即可

例：CEOI2019 Amusement Park
给定一张图，对于所有翻转一个边的子集使得图无环的方案数，求翻转的边的方案数的总和 $\bmod 998244353$，$\left|V\right|\le 18$

首先注意到对于一个 $DAG$ ，翻转其所有边后依旧是一个 $DAG$，因此我们可以将翻转的方案数乘以 $\dfrac{\left|E\right|}{2}$ 得到答案。

首先枚举一个当前点集 $S$ 的子集 $T$ 作为入度为 $0$ 的点，那么 $T\rightarrow S$ 的边都是确定方向的，且 $T$ 是一个独立集

那么 $\displaystyle f\left(S\right)=\sum_{T\subseteq S,T\ne \emptyset}\left[T是独立集\right]f\left(S\backslash T\right)$

那么令独立集的集合幂级数是 $g_S$，那么 $f_S=g_S\cdot f_S +1$，$f_S=\dfrac{1}{1-g_S}$，求逆即可

Burnside 引理

对于置换群 $G$ 和着色集合 $\mathcal{C}$ ，满足 $G$ 作用在 $\mathcal{C}$ 上，即 $\forall f\in G,c\in \mathcal{C},f\ast c\in \mathcal{C}$

则 $\mathcal{C}$ 中非等价着色数，即等价类的个数，为 $\dfrac{1}{\left|G\right|}\sum\limits_{f\in G}\#\left\{c\mid c\in \mathcal{C},f\ast c=c\right\}$

即 $G$ 中每个置换下不变的着色数的平均值。

例：Project Euler 781 Feynman Diagrams 改
给定正整数 $n$ ，求无标号的 $n+2$ 个点的混合图个数。$\bmod 10^9+7$
恰存在一个点没有无向边相邻，恰有一条有向出边，没有有向入边
恰存在一个点没有无向边相邻，恰有一条有向入边，没有有向出边
剩下的点中无向边构成一个匹配，每个点恰有一条有向出边，一条有向入边，有向边无自环
换句话说，有向边构成一条链和若干个环。$n\le 5000$

~~原题是弱联通，有简单做法，所以看看不弱联通的情况~~

首先可以发现任意一个费曼图对 $2n$ 阶对称群封闭。

对于 $2n$ 阶对称群的任意一个置换 $f$ ，有向链以及与有向链弱联通的哪些点都只能由 $f$ 中的不动点构成。

发现，对于若一条有向边连接 $f$ 中的同一个循环内的两个点，则这条边在这个循环上的 “步长” 可以是 $1$ 到环长 $-1$ 中的任意一个数

若一条有向边连接 $f$ 中的两个循环，假设是 $u_1,u_2\cdots u_n$ 和 $v_1,v_2\cdots v_m$，其中 $n\ge m\ge 2,u_1\rightarrow v_1$，那么存在边 $u_2\rightarrow v_2,u_3\rightarrow v_3,\cdots$

如果 $n\ne m$，那么存在边 $u_{m+1}\rightarrow v_1$，矛盾！

因此 $n=m$ ，若一条无向边连接 $f$ 中的一个循环中内部的一对点，那么这个循环长度只能是偶数，且无向边连接的是直径。

若连接 $f$ 中的两个循环，则 $n=m$ ，证明同理。

因此，假设恰好有 $k$ 个长度为 $n$ 的循环，那么种类数有：

$$ \begin{aligned} \left\{\begin{array}{}\displaystyle \left[2\mid k\right]\left(k-1\right)!!n^{\frac{k}{2}}\left(\sum_{i=0}^{\frac{k}{2}}\binom{k}{2i}\left(2i-1\right)!!n^i\left(n-1\right)^{k-2i} \right)&n\equiv 1\bmod 2\\ \displaystyle\left(\sum_{i=0}^{\frac{k}{2}}\left(2i-1\right)!!\binom{k}{2i}n^i\right)\left(\sum_{i=0}^{\frac{k}{2}}\binom{k}{2i}\left(2i-1\right)!!n^i\left(n-1\right)^{k-2i}\right)&n\equiv 0\bmod 2\end{array}\right. \end{aligned} $$

直接背包转移即可，最后转移的时候还要乘上一个

$$ \binom{j}{ik}\left(\prod_{t=1}^{k}\binom{it-1}{i-1}\left(i-1\right)!\right) $$

为选 $k$ 个长度为 $i$ 的环的方案数，时间复杂度 $\mathcal{O}\left(n^2\log_2n\right)$

常用技巧

规约问题，使规模减小

例：CF1580F Problems for Codeforces
求不同的长度为 $n$ 的数列 $a$ 使得 $\forall 1\le i<n,a_i+a_{i+1}<m$ 且 $a_1+a_n < m$，答案 $\bmod 998244353$ ，$2\le n\le 50000,1\le m\le 10^9$

首先观察到相邻两项 $a_i,a_{i+1}$ 必有一项 $<\frac{m}{2}$。

我们先假设 $n$ 是奇数，那么此时环上至少有一处 $a_i<\frac{m}{2},a_{i+1}<\frac{m}{2}$，那么我们从这些地方断开环，断成若干段首尾都 $<\frac{m}{2}$ 的段，

对于这些段，一定都是 $<\frac{m}{2}$ 和 $\ge\frac{m}{2}$ 交错的。

由于这些段减去 $\frac{m}{2}$ 后和相同长度，满足相邻两项和 $<\frac{m}{2}$ ，没有首尾限制的的数列一一对应，且段长必须是__奇数__

因此我们考虑计算出长度为 $i,1\le i\le n$，任意相邻两项和 $<m$ ，没有首尾限制的数列的数量

对于一个数列，如果没有相邻两项均 $<\frac{m}{2}$，那么这个数列必定是 $<\frac{m}{2},\ge\frac{m}{2}$ 交错，与相同长度，限制为 $<\frac{m}{2}$ 的数列一一对应，

否则断开均 $<\frac{m}{2}$ 的那些地方，首尾与长度为__偶数__，限制为 $<\frac{m}{2}$ 的数列一一对应，中间段与长度为__奇数__，且限制为 $<\frac{m}{2}$ 的数列一一对应。（中间段数可以是 $0$）

具体的来说，假设限制是 $<\frac{m}{2}$ 时的长为偶数的 $OGF$ 是 $A$ ，长为奇数的 $OGF$ 是 $B$，那么限制为 $<m$ 时的 $OGF$ 为 $\dfrac{A^2}{1-B}+B$

当 $n$ 偶数是，还可以从限制为 $<\frac{m}{2}$ 的环转移过来，多算一些东西即可。

注意实现细节

例：Project Euler 774 Conjunctive Sequences 改
对值域为 $\left[0,m\right]$ 的长度为 $1,2\cdots n$ 的数列和环计数，使得相邻两项的按位与都不是 $0$，环要求旋转不同构，答案 $\bmod 998244353$。$1\le n\le 10^5,1\le m< 2^{30} $

先考虑链怎么做

首先容斥，考虑对长度为 $1,2\cdots$ 的相邻的两项不为 $0$ 的连续段的方案数计数。假设这个的 $OGF$ 是 $f$，那么答案就是 $\left[-x^n\right]\dfrac{1}{1+f}$

把 $\le m$ 变成 $<m+1$ ，然后考虑怎么将值域规约成规模减半的问题。下面假设 $m$ 就是原来的 $m+1$。

如果 $m$ 这一位是 $0$，那么相当于把 $\frac{m}{2}$ 的每段连续段乘上最后一位放 $0,1$ 的方案数使得没有两个 $1$ 相邻。

如果 $m$ 这一位是 $1$，那么一段合法的段就是由 $m-1$ ，限制为 $\frac{m}{2}$ 的合法段交替形成。此时规约到 $\frac{m}{2}$ 的合法段有一个限制是，这个序列的两端都是 $0$，这个序列的一端是 $\frac{m}{2}$ 另一端是 $0$，或者两端都是 $\frac{m}{2}$。

于是我们对于限制为 $m$ 的算出三个 $dp$ 数组 $f,g,h$，分别表示两端无限制，一端有限制，两端均有限制的方案数。

设辅助数组 $dp_i$ 表示到第 $i$ 位，且第 $i$ 位是 $m-1$ 的方案数。

$$ \begin{aligned} dp_i&=g_{i-1}^{\prime}\cdot F_{i-1}+\sum_{j=1}^{i-1} dp_{j}\cdot h_{i-j-1}^{\prime}\cdot F_{i-j-1}\\ f_{i}&=f_{i}^{\prime}\cdot F_{i}+\sum_{j=1}^{i}dp_j\cdot g_{i-j}\cdot F_{i-j} \end{aligned} $$

$g,h$ 同理计算即可。然后使用多项式求逆和卷积进行优化

复杂度 $\mathcal{O}\left(n\log_2n\log_2m\right)$

计算贡献

例：AGC019F Yes or No
有一个长度为 $n+m$ 的 $01$ 序列，其中有 $n$ 个 $1$，$m$ 个 $0$ ，在所有可能情况中等概率随机，询问 $n+m$ 次，每次询问序列的第 $i$ 位，回答 $\left\{0,1\right\}$ 中的一个数，然后会给出第 $i$ 位的正确值，求最优策略下期望答对多少个。

假设当前剩下有 $p$ 个 $0$ 和 $q$ 个 $1$，且 $p\le q$

那么当 $p\ne q$ 时下一位是 $0$ 时概率是 $\dfrac{\binom{p+q-1}{p-1}}{\binom{p+q}{p}}=\dfrac{p}{p+q}$ ，下一位是 $1$ 的概率是 $\dfrac{q}{p+q}$，回答 $1$ 更优

如果直接对上面这个东西计数是没法做的，考虑这个东西的几何意义

假设整个过程是从 $\left(n,m\right)$ 往左下走到 $\left(0,0\right)$ ，当前位于 $y=x$ 上时期望获得 $\frac{1}{2}$，当在 $y=x$ 上方时回答 $0$ 更优，下方时回答 $1$ 更优

假设有个走的子串是从 $\left(i,i\right)$ 走到 $\left(j,j\right)$，中间不经过 $y=x$，那么除了第一步以外所有回答必一样，都是 $0/1$，而这个子串在对应方向上走了 $j-i$ 步

那么贡献是 $j-i$，因此总的贡献就是 $\max\left(n,m\right)+E\Big($ 与 $y=x$ 的交点的个数 $\Big)\times \dfrac{1}{2}$ .

继续拆贡献，对于 $y=x$ 上的每个点计算经过其的概率即可。

构造双射

例：求证：
$$ \prod_{i=1}^{\infty}\dfrac{1}{1-z^i}=\sum_{i=1}^{\infty}\dfrac{z^{i^2}}{\prod_{k=1}^i\left(1-z^k\right)^2} $$

首先可以知道左边是划分数的 $OGF$。注意到右边是 $z^{i^2}$，所以考虑正方形

把划分数对应的 $\mathrm{Ferrers}$ 的图画出来，考虑左上角最大的正方形，即按照 $y=-x$ 最远能延申到哪里，假设正方形边长为 $i$

那么正方形下侧和右侧都是一个每一项 $\le i$ 的单调不降序列，这样的一组 $i$ 的方案和划分一一对应

因此右边等于左边。

例：Amshz Farm
对于所有长度为 $n$ 的序列 $a$，使得 $\sum\left[a_j\ge i\right]\le n-i+1$ 且 $a_i\in \left[1,n\right]$，求 $\sum_{i}\left(\sum_{j}\left[a_j=i\right]\right)^k$

令 $c_i=\sum_j\left[a_j=i\right]$ ，那么每种不同的 $c_i$ 序列对方案数的贡献是 $\frac{n!}{\prod c_i!}$，对答案的贡献是 $\frac{n!}{\prod c_i!}\cdot\sum c_i^k$

考虑构造方案数到 $n+1$ 个点的有标号有根树（根为 $1$）的双射。

令 $dfs$ 序为按照子节点编号从小到大访问，$s_i$ 为 $dfs$ 序的第 $i$ 个点的儿子数。

那么对于 $\forall 1\le j\le n$，若 $\sum_{i\le j} s_i<n$ ，那么前 $j$ 个点构成了一颗虚树，矛盾！

所以 $s_i$ 是一组合法的 $c_i$

对于任意一组合法的 $c_i$，我们贪心的构造，如果当前节点还有剩余的空位，就往下接，否则往上跳父亲找到第一个合法的位置。

对于不同的 $c_i$ 树的形态互不相同，对于相同的 $c_i$，树的形态有 $\frac{n!}{\prod c_i!}$ ，那么方案数和有根树一一对应。

那么原题所求的和有标号，$1$ 根树一一对应，也和有标号，无根树一一对应。

~~后面的还不会，先不写了~~

一些杂题

例：CF1503E 2-Coloring
求将 $n\times m$ 的网格二染色的方案数，使得对于每一行的黑格子个数不为 $0$ 且位置连续，每一列的白格子个数不为 $0$ 且位置连续，且$1\le n,m\le 2021 $

由题意得，黑色和白色的格子不可能同时都联通

两者均不联通当且仅当排列成了类似风车型的形状，我们定义此时黑色联通

黑色联通时，一定存在一列 $i$ 使得：$\le i$ 的列的白色联通，$>i$ 的列的白色也联通，这时左右的白色连通块每一行都是贴着边缘的

由于黑色联通，第 $i,i+1$ 列的白色一定不相邻，假设此时左边在上，右边在下

设第 $i$ 列最低的白色是第 $p$ 行，第 $i+1$ 列最高的白色是第 $q$ 行，则 $p> q$

令此时左侧第 $i$ 行白色的宽度为 $l_i$，右侧第 $i$ 行白色的宽度为 $r_i$

那么即统计 $0\le l_1\le l_2\le \cdots \le l_p =i>l_{p+1}\ge l_{p+2}\cdots \ge l_{n}\ge 0 $ 的方案数乘上 $0\le r_1\le r_2\le \cdots \le r_{q-1}<n-i=r_{q}\ge r_{q+1}\ge \cdots r_{n}\ge 0$

方案数即为 $\binom{ i+p-1}{p-1}\binom{i-1+n-p}{n-p}\binom{n-i+n-q}{n-q}\binom{n-i-1+q-1}{q-1}$ ，一边和 $p$ 有关另一边和 $q$ 有关前缀和即可

最后答案要乘以 $2$ ，因为假设了 $p>q$ ，白色联通同理，只是 $p> q+1$

例：CF1608F MEX Counting
给定 $n,k$ ，和长度为 $n$ 的序列 $b$，求有多少不同的序列 $a$ 满足 $0\le a_i\le n,\left|\operatorname{mex}\left(\left\{a_1,a_2\cdots a_i\right\}\right)-b_i\right |\le k$ ，其中 $1\le n\le 2000,0\le k\le 50,-k\le b_i\le n+k$ 。答案 $\bmod 998244353$

首先我们有一个很显然的 $dp$ ，$f_{i,j,k}$ 表示枚举到 $a_i$，$\operatorname{mex}$ 为 $j$，且有 $k$ 个位置大于 $\operatorname{mex}$ 的方案数，然后转移，但是这样复杂度过高

我们发现复杂度主要在枚举大小为 $t$ 占了 $k$ 中的几个，所以我们将状态替换为表示大于 $\operatorname{mex}$ 的有多少种值不同的位置。

转移就变为了

$$ f_{i,j,k}=\sum_{t< j}\binom{k+j-t-1}{j-t-1}f_{i-1,t,k+j-t-1}+f_{i-1,j,k}\cdot j +f_{i-1,j,k}\cdot k+ f_{i-1,j,k-1} $$

其中第一项转移可以用前缀和优化，总复杂度为 $\mathcal{O}\left(n^2k\right)$

例：Horrible Cycles
有一个二分图，两侧各有 $n$ 个点，左侧第 $i$ 个点向右侧前 $a_i$ 个点连了无向边，求简单环的个数 $\bmod 998244353$

首先左侧的点是没有顺序的，因此我们可以先把 $a_i$ 排个序

考虑对于一个环在左侧前 $i$ 个点和右侧前 $a_i$ 个点形成的子图里是长什么样的。

假设这个环不全在里面，那么在这个图里就是若干段链，每段链首尾都是右侧点，且每段右侧左侧点交替

那么就可以 $dp$ 了，状态为 $f_{i,j}$ 表示右侧前 $i$ 个点有 $j$ 条链的方案数，这样我们只需要在 $a_j=i$ 的时候加入点 $j$ 就行了

转移时新加入的点可以单独成立一条链或者什么都不做，点 $j$ 可以合并两条链或者什么都不做。

复杂度 $\mathcal{O}\left(n^2\right)$

例：Cyclic Medians
给定 $n,m$ ，和长为 $n$ 的数列 $x$ ，以及长为 $m$ 的数列 $y$，下标均从 $0$ 开始
令变量 $a$ 初始时为 $a_0$，对其做 $n\times m$ 次操作（下标也从 $0$ 开始），第 $i$ 次把 $a$ 变成 $a,x_{i\;\bmod \;n},y_{i\;\bmod\;m}$ 的中位数。给定 $V$ ，求对于所有值域在 $\left[1,V\right]$ 中的数列 $x,y$，$a$ 最后的值的和。

首先我们把 $a$ 变成 $\sum_{i\ge 0} \left[i<a\right]$

按 $\le v$ 把所有数变成 $0,1$ ，每次中位数的操作即使对三个数取众数

可以发现，只有当每次操作是 $0,1$ 和 $a$ 时 $a$ 的值才会不变，否则 $a$ 的值和初始值无关。

有个很重要的性质是，当结果和 $a$ 无关时，结果为 $0$ 和 $1$ 的个数是相同的，因为如果对所有 $x,y$ 取反结果就会取反

当每次操作是 $0,1$ 和 $a$ 时，令 $g=\gcd\left(n,m\right)$，那么对于 $k=0,1\dots g-1$ ，$x_{k},x_{k+g},\dots x_{n-k+g}$ 和 $y_{k},y_{k+g},\dots y_{m-k+g}$ 两两会和 $a$ 组合一次

因此要么这一组 $x$ 都是 $1$，$y$ 都是 $0$ ，或者这一组 $x$ 都是 $0$ ，$y$ 都是 $1$，因此方案数是 $\displaystyle\left(v^{\frac{n}{g}}\left(V-v\right)^{\frac{m}{g}}+v^{\frac{m}{g}}\left(V-v\right)^{\frac{n}{g}}\right)^g$

例：TROC-20 E String Ordinal 改
有一个长为 $n$ 的 $01$ 字符串 $S$ ，给定 $S$ 的第 $i$ 位是 $0$ 的概率 $p_i$，求期望最少删掉几个字符，使得 $10$ 不是剩下的字符串的一个子序列，对 $998244353$ 取模
$1\le n\le 3\times 10^5$

首先原问题等价于 $n-$ $s$ 中最长不下降子序列的长度

如果 $p_i$ 均为 $\frac{1}{2}$，即 TROC-20 G Superstring Ordinal

我们枚举 $s$ 最长不下降子序列中 $0/1$ 交界的位置，并钦定这是可能的位置里最靠后的一个点

那么假设这个点是 $i$，则从 $i$ 开始的任意一段子串中 $1$ 的个数都必须严格大于 $0$ 的个数，否则 $i$ 一定不优。

且以 $i$ 为结尾的任意一段子串中 $0$ 的个数必须大于等于 $1$ 的个数，否则 $i$ 也一定不优

此时是一个类似卡塔兰数的结构。

对于一个 $1,-1$ 组成的长度为 $k$ 的序列，任意前缀和 $\ge 0$ 的方案数为

$$ \sum_{i=\left \lceil\frac{k}{2}\right \rceil}^{k}\left(\binom{k}{i}-\binom{k}{i+1}\right)=\binom{k}{\left \lceil \frac{k}{2} \right \rceil} $$

任意前缀和 $\ge 0$ 的序列中 $1$ 的个数总和为

$$ \sum_{i=\left \lceil\frac{k}{2}\right \rceil}^{k}i\left(\binom{k}{i}-\binom{k}{i+1}\right)=\sum_{i=\left \lceil\frac{k}{2}\right \rceil}^{k}\binom{k}{i} +\binom{k}{\left \lceil \frac{k}{2} \right \rceil}\cdot \left(\left \lceil \frac{k}{2} \right \rceil-1\right) $$

均可以 $\mathcal{O}\left(1\right)$ 计算，总复杂度 $\mathcal{O}\left(n\right)$

对于原问题，将 $0$ 看作 $1$ ，$1$ 看作 $-1$ 以后最长不降子序列等于 $1$ 的个数加上前缀最大值，前面一部分是容易计算的，对于后面一部分，我们对于每个 $i$ ，计算出前缀最大值 $\le i$ 的概率，即可计算答案。时间复杂度 $\mathcal{O}\left(n^3\right)$

然后考虑一个反悔贪心，先把所有的 $1$ 作为答案，维护一个计数器表示当前 $1$ 的个数减 $0$ 的个数，每当计数器变成 $-1$ 的时候翻转上一次计数器清零的位置到当前位置的这段区间，并将计数器清零，答案加 $1$

具体维护 $f_{i,j},g_{i,j}$ 表示到第 $i$ 位，计数器为 $j$ 时候的概率和答案的期望。

时间复杂度 $O\left(n^2\right)$

考虑分治，假设我们当前分治区间为 $\left(l,l+k\right]$，已知 $f_{l,0}\sim f_{l,k-1}$，求其对 $f_{l+k,0}\sim f_{l+k,k-1}$ 的贡献

假设分治中点为 $l+t$ ，那么我们先计算出 $f_{l+t,0}\sim f_{l+t,k+t-1}$ 再计算出其对 $f_{l+k,0}\sim f_{l+k,k-1}$ 的贡献

对于左半部分， $f_{l,t}\sim f_{l+k}$ 对 $f_{l+t,0}\sim f_{l+t,t-1}$ 和 $f_{l,0}\sim f_{l,k-1}$ 对 $f_{l+t,t}\sim f_{l+t,k+t-1}$ 的贡献都可以由卷积直接得到而不会进行计数器重置的操作

而 $f_{l,0}\sim f_{l,t-1}$ 对 $f_{l+t,0}\sim f_{l+t,t-1}$ 的贡献可以继续分治得到

右半部分同理

时间复杂度 $T\left(n\right)=2T\left(\dfrac{n}{2}\right)+\mathcal{O}\left(n\log_2n\right)=\mathcal{O}\left(n\log_2^2n\right)$

例：CF1553I Stairs
给定一个长度为 $n$ 的排列 $p$。
令其中第 $i$ 个位置的权值为 $p$ 中最长的包含 $i$ 的连续自然数按顺序组成的区间的长度。例如，$p=\left[4,1,2,3,7,6,5\right]$ 中，第 $6$ 个位置的权值为 $\left[5,7\right]$ 的长度，第 $2$ 个位置的权值为 $\left[2,4\right]$ 的长度。
将这些权值依次拼在一起，就得到了 $p$ 的「阶梯序列」。
给定 $a$，你需要求出存在多少个 $p$，使得 $a$ 为 $p$ 的「阶梯序列」。答案对 $998244353$ 取模。（题意来自luogu)

给出的 $a_i$ 数组显然是形如 $a_1$ 个 $a_1$ ，$a_{a_1+1}$ 个 $a_{a_1+1}$ ，$\dots$ ，否则一定不合法，直接输出 $0$ 即可，那么原序列可以简化为 $b_1,b_2,\cdots b_m$

对于每个 $b_i$ ，如果不是 $1$ ，那么它可以是上升或者下降的，$2$ 种情况，但是如果是 $1$ 的话只有一种情况，因此我们只需考虑 $b_i$ 是否是 $1$ 即可。

如果不考虑每个 $a_i$ 是极长段的限制，那么总方案数就是 $2^{m-cnt_1}\cdot m!$，接下来考虑容斥。

如果 $b_1,\dots,b_m$ 被合并成了 $k$ 个连续段，容斥系数就是 $\left(-1\right)^{m-k}$

考虑如何把 $2^{m-cnt_1}$ 和 $m!$ 塞进转移式子里。

但是由于最后的方案数和 $k!$ 有关，因此 dp 时必须保留段数，但是可以直接将这一连续段的方案数乘进转移。

$$ \begin{aligned} f_{i,j}=\left\{\begin{matrix}f_{i-1,j-1}+2\sum_{k\le i-2} f_{k,j-1} &b_i=1\\\\2\sum_{k\le i-1} f_{k,i-1} &b_i\neq 1\end{matrix}\right. \end{aligned} $$

写成生成函数就是：

$$ \left[\begin{matrix}sum_{i-1}\\f_i\end{matrix}\right]=\left\{\begin{matrix}\left[\begin{matrix}1 &1\\x &2x\end{matrix}\right]\cdot \left[\begin{matrix}sum_{i-2}\\f_{i-1}\end{matrix}\right] & b_i=1\\\\\left[\begin{matrix}1 &1\\2x &2x\end{matrix}\right]\cdot \left[\begin{matrix}sum_{i-2}\\f_{i-1}\end{matrix}\right] & b_i\neq1\end{matrix}\right. $$

分治用 NTT 算矩乘即可。

文章目录

组合计数

结论