生成函数杂题

GF 加训！

前置

序列 $f_1,f_2,...,f_n$ 的生成函数为 $F$，指数型生成函数为 $\hat F$。

无标号组合： $\dfrac{1}{1-F}$。

有标号有序组合：$\dfrac{1}{1-\hat F}$。

有标号无序组合：$\exp(\hat F)$。

loj3395

给定 $n$，对 $k\in [1,n]$ 计数存在一个长度 $\ge k$ 的连续上升子段的 $n$ 阶排列个数。

$n\le 1000$​，读入模数。

首先先转化为每一段都 $<k$ 的方案数。

在一般的欧拉数问题里，一般是钦定断点数量进行容斥，容斥系数是显然的 $(-1)^c$，但是本题要求的是长度，容斥并不显然。

依旧是要钦定若干连续段必须是上升的，然后断点处随意，我们要给每个长度一个容斥系数 $p_i$。

对于其容斥系数，我们考虑一个合法划分，连续段长度为 $a_1,a_2,...,a_k$。

$$f(a_1,a_2,a_3,...,a_k)=\prod_{i=1}^k [a_i<k]$$

一个合法的连续段，在容斥中会被分成若干个小段。

$$[m<k]=\sum_{\sum a_i=m}\prod p_{a_i}$$

是一个无标号组合，设 $p_i$ 的生成函数为 $P$，有：

$$\frac{1}{1-P(x)}=\sum_{i=0} [i<k]x^i=\frac{1-x^k}{1-x}\\ P(x)=\frac{x-x^k}{1-x^k}=x+\sum_{i=1} x^{ik+1}-x^{ik}$$

然后考虑去组合答案，连续段拼起来是一个有顺序有标号组合，因此答案为：

$$[\frac{x^n}{n!}]\frac{1}{1-\hat P(x)}$$

直接暴力多项式求逆，注意到由于只有 $ik,ik+1$ 的位置有值，因此枚举 $k$ 之后是调和级数，总复杂度 $\mathcal O(n^2\log n)$。

已知 $n,m,A,B,C,D$，要从 $(0,0)$ 走到 $(n,m)$，在 $(x,y)$ 的时候，你可以：

• 走到 $(x-1,y+1)$，权值为 $Ax^2$ 。
• 走到 $(x,y+1)$，权值为 $Bx+Cy$。
• 走到 $(x+1,y+1)$，权值为 $D$。

求所有方案权值乘积之和。

$n,m\le 2\times 10^5$ 。

太有难度了/yun 。

这种题要注意各个模型之间的转化，路径，盒子，树，序列之类的。

注意到这题 $y$ 每次加一，$x$ 最多变化一，这个可以对应成有根森林，然后在赋予其组合意义（这步其实最高妙）。

$x$ 表示现在还有用的树数量，$y$ 表示总点数。

• 新开一棵有用的树，权值为 $D$。
• 让一棵有用树的根变成自己儿子，权值为 $B$，总权值就是 $Bx$。
• 成为任意一个点的儿子，权值为 $C$，总权值 $Cy$​。
• 选两棵有用树，成为他们根的父亲，权值为 $2A$，总权值 $x(x-1)A$ 。
• 成为一棵有用树的根，权值为 $A$，总权值 $xA$，并把这棵树变成无用的。

注意到这样和原来的路径问题完全对应了，然后只需要数树的权值然后组合即可。

最后无用的树一定是一个有用的加一个根，再挂几个 $C$，因此只需要数有用的树。

$$f_n=2A\sum_{i=1}^{n-2}\binom{n-1}{i}f_if_{n-1-i}+((n-1)C+B)f_{n-1}+[n=1]D$$

懒得解方程牛顿迭代了，直接分治 FFT 解出 $f$。

然后组合答案，先考虑搞出无用树的生成函数：

$$G(x)=A\int \frac{F(x)}{1-Cx}\text{dx}$$

上面放个根，这个根还可以挂若干个 $C$，而 $C$ 又是有标号有序组合，最后需要积分平移一格。

然后答案就是：

$$[\frac{x^n}{n!}]\frac{F^m(x)}{m!}\exp(G(x))$$

CF1930I

给定长度为 $n$ 的 01 串 $p$，计数长度为 $n$ 的 01 串 $q$ 满足，对于 $1 \le i \le n$ 存在 $l, r$ 使得：

• $1\le l\le i\le r\le n$。
• $p_i$ 是 $q[l,r]$ 的众数之一。

$n\le 10^5$ 。

分析一下充要条件，换成一个 $+1,-1$ 路径，容易发现如果一条边前后有相同高度的就合法，否则寄。

钦定若干个不合法，然后去容斥，前后两段的贡献是好算的，中间每段的贡献相当于是要放 $i$ 个 $+1,-1$，要让起点是最小值，终点是最大值。

容斥一下，先枚举终点高度为 $K$，然后经过若干次对称后到达 $K'$，方案数就是 $\dbinom{i}{(i-K')/2}$​​ 。

统计一下每个 $K'$ 的贡献，记为 $c_{K'}$。

$$f_n=\sum_{i=-n}^n c_i\binom{n}{(n-i)/2}$$

但是这个东西直接用卷积非常难做，生成函数一下：

$$f_n=[x^0] C(x^{-1}+x)^n$$

看上去依然非常不可做，于是看题解。

居然是直接分治，注意到 $(x^{-1}+x)^n$ 的长度只有 $\mathcal O(n)$，因此在算 $[l,r]$ 的答案的时候，可以先暴力卷出 $mid$ 处的多项式，然后考虑算分成的两个区间，那么此时的多项式只需要保留 $\mathcal O(r-l)$ 的长度即可，那么总复杂度 $\mathcal O(n\log^2 n)$。

算出中间部分之后，就是一个简单的 dp 了，也是分治 FFT 转移。

总复杂度 $\mathcal O(n\log^2 n)$。

有点小卡常，不过卡了一下还是过了。