Luogu分析根据二项式定理有所以我们只要把边权设成 $e^{a_ix}$,然后直接矩阵树定理即可。因为数据范围很小,所以多项式乘法和求逆可以直接暴力,NTT 甚至会慢。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==========...
Luogu分析答案显然是直接分治把所有 $1-a_ix$ 卷起来,然后多项式 $\ln$ + 多项式求导即可求出 $G(x)$,再推回 $A(x)$ 后卷积即可。代码不想写 vector,于是从鱼那里蒯了一个分治 /kel// ==================================== // author: M_sea // website: https://m-sea...
LOJ分析无。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freo...
咕,咕咕,咕咕咕
Luogu分析先考虑所有 $n$ 个点竞赛图的哈密顿回路数之和。可以发现为多项式求逆即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <...
Luogu分析设 $f_i$ 为 $i$ 个点的 DAG 数量。一个想法是枚举入度为 $0$ 的点的数量,有多项式求逆即可。现在还要求弱连通,那么把 $F(x)$ 求个多项式 $\ln$ 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ /...
CodeforcesLuogu分析设 $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-blog.com...
Luogu分析考虑写出所有物品的生成函数对于一个物品,直接枚举它体积的倍数,即可构造出 $G(x)$ ,然后直接求 exp 即可得到答案。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ============================...
LuoguBZOJLOJ分析$\mathrm{LCT}$ + 泰勒展开。取 $x_0=0.5$ ,然后泰勒展开,发现后面的项的贡献很小,可以只保留 $13$ 项。$\mathrm{LCT}$ 的每个节点维护该点函数的 $n$ 阶导数与子树的 $n$ 阶导数和,这样子查询就可以直接拿出来算。至于 $n$ 阶导数怎么算...$sin'(x)=cos(x),\ cos'(x)=-sin(x)$$(...