自动搬运

查看原文

来自洛谷，原作者为

	玫葵之蝶 **

搬运于2025-08-24 21:58:14，当前版本为作者最后更新于2018-03-01 19:43:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官方题解

版权声明：本题由CCFWC T2改

首先那个质数集合和合数集合没有任何关系，可以分开统计

质数集合我们可以列个dp转移方程：

$dp_S=\frac{1}{\prod_{i\in S}V_i}*\sum_{T\in S}dp_T\sum_{i\in T}V_i$

时间复杂度$O(3^n)$

关于这个东西的优化最后说，先说合数集合

对于合数集合首先我们给出一个结论：

那个E(...)一定等于边权和

我们考虑如何证明

我们考虑将边权从大到小排序

我们顺序处理每一条边

因为那个是路上的最大边权

但是要求的是最小的价值和

所以我们要设计一种方案使得当前考虑的边的计算次数最少

最优方案就是我们将这条边两侧的点在排列中分割成两部分

这样考虑的话每个边都会且仅会被计算一次

然后就来个简单dp就可以求出合数的答案了

这部分的时间复杂度为$O(n^2)$

然后结合前面的做法就可以得到60分了

我们考虑如何优化前面的那个算法

首先那个东西其实就是个子集卷积，可以$O(2^nn^2)$

戳这里看解法

其实也可以看vfk的论文，讲得比我好多了

然后就可以得到80-100分了

80一般应该是用了FWT然后常数过大

100的话可以用FMT常数较小

本题其实也很良心的qwq