2021.10.17模拟赛

If I have never known the sore of farewell and pain of sacrifices

暴力连边是 $P^3$ 的复杂度，但是考虑到代价是线性加的，但是每次是乘的，所以猜想答案可能不超过 $\log$ 级别？

打个表答案不超过 $17$ 所以每个点只连前后十七条边即可

设 $c[l,r]$ 是 $[l,r]$ 区间的最小代价， $t[l,r]$ 是 $[l,r]$ 区间的最小代价数量

暴力区间 dp，发现区间肯定是取最大值最优，卡卡常就过了

操作是取 $ci$ 的后几位，发现二进制下乘法能用的性质不多，所以转换成模意义

若当前最高的 $1$ 位是 $x$ 需满足 $ci \equiv i \pmod {2^{x+1}}$

即 $(c-1)i \equiv0 \pmod {2^{x+1}}$ 如果 $(c-1)=b2^m$ 那么必然有 $2^{x+1-m}|i$

因为做了个前缀 $\max$ 所以要考虑每个能取到值往后会有 $2^{x+1-m}$ 的贡献

记 $u=x+1-m$ 则这个 $x$ 的答案为 $\sum (2^x+k2^{u})(2^u)$ $k$ 的范围是 $[0,2^{m-1})$

等差数列求和即可

对于 $x=n$ 的位置单独处理 $2^x+k2^u \le n \Rightarrow k=\lfloor\dfrac{n}{2^u}\rfloor-2^{x-u}$

会有一小部分算超出 $n$ 减去即可

发现这个东西显然具有单调性，二分，快速判定正方形内的不同个数可以用 bitset RMQ 判定

二分 $\le k$ 和 $\le k-1$ 做差即可

$O(n^2\log nm)$

May all the beauty be blessed