洛谷5406 [THUPC2019]找树
Luogu LOJ 分析 转化为计数问题，求每种权值的生成树个数。 考虑矩阵树定理 我们对每条边构造一个多项式 $f(x)=x^w$，并将乘法定义为输入的运算，这样子求出的基尔霍夫矩阵删去一行一列后的行列式的 $x^w$ 项系数即为边权和为 $w$ 的生成树个数。 具体实现时，我们先对行列式中的每个元素做 FWT，求出行列式后再 IFWT 回来。这里的 FWT 和 IFWT 是广义的，即这...
Luogu LOJ 分析 转化为计数问题，求每种权值的生成树个数。 考虑矩阵树定理 我们对每条边构造一个多项式 $f(x)=x^w$，并将乘法定义为输入的运算，这样子求出的基尔霍夫矩阵删去一行一列后的行列式的 $x^w$ 项系数即为边权和为 $w$ 的生成树个数。 具体实现时，我们先对行列式中的每个元素做 FWT，求出行列式后再 IFWT 回来。这里的 FWT 和 IFWT 是广义的，即这...
Luogu 分析 根据二项式定理有 所以我们只要把边权设成 $e^{a_ix}$，然后直接矩阵树定理即可。 因为数据范围很小，所以多项式乘法和求逆可以直接暴力，NTT 甚至会慢。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ===...
Codeforces Luogu 分析 我们把顶点黑白染色，那么一面镜子就可以看成是连接同色点的一条边。 接下来给出一个结论：一个方案合法当且仅当黑点连成了一棵树或者白点连成了一棵树。 （比较感性理解的）证明： 首先，当黑点连边确定时白点连边一定唯一确定，所以我们只考虑黑边确定的情况。 先证必要性： 先考虑后面那个限制。如果连成了环，则环内部的边一定没有光线会穿过，所以不能有环。 再考虑前...
Codeforces Luogu 算法一 分析 设树边的权值为 $x$，非树边的权值为 $1$，然后矩阵树定理。设得到的多项式为 $F(x)$，那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。 然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式，所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$，然后解方程组解出系数即可...
Luogu LOJ 分析 显然莫比乌斯反演一下，可以得到 直接做不一定跑得过去，可以加一个剪枝：如果当前满足条件的边数 $<n-1$ 显然当前的 $d$ 的贡献为 $0$，不必再矩阵树计算。这样子复杂度似乎就是对的了。 另外有的高斯消元写法会在生成树个数是 $998244353$ 的倍数的时候 GG，谁能告诉我为啥啊 /kel 代码 // ======================...
Luogu 分析 显然答案为 我们知道矩阵树定理求的实际上是 $\sum_T \prod_{e \in T} w_e$，于是我们可以使用矩阵树定理算出后面东西。 但是有 $p_e = 1$ 的情况，我们只需要把 $p_e$ 设为 $1-\epsilon $ 即可。 代码 //It is made by M_sea #include <algorithm> #include &l...