悠然w

矩阵树定理

BZOJ(6) cdq分治(2) CodeForces(2) DP(6) dsu on tree(2) FFTNTT(4) FWT(1) KDtree(4) loj(1) luogu(6) min-max容斥(1) ODT/珂朵莉树(6) OI无关(1) 二分(2) 二分图匹配(3) 克鲁斯卡尔重构树(1) 分块(1) 分治(3) 动态点分治(1) 区间DP(1) 单调栈(8) 双指针(1) 后缀自动机(1) 奇技淫巧(3) 学习笔记(4) 容斥定理(1) 差分(3) 广搜bfs(3) 扫描线(1) 数位DP(3) 数论(1) 整体二分(1) 文化课(1) 最小生成树(1) 最短路(3) 未归档(57) 杂记(11) 树状数组(4) 树链剖分(1) 概率&期望(3) 模拟(4) 洛谷(10) 状压DP(3) 生成函数(2) 矩阵乘法&矩阵快速幂(2) 矩阵乘法&矩阵快速幂(2) 线段树(4) 组合数学(1) 结论题(2) 考试总结(20) 莫队(1) 贪心(3) 随机(2) 题解(1) 高斯消元(2) 高精度(6)

归档

标签

去牛客网

/ 注册

全部文章 / 矩阵树定理（共2篇）

洛谷 P3317 [SDOI2014]重建矩阵树定理

题目大意给出一个图，每条边都有一定概率出现，问最后出现一棵树的概率。题解我们平时矩阵树定理所求的就是\(\displaystyle \sum_{T} \prod_{e \in T} Val_e\) 其中\(T\)是树，\(e\)是边。这道题我们要求的就是 \(\displaysty...

2020-03-28

0 0

[武汉加油] luogu P6178 【模板】Matrix-Tree 定理

矩阵树定理想必大家应该都会高斯消元吧，不会的话可以看模板,我们现在着重讲一下建矩阵的方法。前置知识：我们用到的矩阵，也就是基尔霍夫矩阵的任意一个代数余子式是所有生成树的边权积的和。当所有边边权为1时求的就是生成树的个数了。我们以下设 \((x,y,z)\) 为 \(x\) 到 \(y...

2020-03-05

0 0

洛谷 P3317 [SDOI2014]重建 矩阵树定理

[武汉加油] luogu P6178 【模板】Matrix-Tree 定理

洛谷 P3317 [SDOI2014]重建矩阵树定理