neko

一.neko_tree 猫neko树是一种维护序列的数据结构。在处理绝大多数线段树能处理的问题（如最大子段和，区间最大值，区间\(gcd\)等满足结合律且能快速合并的信息）上能做到\(O(nlogn)\)预处理后\(O(1)\)的询问。但是不支持修改。 neko树怎么维护信息？想象在线段树上取得区间 ......

发现挨位考虑填哪个不太现实，考虑值域。 令 $dp_{i,j,st}$ 表示考虑到 $i$，此时序列长度为 $j$，$i-m$ 到 $i-1$ 填空状态为 $st$ 的方案数，考虑选/不选数即可： $dp_{i,j,st}\times (\text{popcount}(st)+1)\to dp_{i ......

发现有互不相等的限制，那就考虑一下连续段 DP。每次从小到大考虑每个数是否填，填的话填到哪里即可。 容易发现题目中的限制相当于要求每一个连续段的右边填的数不能与它差出 $m$，且容易发现每个段的差的要求一定不相等，那么我们可以直接 $2^m$ 状压记录每个连续段的差值要求。然后再记录一下是否已经确定 ......