[题解] Mivik 卷积

· · 题解

欢迎到我的博客查看

两个多项式 A 和 B 通过 Mivik 卷积得到 C 可以文字描述为：

两个盒子，从第一个里面选 i 个（0\le i<|A|）物品权值为 A_i，从第二个里面选 j 个（0\le j<|B|）权值为 B_j。C_i（0\le i<|A|+|B|-1）的值为从两个盒子里面选总共 i 个的最大权值和。

容易证得 Mivik 卷积的结合律和交换律（考虑下标的和）。然后我们发现整个问题就变成了：

要求构造 |S|-1 个物品，第 i 个物品不选的权值为 b_i，选的权值为 a_i，使得从其中选 i 个物品（0\le i<|S|）的最大权值和恰为 S_i。

我们考虑如果给定物品我们怎么计算 S。我们首先把所有的 b_i 加起来得到 S_0，然后把所有物品按 (a_i-b_i) 从大到小排序，则 S_k 等于 S_0 加上前 k 大的 (a_i-b_i)。

我们发现 S 合法当且仅当对于任意一个 i（1\le i<|S|-1），都有 S_i-S_{i-1}\ge S_{i+1}-S_i。我们可以用这个条件判合法。然后我们如下构造 a 和 b 数组（下标从 1 开始）：b_1 设置为 S_0，a_1 设置为 S_1，对于其它的 i，b_i 设置为 0，a_i 设置为 v_i-v_{i-1}。注意对 |S|=1 要特判答案。

所以这真的是一道良心语文题。

mivik.h

代码