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

[题解] [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

代码

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

https://mivik.gitee.io/2020/solution/mivik-newbie-and-chinos-contest-2020-solution-convolution/

作者

Mivik

发布于

2020-12-04

更新于

2021-05-31

许可协议

评论