[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Mivik 卷积

定义两个多项式的 Mivik 卷积如下：

$$ f\left(x\right)\otimes g\left(x\right)=\sum_{k=0}^{\deg f +\deg g}\max_{i\in [0,\deg f] \land j\in [0,\deg g]\land i+j=k}\left\{\left[x^i\right]f\left(x\right)+\left[x^j\right]g\left(x\right)\right\} x^k $$

给出一个最高项次数为 $n$ 的多项式 $f$，试构造多个一次函数使其 Mivik 卷积为 $f$，或者指明无解。

$1\le n\le 5\cdot 10^5$，$-10^8\le f_i\le 10^8$

题目链接

---

思路

两个多项式 $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

代码