首页 > 其他分享 >矩阵树定理 BEST 定理

矩阵树定理 BEST 定理

时间:2024-04-26 09:04:07浏览次数:25  
标签:dfrac 定理 个数 矩阵 prod sum BEST out

矩阵树定理 \(\text{BEST}\) 定理

证明很复杂,连 \(\text{cmd}\) 这种无敌神犇都不会,而且对定理本身的可扩展性几乎为 \(0\),即每次套用的定理都跟模板一模一样。

矩阵树

无论任何情况,一定要不能有自环

无论任何情况,一定要不能有自环

无论任何情况,一定要不能有自环

对于无向无权图,设 \(A\) 为邻接矩阵,\(D\) 为度数矩阵,定义基尔霍夫矩阵为 \(K=D-A\),那么生成树个数为去掉任意的第 \(k\) 列第 \(k\) 行的余子式。

对于有向图,设 \(A\) 为邻接矩阵,\(D^{in}/D^{out}\) 为入度/出度矩阵,同样定于 \(K^{in}/K^{out}=D^{in}/D^{out}-A\)

以 \(k\) 为根的外向树个数为 \(K^{in}\) 去掉第 \(k\) 行第 \(k\) 列的余子式。

以 \(k\) 为根的内向树个数为 \(K^{out}\) 去掉第 \(k\) 行第 \(k\) 列的余子式。

加权扩展,如果每个点带权的话那么的是所有生成树边权乘积的和。

即求的是:

\[\sum_T\prod_{e\in T}w_e \]

此时邻接矩阵的值为边权,度数矩阵为边权和。

对于矩阵数的一个小优化:因为最终的答案一定不可能是负数,所以算行列式的时候可以不用记录当前值的正负号。

P6178 【模板】Matrix-Tree 定理

模板。

P4336 [SHOI2016] 黑暗前的幻想乡

发现每个公司恰好搞一条边有点烦,还是转容斥。

设 \(f(S)\) 表示钦定集合 \(S\) 内的元素不能搞边的方案数。

那么有:

\[ans=\sum_S(-1)^{n-|S|}f(S) \]

P3317 [SDOI2014] 重建

本题求的是:

\[\begin{aligned} ans&=\sum_T(\prod_{e\in T}w_e \prod_{e\notin T} w_e)\\ &=\sum_{T}(\prod_{e\in T}w_e\dfrac{\prod_e(1-w_e)}{\prod_{e\in T}(1-w_e)})\\ &=\prod_e(1-w_e)(\sum_T\prod_{e\in T}\dfrac{w_e}{1-w_e}) \end{aligned} \]

为了防止分母为 \(0\),需要扰动一下。

P6624 [省选联考 2020 A 卷] 作业题

先煎蛋地化简下式子

\[\begin{aligned} ans&=\sum_T(\sum_{i=1}^{n-1}w_{e_i})\times \gcd(w_{e_1},w_{e,_2},\cdots,w_{e_{n-1}})\\ &=\sum_T\sum_{i=1}^{n-1}w_{e_i}\sum_{d|gcd(w_{e_1},w_{e_2},\cdots,w_{e_{n-1}})}\varphi(d)\\ &=\sum_{d=1}^{max(w_{e_1},w_{e,2},\cdots,w_{e_{n-1}})}\varphi(d)\sum_T[d|\gcd(w_{e_1},w_{e_2},\cdots,w_{e_{n-1}})](\sum_{i=1}^{n-1}w_{e_i}) \end{aligned} \]

发现内层求的是所有生成树的边权和的和,这与我们能干的求所有生成树的边权积的和。

那么这里有两种常见手法,一种是取对数/\(\text{exp}\) 将乘法与加法相互转换,还有一种也就是这道题的方法。

考虑把边权变为 \((1+w_ix)\),那么最终我们只需要求得最后的一次项系数即可。

那么就需要重新定义加建乘除

设当前两个多项式分别为 \(a+bx\) 和 \(c+dx\)。

加法减法就是对应项加减。

乘法即为:\((a+bx)(c+dx)=ac+(ad+bc)x\)

除法:\(\dfrac{a+bx}{c+dx}\)

考虑先手动将 \(c+dx\) 求逆变乘法。

\((c+dx)(e+fx)=1 (\text{mod} \ \ x^2)\)

带入 \(x=0\) 以及 \(x=1\) 得到:

\[\left\{ \begin{aligned} ce=1 \\ ce+cf+de=1 \end{aligned} \right. \to \left\{ \begin{aligned} e&=\dfrac{1}{c} \\ f&=-\dfrac{d}{c^2} \end{aligned} \right. \]

那么:

\[\dfrac{a+bx}{c+dx}=(a+bc)(\dfrac{1}{c}-\dfrac{d}{c^2}x)=\dfrac{a}{c}+\dfrac{bc-ad}{c^2}x \]

直接做为 \(O(n^3V)\),\(V\) 为值域,有点爆。

优化:注意到只有当可选边个数大于等于 \(n-1\) 的所有 \(d\) 求行列式即可。

P5296 [北京省选集训2019] 生成树计数

发现求的是 \(k\) 次方和,比上面那个更加复杂。

依葫芦画瓢,将边权设为 \((1+x+……+x^k)\)。

但是在重新定义乘法的时候不太对,假设前一个多项式为 \(A_0,A_1,\cdots A_k\),后一个为 \(B_{0},B_{1},\cdots,B_k\)

乘法的时候为:

\[C_i=\sum_{j=0}^{i}\binom{i}{j}A_jB_{i-j} \]

这与正常的卷积不太一样,把组合数打开:

\[\dfrac{C_i}{i!}=\sum_{j=0}^{i}\dfrac{A_j}{j!}\times \dfrac{B_{i-j}}{(i-j)!} \]

那我们只需要把初始的比设置成

\[\sum_{i=0}^{k}\dfrac{w_i}{i!}x^i \]

再推一下暴力多项式求逆的方法:

\[\sum_{j=0}^{i}A_jB_{i-j}=[i=0] \]

求逆相当于是给定一个 \(A\),求 \(B\)。

\[-\sum_{j=1}^{i}f_jg_{i-j}=f_0g_j \]

那么有:

\[B_i= \begin{cases} \dfrac{1}{A_0} & i=0\\ -\dfrac{1}{A_0}\displaystyle\sum_{j=1}^{i}A_jB_{i-j} & i>0 \end{cases} \]

最后再套上矩阵树即可。

P4208 [JSOI2008] 最小生成树计数

首先注意到无论怎么变换顺序,最终边权形成的集合一定相等。

那么考虑先对求出每种权值出现了多少次,然后对于每种权值,加入

所有不是这种权值的树边,然后并查集缩点,加入所有这种权值的边跑矩阵树求出方案数。

最终答案为每种权值得到的答案的乘积。

【UR #6】智商锁

鲜花:我还做这道题前也想到了同样的idea,蛤蛤蛤。

首先把 \(k=0\) 的情况判掉。

一种朴素的想法是直接随机一个图然后看看它的生成树个数是否恰好为 \(k\) ,每次成功的概率为 \(\dfrac{1}{998244353}\),没救。

注意到对于一个图,答案为每个边双连通分量的生成树的个数乘积,原因是割边必须选。

那你考虑将图分为 \(4\) 个部分,每个部分 \(25\) 个点,然后随机 \(1000\) 个 \(25\) 个点的图跑矩阵树,那么只要存在四个图 \(A,B,C,D\) 设 \(f(S)\) 为图 \(S\) 的生成树个数。

那么只要存在 \(f(A)f(B)f(C)f(D)\equiv k\pmod {998244353}\) 即可。

\(f(S)\) 是随机生成,可以近似为一个随机数,那么可以近似为产生 \(1000^4\) 个随机数,那么极大概率能找到一个特定的 \(k\)。

\(f(A)f(B)\) 这种成对的值放入 \(\text{map}\) 内,每次遍历每个值,看看 \(\dfrac{k}{f(A)f(B)}\) 是否存在即可。

最后把找到的 \(4\) 个图 \(A,B,C,D\) 顺次排布,然后 \((A,B),(B,C),(C,D)\) 分别连一条边即可。

\(\text{BEST}\) 定理

说的是对于一个有向 欧拉图 ,记第 \(i\) 个点的出度为 \(out_i\) ,其本质不同欧拉回路个数为:

\[T\prod_{i=1}^{n}(out_i-1)! \]

\(T\) 为任意一个点为根内向树个数。(u 群有大佬证明说任意一个点为根的答案全相等)

注意一定是有向的欧拉图。

要使用定理前一定要判断是否为欧拉图。

注意:这里把循环同构的欧拉回路只计算了一遍,如果从第 \(i\) 个点为起点和终点的欧拉回路数量还需要乘以 \(out_i\)

P5807 【模板】BEST 定理 | Which Dreamed It

板子题,直接做就好了。

[AGC051D] C4

注意到这是无向图,考虑枚举 \(1\to 2,2\to 3,3\to 4,4\to 1\) 分别的个数为 \(a,b,c,d\),那么反过来的个数为 \(A-a,B-b,C-c,D-d\),大写字母表示无向图时的边权。

此时复杂度爆了,但是你注意到最终一定要是欧拉图,也就是出入都要平衡,那么只要确定了 \(a\) 那所有的都确定了。

确定了每条边的个数后直接跑欧拉回路板子即可。

注意到本体同起点同终点的边不做区分,那么最后要乘以 \(\dfrac{1}{a!b!c!d!(A-a)!(B-b)!(C-c)!(D-d)!}\)

复杂度 \(O(A)\)

扩展:求无向图的欧拉回路数量?

别想了哥们,这是 \(\text{NPC}\)

P7531 [USACO21OPEN] Routing Schemes P

注意到每条边需要恰好出现一次,这与欧拉回路的定义很像。

考虑转化,建立一个源点和汇点,每次源点连向所有起点,所有终点连向汇点,然后汇点向源点连 \(n\) 条边,\(n\) 为起点终点个数。

然后答案为以源点为根的欧拉回路个数,但是汇点和源点连出去的边是不区分,最后还需除以 \(out_S!out_T!\)。

标签:dfrac,定理,个数,矩阵,prod,sum,BEST,out
From: https://www.cnblogs.com/Hanghang007/p/18159162

相关文章

  • 矩阵树定理 BEST 定理
    矩阵树定理\(\text{BEST}\)定理证明很复杂,连\(\text{cmd}\)这种无敌神犇都不会,而且对定理本身的可扩展性几乎为\(0\),即每次套用的定理都跟模板一模一样。矩阵树无论任何情况,一定要不能有自环无论任何情况,一定要不能有自环无论任何情况,一定要不能有自环对于无向无权图,......
  • Hessian矩阵以及在血管增强中的应用—OpenCV实现【2024年更新】
    有别于广为人知的Sobel、Canny等一阶算法,基于Hessian矩阵能够得到图像二阶结果,这将帮助我们深入分析图像本质。Hessian矩阵在图像处理中有着广泛的应用:其中在图像分割领域,包括边缘检测、纹理分析等;在图像增强领域,包括边缘增强、边缘消除等。本文从Hessian矩阵定义出发,通过清晰简......
  • 矩阵
    矩阵的定义:矩阵(matrix)其实就是一个二维数组,第\(i\)行\(j\)列的元素即为\(a_{i,j}\)矩阵的运算:加减:它们均为逐个元素进行。只有同型矩阵之间可以对应相加减。转置:矩阵的转置,就是在矩阵的右上角写上转置「T」记号,表示将矩阵的行与列互换。对称矩阵转置前后保持不变。乘......
  • cf1957 E. Carousel of Combinations(打表/威尔逊定理)
    https://codeforces.com/contest/1957/problem/E题意记\(Q_n^k\)为在\(n\)个数中选\(r\)个数排列成一圈的方案数,即圆排列数。求\[\sum_{i=1}^n\sum_{j=1}^iQ_i^j\\mathrm{mod}\j\]对\(10^9+7\)取余的结果。思路这种模数变来变去的题,要考虑打表。打表思路:https......
  • 二维矩阵、关键功能、关键质量测试
    答题纸 1、 绘制需求层次-需求方面二维矩阵。 功能质量约束业务级需求在线的房屋租赁系统,完善的房屋匹配机制。 可用性、可靠性、安全性、房源、需要移动端和网页端用户级需求用户:租赁者、管理员、房主房主:即使看到房屋的看房信息。......
  • CF1957E 做题小计 : 威尔逊定理
    被数论虐爆了(悲)威尔逊定理\(\forallp\inprime,(p-1)!\equiv-1(\bmodp)\)为什么啊?对于\(2\)很显然。对于\(p\),我们知道\(inv(p-1)=p-1=-1\),然后\(inv(1)=1\)然后因为\(p\inprime\),所以对于任意\(a\in[2,p-2]\),都有\(inv(a)\)与它唯一对应。因为\(......
  • 两个不等式,几个大数定律,和中心极限定理
    I,不等式  2,大数定律 特注,该定理的证明一般假设方差有限,然后证明此情形。事实上,方差无限也成立,但比较精巧,一般书上不给证明。   ......
  • Python Numpy 矩阵运算
    目录1前言2点积与矩阵乘法2.1np.dot()2.2np.matmul()和@2.3np.multiply和*3矩阵的逆4Ref1前言Python中经常涉及到矩阵运算,其借助于Numpy库进行,因此本文记录一些基于Numpy的矩阵运算2点积与矩阵乘法矩阵的点积(dotproduct),又称为内积(innerproduct)$a=(x_1,y_1)......
  • 基于EP4CE6F17C8的FPGA矩阵键盘实例(另类方法)
    一、电路模块电路模块参见“基于EP4CE6F17C8的FPGA矩阵键盘实例”部分。二、实验代码本例使用6个数码管依次显示按下按键的键值,每位显示的值可从0~F,对应16个矩阵按键。按键reset为复位键,代码使用Verilog编写,具体如下。先编写数码管实现显示字形解码的程序,模块名称为seg_decode......
  • 2024年GPLT团体程序设计比赛L2-D吉利矩阵题解
    只能说比赛时前期做得太慢了,后面导致题目只能捞点分数(IOI赛制),当时这道题是我不剪枝DFS拿了4分,压线拿铜牌!考完试一做,发现是个大水题(bushi)主要原理:DFS(深度优先搜索)+剪枝名言:学搜索核心就是学剪枝废话不说了,见代码点击查看代码//原理:DFS+剪枝#include<bi......