首页 > 小月的炼金术
开通博客写题解
头像 yangjl⁣⁣⁣⁣
发表于 2025-12-19 22:43:21
小月的炼金术 解法：矩阵树定理+多项式乘法 注意到如果没有那什么mod3的限制，就是朴素的矩阵树定理，求所有生成树权值之和（生成树权值定义为边之积）。 而 mod3 的限制可以通过把模P域换成循环取模的多项式域： 边类型是普通管道，系数就是普通 ; 变类型是冰或者火，一个加系数 ，一个加系数，两个组 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 luqyou
发表于 2025-12-20 10:41:01
G | 小月的炼金术 对于类型为 的边，令其边权为 ；对于类型为 的边，令其边权为 ；对于类型为 的边，令其边权为 。 那么我们对这个图做矩阵树定理，求出来的 即代表 的所有生成树的 之和。 将这个多项式乘以 ，则是一个 次多项式，直接代入 作为点值做矩阵树然后拉插出原多项式即可，时 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”