洛谷5296 [北京省选集训2019]生成树计数
Luogu分析根据二项式定理有所以我们只要把边权设成 $e^{a_ix}$，然后直接矩阵树定理即可。因为数据范围很小，所以多项式乘法和求逆可以直接暴力，NTT 甚至会慢。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==========...
标签 多项式运算 下的文章
- 首页
- 多项式运算
洛谷4705 玩游戏
Luogu分析答案显然是直接分治把所有 $1-a_ix$ 卷起来，然后多项式 $\ln$ + 多项式求导即可求出 $G(x)$，再推回 $A(x)$ 后卷积即可。代码不想写 vector，于是从鱼那里蒯了一个分治 /kel// ==================================== // author: M_sea // website: https://m-sea...
LOJ150 挑战多项式
LOJ分析无。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freo...
洛谷4233 射命丸文的笔记
Luogu分析先考虑所有 $n$ 个点竞赛图的哈密顿回路数之和。可以发现为多项式求逆即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <...
洛谷6295 有标号 DAG 计数
Luogu分析设 $f_i$ 为 $i$ 个点的 DAG 数量。一个想法是枚举入度为 $0$ 的点的数量，有多项式求逆即可。现在还要求弱连通，那么把 $F(x)$ 求个多项式 $\ln$ 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ /...
CF438E The Child and Binary Tree
CodeforcesLuogu分析设 $s_i$ 表示 $i$ 是否在集合中，$f_i$ 表示权值和为 $i$ 的二叉树数量，那么多项式开根+多项式求逆即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ================...
洛谷4841 [集训队作业2013]城市规划
Luogu分析设 $f_i$ 为 $i$ 个点的无向连通图个数，$g_i$ 为 $i$ 个点的无向图个数，那么显然有多项式求逆后卷起来求出 $[x^{n-1}]F(x)$ 从而求出 $f_n$ 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com...
洛谷4389 付公主的背包
Luogu分析考虑写出所有物品的生成函数对于一个物品，直接枚举它体积的倍数，即可构造出 $G(x)$ ，然后直接求 exp 即可得到答案。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ============================...
洛谷4546 [THUWC2017]在美妙的数学王国中畅游
LuoguBZOJLOJ分析$\mathrm{LCT}$ + 泰勒展开。取 $x_0=0.5$ ，然后泰勒展开，发现后面的项的贡献很小，可以只保留 $13$ 项。$\mathrm{LCT}$ 的每个节点维护该点函数的 $n$ 阶导数与子树的 $n$ 阶导数和，这样子查询就可以直接拿出来算。至于 $n$ 阶导数怎么算...$sin'(x)=cos(x),\ cos'(x)=-sin(x)$$(...