CF891E Lust
Codeforces Luogu 分析 设最后得到的序列为 $\{b\}$，可以发现答案为 求出 $\prod(a_i - x)$，然后枚举其次数计算即可。时间复杂度 $\mathcal{O}(n \log^2 n)$ 甚至 $\mathcal{O}(n^2)$。 代码 // ==================================== // author: M_sea /...
标签 生成函数 下的文章
- 首页
- 生成函数
洛谷5206 [WC2019]数树
Luogu LOJ orz laofu！!1 分析 $op = 0$ 只需要统计两棵树有多少条重边即可。假设有 $c$ 条，答案即为 $y^{n - c}$。 $op = 1$ 先特判掉 $y = 1$ 的情况，答案为 $n^{n - 2}$。 我们要求的是 考察每个连通分量。一个大小为 $a$ 的连通分量会产生 $\frac{n^2 y}{1 - y} a^2$ 的乘积贡献，而 $a$...
洛谷6597 烯烃计数
Luogu 分析 首先求出烷基的 OGF $F(x)$，具体求解过程可以看这里。 考虑一个烯烃断掉双键后会构成一棵根的儿子数 $\leq 2$、其余节点的儿子数 $\leq 3$ 的树，我们考虑求出其 OGF $G(x)$。 根据 Burnside 引理可以得到 这里减 $1$ 是因为双键两端都必须有碳原子（双键显然不能连在氢原子上）。 依据上式直接计算即可。时间复杂度 $\mathcal...
LOJ6538 烷基计数 加强版 加强版
LOJ 分析 要求的就是每个节点的儿子数都不超过 $3$ 的无标号有根树数。 设其 OGF 为 $F(x)$，考虑列出一个关于 $F(x)$ 的方程。 不妨规定 $[x^0]F(x) = 1$，那么可以看成每个节点的儿子数都恰好为 $3$。 直接得出 $F(x) = 1 + F(x) ^ 3$ 显然是错误的，因为我们同构的情况被重复计算了。 因此可以考虑 Burnside 引理。对于 $(1...
BZOJ3684 大朋友和多叉树
darkbzoj 分析 设答案的 OGF 为 $F(x)$，则有 多项式求逆 + 多项式快速幂计算即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #in...
UOJ551 【UNR #4】校园闲逛
UOJ 分析 设 $f_{i ,j, w}$ 为从 $i$ 走到 $j$、权值和为 $w$ 的方案数，$g_{i, j, w}$ 表示连接 $i,j$ 的权值为 $k$ 的边数。 那么有 可以证明 $I-G$ 一定是可逆的。于是我们只需要求一个每个元素都是一个多项式的矩阵的逆，和普通矩阵求逆类似地做即可。 然而这题还卡常，需要精细地实现来减少 NTT 的次数，最好把预处理原根、取模优化、寻...
洛谷4365 [九省联考2018]秘密袭击coat
Luogu LOJ 分析 首先把第 $k$ 大转化掉： 不妨再设一个 $g_{i,j,k}$ 表示子树 $f_{i,j,k}$ 的和，并设 $G_{i,j}(x)=\sum_k g_{i,j,k}x^k$。答案即为 $\sum_{i=k}^n[x^i](\sum_j G_{1,j})$。 看起来这个转移并没有什么可以优化的地方。但是 $F_{i,j}$ 和 $G_{i,j}$ 的最高次项都...
洛谷5296 [北京省选集训2019]生成树计数
Luogu 分析 根据二项式定理有 所以我们只要把边权设成 $e^{a_ix}$，然后直接矩阵树定理即可。 因为数据范围很小，所以多项式乘法和求逆可以直接暴力，NTT 甚至会慢。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ===...
洛谷5326 [ZJOI2019]开关
Luogu LOJ 分析 设 $P=\sum_{i=1}^n p_i$。 设 $F(x)$ 为按到目标状态的指数型概率生成函数，$G(x)$ 为按回自己的指数型概率生成函数。 $F(x)$ 直接把每个开关乘在一起即可，$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有 直接计算即可。 代码 // ==================================== //...
洛谷4233 射命丸文的笔记
Luogu 分析 先考虑所有 $n$ 个点竞赛图的哈密顿回路数之和。可以发现为 多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #includ...