UOJ 269 [清华集训2016] 如何优雅地求和题意：给定一个函数 $f(x)$，求出 $Q = \sum_{k = 0} ^ n f(k) \binom{n}{k} x^k (1 - x)^{n - k}$。 给定了 $f, n, x$。 可以发现给定了 $x$ 之后后面的两项可以看成常数但是又不能完全看成常数，但是可以 $O(1)$ 计算的，不妨设系数为 $c_i$。 那么就是求 $Q = \sum_{k = 0} ^ n f(k) \binom{n}{k} c_i$。 考虑拆开来看: $$\begin{aligned}&\sum_{k = 0} ^ n \sum_{j = 0} ^ m k^j \binom{n}{k} c_k \\=& \sum_{k =0}^ n c_k \binom{n}{k} \sum_{j = 0} ^ m k^j \\\end{aligned}$$ 考虑后面的部分怎么操作： 显然后面部分为 $\frac{k^{m + 1} - 1}{k - ...

#593. 新年的军队属实是一道神仙题，估计是去年这个时候听说了这道题，最近把这个坑填了。 给后面要来写的人提个醒，这个题其实没有想象地那么恐怖，代码其实也不复杂，只是推导十分困难。 我说我这篇是全网最详细的不过分吧。 暴力首先我们熟悉一下题目，本质上就是考虑所有的排列 $p$，一个合法的排列有 $m$ 个 $p_i > p_{i + 1}$，求 $\forall l, p_k = l$ 的排列 $p$ 的方案数。 暴力直接全排列即可。 转化显然是人都会全排列，我们考虑点别的。可以发现这个 恰好 m 个下降 就是欧拉数。 我们现在的困难就是如何对应每个 $p_k = l$，并且求出方案数。 考虑使用科技解决这个问题，我们先简化一下如果只需要求一个固定的 $l$。 $Q1:$ 看到很大的数据范围说明很难使用 $\tt Dp$ 来解决问题，况且欧拉数 $\tt Dp$ 是 $O(n^2)$ 的，已经难以推广。 考虑一个经典转化，单点方案数其实可以等价于概率乘上总方案，我们已知总方案我们不妨来计算概率。 $Q2:$ 很显然如果直接考虑所有排列的话我们不一定满足条 ...

我们考虑最终答案为 $i$ 的概率为 $f_i$。 考虑转移的时候肯定是通过 $\tt border$ 进行转移，这样就可以通过 $\tt Dp$ 进行解决。 考虑使用一种另外的方法，我们思考 $f_i$ 肯定是通过一个不合法的情况进行转移的，我们考虑设 $g_i$ 表示长度为 $i$ 但是没有结束。 通过生成函数表示，显然有等式 $ans = F’(1)$。且 $F$ 和 $G$ 的关系是 $F + G = Gx + 1$，就是考虑之后再加入一个字符的贡献。 之后考虑先前 $\tt Dp$ 的 $\tt border$ 转移，显然对于 $G$ 加入某些字符是可以使得其满足条件的。 假设加入了字符串 $S$ 要么 $S$ 就是要求的字符串，要么就是因为之前已经有过一部分了，不妨考虑我们直接加入要求字符串，之后减去多算的，因为多算的部分肯定是 $\tt border$。 考虑已经有的部分是 $A$ 后面的部分是 $B$ 满足 $A + B = L$ 那么我们有 $L - B = A$ 也就是说 $A$ 满足前缀等于后缀，所以是 $\tt bord ...

AT2369 [AGC013C] Ants on a Circle 应该是第二次做到这个题了，但是还是没有写出来。第一次没有看懂题意不应该是理由，倒数的几篇题解，省选退役了。。。 首先如果不考虑编号，我们穿过和返回本质是一样的。 其次对于碰撞我们可以看成穿过之后编号进行了交换，那么我们就需要计算交换编号之后的情况。 节点的相对顺序是不变的。 节点经过 $m$ 时间之后绝对位置是不变的。 我们考虑计算每个点的编号，这样就可以不用考虑返回的情况。 $\tt Solution \ 1$考虑对于一个点，考虑与其相反的点和其碰撞的次数。 我们可以考虑到这个点和相反的所有点碰撞，可以看成两部分，一部分是 $k$ 倍的 $m$ 时间，还有剩余的时间。 直接使用二分即可。 考虑从位置 $x$ 走可以分成 $x + T$ 和 $x$ 部分进行计算贡献，这样计算周期就是经过 $0$ 的了，之后考虑 $v \equiv p \pmod m$，可以直接计算出周期和单独部分。 1234567891011121314151617181920212223242526272829303132333435363 ...

P7987 [USACO21DEC] Paired Up G首先考虑我们匹配肯定是相邻匹配的，之后还有一种可能是间隔一个匹配的。 对于这样进行 $\tt Dp$ 设 $f(i, j)$ 其中 $j$ 是 $0/1$ 表示 $1 \sim i$ 未匹配点的奇偶性。 考虑如下 $4$ 种类转移，设 z = i & 1，$las$ 表示最大的 $x_i - x_{las} > K$ 的位置。 中间有一段是可以内部匹配的 $f(i, z) = f(las, !z) + y_i$。 $x_i - x_{i - 1} \le K$ ，考虑让 $i, i - 1$ 匹配 $f(i, z) = f(i - 1, z)$。 $x_{i + 1} - x_i \le K$，考虑让 $i, i + 1$ 匹配，那么匹配点的奇偶性改变 $f(i, !z) = f(i - 1, !z)$。 $x_{i + 1} - x_i \le K$，考虑跳过这个位置，有 $f(i, !z) = f(las, z) + y_i$。 123456789 ...

P8099 [USACO22JAN] Minimizing Haybales P考虑交换操作会自然想到贪心，考虑贪心选择。 现在对于贪心有一个唯一的问题：是否存在 $i < j, h_i > h_j$ 在 $i$ 进行交换之后 $j$ 不能到达 $j$ 先手操作的最优位置。 考虑 $i$ 向左操作的过程，其可以经过的是 $[h_i - k, h_i + k]$ 的部分，$j$ 经过的是 $[h_j - k, h_j + k]$。 仔细想想确实也没有影响，那么我们可以得到一个贪心。 从左向右扫维护最小字典序的序列，之后二分到一个最大的可以移动的位置，之后再次二分找到最优位置，也就是使得后缀没有 $< h_i$ 的位置。 我们使用平衡树上二分就可以解决这题。 一开始我做的时候，我贪心证伪了 $\cdots$ 这样显得我很呆 $\cdots$ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 ...

CF917E Upside Down 比较有趣的一个题。 对于 $i \to j$ 的路径我们很容易想到分成两部分进行计算： $i \to lca$ $lca \to j$ 跨过 $lca$ 对于前面的部分我们建立 $\tt ac$ 自动机，之后本质上就是单点加区间查询，我们树状数组维护一下。 我们方便处理的是从 $lca \to i$ 的路径，那么我们考虑对于不方便的情况直接建立反串的 $\tt ac$ 自动机即可。 对于跨过的部分我们不妨考虑字符串的分界点为 $x$，那么左边就是 $[1, x]$ 右边是 $[x + 1, n]$。对于两边发现有一个端点是固定的，我们考虑根据这个进行计算。 我们先考虑找到一个合法的串，我们不妨只考虑 $[x + 1, n]$ 的情况另一种情况同理，贪心考虑可以知道这个串右端点是固定的，考虑两段从 $\tt lca$ 经过若干步走到字符串末尾的串设长度为 $a, b, a < b$。因为末尾部分是相同的，所以 $a$ 是 $b$ 的 $\tt border$，那么我们贪心可以考虑选取尽可能长的串。 选取串我们可以考虑尽可能长的串，经过简单 ...

P5287 [HNOI2019]JOJO 加入 $x$ 个字符 $c$，保证相邻加入操作 $c$ 不同。 查询每个前缀的 $\tt border$ 长度和。 如果不看输入感觉没有什么优秀的做法，输入提示了 $x$ 个 $c$ 肯定和做法有关。 我们尝试计算加入 $c$ 的 $\tt border$，首先找到加入前串 $S$ 的 $\tt border$，之后如果后面恰好有 $\ge x$ 个 $c$ 说明是可以匹配的，如果没有说明这个不是 $\tt border$，考虑继续向前找当前 $\tt border$ 的 $\tt border$。 既然相邻操作 $c$ 是不同的，考虑将一次操作看成一个点，$S$ 的 $\tt border$ 的结尾肯定恰好是一个完整点，不然之后不可能跟上 $c$。考虑跳 $\tt border$ 后每次后面跟着的 $c$ 是逐渐变多的，考虑如果减少的话 $\tt border$ 是可以增长的。 然后对于一段都能匹配是一个等差数列求和。 我们考虑暴力跳 $\tt border$ 是不行的，考虑优化，我们如果 $\tt border$ 的长度 $\ge \fr ...