323 AT_xmascon21_c Count Me
先做没有问号的情况。
把问题倒着做，每次删只能删连续段的末端 \(0\)，或是连续段的开头 \(1\)，若我们在开头插入 \(0\)，在结尾插入 \(1\) 并强制这些不能删，那么我们能将 \(0\) 连续段与 \(1\) 连续段匹配，操作可以看作将一个 \(01\) 变成 \(0\) 或是 \(1\)，于是我们完成了去重。
我们在相邻位置之间插入一个分隔符，考察第一次操作这两个分隔符两端字符的时间，将其作为分隔符的删除时间，容易发现其为 \(1\) 到 \(n+1\) 的一个排列。
考察字符串对排列的限制，一个简单的观察是一个 \(0\) 限制右边比左边先删除，\(1\) 则相反，事实上任意满足限制的排列都能构造出对应的字符串，于是问题变为了 loj#575. 「LibreOJ NOI Round #2」不等关系。
问号事实上很好考虑，因为任意合法排列填完后问号都会被唯一地确定，用问号分割串分别做即可。
324 CFgym102978J Japanese Knowledge
没有 \(k\) 限制的问题是经典的阶梯状网格图格路计数，具体可见 CFgym102220I Temperature Survey，做法大致是每次取中点劈开，递归左上，并使用若干次 FFT 刻画中间红色长方形的转移，然后递归右下。
\(k>0\) 时存在一组双射：
仅保留区间 \([k+1,n]\) 内的数，并将其余数减一（为了强制没有好操作），做 \(k\) 无限制的问题的答案等于恰好 \(k\) 个好操作的答案。
证明考虑建立两个问题的双射：
- 原问题到新问题：删去所有 \(A_i=x_i\) 的 \(x_i\)，剩余的数字拼接在一起一定符合要求；
- 新问题到原问题：从小到大枚举新问题的答案序列，每次放在大于等于其的第一个空位置，剩下的位置填 \(A_i\)。
容易发现这两个映射互为逆。
于是问题类似上面的 \(k\) 无限制，分治 NTT 即可，复杂度 \(O(n\log^2 n)\)。
325 CFgym102978E Edge Subsets
以前模拟赛考过，然而现在又不会做了。
不妨令 \((A,B)=1\)，因为可以分组处理。
我们将一个点 \(x\) 记作 \((\lfloor\frac xB\rfloor,\frac xA\bmod B)\)，于是 \(+A\) 相当于向右（循环）或是向右下，\(+B\) 相当于向下。
于是我们获得了一个类似网格图的东西，有两种状压方式：
- 从上往下扫，记录整行匹配状态，状态数 \(2^B\lceil\frac{n}{B}\rceil\)；
- 枚举第一列状态，从左到右扫，记录整列匹配状态，状态数 \(4^{\lceil\frac nB\rceil}B\)。
平衡可以得到状态数不超过 \(2^{\sqrt{2n}}\operatorname{poly}(n)\) 的做法。
326 CFgym103415J Cafeteria
将转移刻画为矩阵形式，我们若计算出前缀积矩阵 \(A_i\) 与前缀积的逆矩阵 \(B_i\)，就可以 \(O(m)\) 地处理一次询问。
观察转移矩阵，其只有主对角线/主对角线上方可能为 \(1\)，于是左乘该矩阵等价于对于每个主对角线上方的 \(1\)（假设其在 \((i,i+1)\)），将第 \(i\) 列加到第 \(i+1\) 列，是 \(O(n^2)\) 的。
还需求出前缀积的逆矩阵，也就是要预处理右乘这个矩阵逆的前缀积。右乘该矩阵等价于把第 \(i+1\) 行加到第 \(i\) 行，因此右乘其逆就等价于把第 \(i\) 行减去第 \(i+1\) 行。
复杂度 \(O(nm^2+qm)\)。
327 2021 集训队互测 Round 12 蜘蛛爬树
数据结构学傻了.jpg。
答案形式一定是在某个点跳完所有的横边，假设这个点是 \(p\)，我们使用树剖的结构刻画其：
- \(\log\) 条重链的前缀所有轻子树（包括根）；
- 一条重链的区间内所有轻子树（包括根）；
- \(\log\) 个点的子树（每个跳到新重链的点）；
- \(\operatorname{lca}\) 子树补内的结点，这一部分需要继续划分，可以得到形式与第一、二部分一致的问题。
第一部分可以离线下来对于每条重链扫描线维护李超树，第二部分使用线段树套李超树（由于是静态的，pushup 可以直接李超树合并），第三部分维护子树的李超树合并。
一个细节是第二部分李超树合并会改变某些结点的信息，你可以把询问挂在对应线段树结点，在合并完当前线段树子树的李超树后立即处理询问。
复杂度 \(O(n\log^2 n)\)。
328 Ptz2019 Winter Day3 Japanese Contest I Ranks
将问题分为三部分解决：
- \(A\) 的秩；
- \(A\) 去掉第 \(i\) 行（记作 \(v_i\)）后秩的变化；
- \(A\) 取反 \((i,j)\) 位置后去掉第 \(v_i\) 秩的变化。
第一部分使用线性基可以 \(O(\frac{n^3}{w})\)。
第二部分等价于 \(A\) 去掉 \(v_i\) 后能否线性表示出 \(v_i\)。即是否存在一个异或和为 \(0\) 的集合包含 \(v_i\)。
将所有自由元用基底表示出来，我们断言只有这些基底，以及自由元可以满足上面的性质，证明比较简单，将某个未出现的基底所在的集合拿出来，将所有自由元用基底表示，可以发现这个基底能被其余基底表示出来，矛盾。
第三部分是类似的，其相当于是否存在一个异或和为 \(2^j\) 的集合包含 \(v_i\)。
注意到我们只需得知一个这样的集合，通过异或上异或为零的集合就可以生成所有满足条件的集合，于是我们尝试用线性基表示出 \(2^j\)，若能，那么 \(2^j\) 的表示与上面合法的元素均满足条件。
复杂度 \(O(\frac{n^3}{w})\)。
标签：27,frac,前缀,矩阵,52,问题,旧梦,基底,李超树 From： https://www.cnblogs.com/xiaoziyao/p/17359363.html