洛谷6597 烯烃计数
Luogu 分析 首先求出烷基的 OGF $F(x)$，具体求解过程可以看这里。 考虑一个烯烃断掉双键后会构成一棵根的儿子数 $\leq 2$、其余节点的儿子数 $\leq 3$ 的树，我们考虑求出其 OGF $G(x)$。 根据 Burnside 引理可以得到 这里减 $1$ 是因为双键两端都必须有碳原子（双键显然不能连在氢原子上）。 依据上式直接计算即可。时间复杂度 $\mathcal...
如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
Luogu 分析 首先求出烷基的 OGF $F(x)$，具体求解过程可以看这里。 考虑一个烯烃断掉双键后会构成一棵根的儿子数 $\leq 2$、其余节点的儿子数 $\leq 3$ 的树，我们考虑求出其 OGF $G(x)$。 根据 Burnside 引理可以得到 这里减 $1$ 是因为双键两端都必须有碳原子（双键显然不能连在氢原子上）。 依据上式直接计算即可。时间复杂度 $\mathcal...
LOJ 分析 要求的就是每个节点的儿子数都不超过 $3$ 的无标号有根树数。 设其 OGF 为 $F(x)$，考虑列出一个关于 $F(x)$ 的方程。 不妨规定 $[x^0]F(x) = 1$，那么可以看成每个节点的儿子数都恰好为 $3$。 直接得出 $F(x) = 1 + F(x) ^ 3$ 显然是错误的，因为我们同构的情况被重复计算了。 因此可以考虑 Burnside 引理。对于 $(1...
Luogu 分析 显然进的球数服从超几何分布，即 $\mathcal{O}(L \log L)$ 预处理一行第二类斯特林数，然后 $\mathcal{O}(SL)$ 计算答案即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==...
UOJ 分析 题目要求的就是 $[l,r]$ 中的数的次大质因子的和，这里的次大是可重集的次大。 首先对其差分，变为求 $[1, n]$ 中的数的次大质因子之和。 这个数据范围启发我们考虑一些筛法，仔细思考之后发现只能考虑 Min_25 筛。 然而直接做显然是不行的。我们需要对其第二部分即求答案的部分进行一些改造，使得它能求出我们想求的东西。 对于一个合数，我们在其剩余的质因子个数 $\le...
LOJ 分析 可以发现答案即为 数论分块计算即可。 再考虑 $\sum \sigma_0\!^2(i)$。我们知道 $\sigma_0\!^2$ 是积性函数，且有 $\sigma_0\!^2(p) = 4$、$\sigma_0\!^2(p ^ k) = (k + 1) ^ 2$，因此可以使用 Min_25 筛计算。 代码 // ===============================...
定义 复合逆 如果 $F(G(x)) = x$，则称 $F(x)$ 为 $G(x)$ 的复合逆，记做 $G^{-1}(x)$。 实际上，如果 $F(x)$ 为 $G(x)$ 的复合逆，那么 $G(x)$ 也一定为 $F(x)$ 的复合逆，即复合逆是相互的关系。 拉格朗日反演 设 $F(x)$ 与 $G(x)$ 互为复合逆，则有以下两个式子 多项式 ln 求出 $D(x)$ 和 $F(x)$...
darkbzoj 分析 设答案的 OGF 为 $F(x)$，则有 多项式求逆 + 多项式快速幂计算即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #in...
球与盒子问题大杂烩 下面我们对这 $12$ 个问题简略分析。 I 球之间互不相同，盒子之间互不相同。 每个球都可以任意选择一个盒子，答案为 $m^n$。 II 球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。 每个球选择一个盒子，已经被选择过的盒子不能再被选择，答案为 $m^{\underline{n}}$。 III 球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。...
Luogu LOJ 分析 转化为计数问题，求每种权值的生成树个数。 考虑矩阵树定理 我们对每条边构造一个多项式 $f(x)=x^w$，并将乘法定义为输入的运算，这样子求出的基尔霍夫矩阵删去一行一列后的行列式的 $x^w$ 项系数即为边权和为 $w$ 的生成树个数。 具体实现时，我们先对行列式中的每个元素做 FWT，求出行列式后再 IFWT 回来。这里的 FWT 和 IFWT 是广义的，即这...