题解 P4257 【可爱の#10数字划分】

· · 题解

官方题解

版权声明：本题由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