[题解] [Mivik Round nurture] Mirror

[题解] [Mivik Round nurture] Mirror

一个无穷的地图,行列从 0 开始标号。$(i,j)$ 可以通过当且仅当 $(i\&j)=0$。同时地图中还有 $n$ 个炸弹。现在给出两个格子,保证可以通过,问从一个格子走到另一个格子至少需要走多少步,且在步数最少的情况下至少需要拆除哪些炸弹。

$1\le n\le 2\cdot 10^5$,$0\le x,y\le 10^{18}$

阅读更多
[题解] [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$

阅读更多