网站开发 提成,湖南seo优化按天付费,免费扑克网站代码,云服务器网站建站老早就听说#xff0c;一直没学#xff0c;今天遇到一个LGV比较裸的题#xff0c;特地学习一下 选自oi-wiki
定义#xff1a; e(u,v)表示u到v这条路径上所有边的边权之积(路径计数时#xff0c;可以将边权都设为1),很多路径统计问题就是用到这一点
引理#xff1a; 答案…老早就听说一直没学今天遇到一个LGV比较裸的题特地学习一下 选自oi-wiki
定义 e(u,v)表示u到v这条路径上所有边的边权之积(路径计数时可以将边权都设为1),很多路径统计问题就是用到这一点
引理 答案就是矩阵的行列式(可以用高斯消元来搞)
用法
在路径统计问题中我们会将边权设为1e(u,v)常常用于表示从(a,b)走到(c,d)的方案数一共要走sumabs(c-a)abs(d-b),其中挑选c-a步选择向下走,即Cc−ad−bc−aC_{c-ad-b}^{c-a}Cc−ad−bc−a 对于起点终点的选择要具体情况具体分析首先起点和终点不能是重复的而且和原方案等价多数采取平移。
例题
2019牛客多校Monotonic Matrix [P6657 【模板】LGV 引理] hdu5852 Intersection is not allowed! P7736-[NOI2021]路径交点 CodeForces 348D Turtles
