2021.09.03模拟赛

莫听穿林打叶声，何妨吟啸且徐行

经典分块题

考虑处理出来每个块里 $\bmod x$ 的最大值，贪心的考虑 $nx-1$ 是最大值，如果没有就继续向前扫，直到找到，这是一个前缀 $\max$ 过程

开一个桶记录有那些数，做个前缀 $\max$ 就可以 $O(k\ln k)$ 来计算每一个块的答案，预处理是 $O(Bk\ln k)$

查询暴力查即可， $O(B)$ 最终块长取 $O(\sqrt{k\ln k})$ 即可

先转换成从下往上射的图形，长这样

发现按 $y$ 排序需要查询一个矩形内符合条件的方案，不太好做，所以改为按 $x$ 排序

那么发现因为两次入射的方向需要不同，记 $dp_{x,0/1}$ 表示从左下还是右下入射

转移的时候从自己向前枚举，遇到比自己高的就把自己的方案加给他，否则把他的方案加给自己

考虑为啥是对的

因为大的情况是从小的拼起来的，所以只需要证明最小的不合法情况不会被计算

这样显然不会被统计，因为要求两次转移的 $0/1$ 不同

这样子考虑计算最右边的点的时候先会更新最上面的点，这时候下面的点的方案数还没有贡献到她，所以不会计算这条路径

考虑一个位置 $i$ 如果 $2i-1 \le n$ 的话那么必须 $2i-1$ 这个点合法且自己能够翻转得到 $2i-1$

大于 $n$ 只需要这一段后缀和原串后缀匹配即可

考虑我们的最优策略是把一段填平

而且一定是一段谷底，即先减后增的，可以反证

那么设 $dp_{i}$ 当前点为 $i$ 高度为 $h_i$ 的最小值，有 $dp_i = \min(dp_j + \sum\limits_{k=j+1}^{i}(t-h_k)^2+c\times|h_i-t+h_j-t|)$

把后面的式子拆开可以发现是个关于 $t$ 的二次函数，可以 $O(1)$ 计算

所以就需要优化枚举 $j$

因为是把中间填平，所以需要保证枚举的两个端点是大于区间里的高度的，而且因为只需要填谷底，不要填单调递减/增的地方，可以拿单调栈维护一下当前能更新的元素，前后放极大值辅助更新，因为每个点只会被进栈一次，复杂度 $O(n)$

求 $n$ 个点环大小为 $m$ 的基环树

考虑钦点 $m$ 个点作为环，乘上环同构的方案数 $\binom{n}{m}\dfrac{(m-1)!}{2}$

这样的话就是把一个大小为 $m$ 的环和 $n-m$ 个点拼成一个树的方案

purfer 序列的结论: $k$ 个大小分别为 $\mathrm{siz}_i$ 的连通块拼成树方案数为 $\prod \mathrm{siz}_in^{k-2}$

现在是 $n-m+1$ 个连通块，有一个大小为 $m$ 剩下的都是 $1$

总方案数 $\binom{n}{m}\dfrac{(m-1)!}{2}m\times n^{n-m-1}$

需要特判掉 $n=m$ 和 $m \le 2$ 的情况