洛谷4233 射命丸文的笔记
Luogu 分析 先考虑所有 $n$ 个点竞赛图的哈密顿回路数之和。可以发现为 多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #includ...
Luogu 分析 先考虑所有 $n$ 个点竞赛图的哈密顿回路数之和。可以发现为 多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #includ...
Luogu 分析 设 $f_i$ 为 $i$ 个点的 DAG 数量。 一个想法是枚举入度为 $0$ 的点的数量，有 多项式求逆即可。 现在还要求弱连通，那么把 $F(x)$ 求个多项式 $\ln$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blo...
Codeforces Luogu 分析 设 $s_i$ 表示 $i$ 是否在集合中，$f_i$ 表示权值和为 $i$ 的二叉树数量，那么 多项式开根+多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =========...
Luogu 分析 设 $f_i$ 为 $i$ 个点的无向连通图个数，$g_i$ 为 $i$ 个点的无向图个数，那么显然有 多项式求逆后卷起来求出 $[x^{n-1}]F(x)$ 从而求出 $f_n$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-bl...
Luogu 分析 考虑写出所有物品的生成函数 于是可以调和级数的处理出 $G(x)$，然后多项式 exp 即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #i...
Luogu LOJ 分析 LCT + 泰勒展开。 取 $x_0=0.5$ ，然后泰勒展开，发现后面的项的贡献很小，可以只保留 $13$ 项。 $\mathrm{LCT}$ 的每个节点维护该点函数的 $n$ 阶导数与子树的 $n$ 阶导数和，这样子查询就可以直接拿出来算。 至于 $n$ 阶导数怎么算... $sin'(x)=cos(x),\ cos'(x)=-sin(x)$ $(e^x)'=...