Legendgod’s Blog 树状数组一个函数 $\tt lowbit(x) = x \text{&} (-x)$ 表示 $x$ 的最低二进制位的位置。 可以维护区间加区间和，常数比较小。 $O(n)$ 建树，考虑对于节点 $x$ 向上更新 $x + \tt lowbit(x)$ 即可。 查询第 $K$ 小，就是经典二进制上二分，假设元素 $i$ 出现了 $a_i$ 次。 123456789int Kth(int k) { int cnt = 0, ret = 0; for(int i = log2(n); ~ i; -- i) { ret += (1 << i); if(ret >= n || cnt + t[ret] >= K) ret -= (1 << i); else cnt += ret; } return ret + 1;} 时间戳优化，听起来听高级的，其实就是打标记看当前时刻有没有经过，经过的时候 ...

Legendgod’s Blog 一下子没有什么精神，开一个博客来总结一下，我曾经会过什么东西，同时就当做复习了。 预计会写稍微多一点东西，尽量按照 $\tt oi-wiki$ 的结构和自己的理解来。 如果说当做课件的话可以用下面的部分： ‘ 队列常常就是用 $\tt queue, priority_queue, deque$，分别是普通队列，优先队列，双端队列。 优化 $\tt Dp$，比如说维护一个最大值，就是考虑如果说当前值比之后加入位置的小，显然当前的位置就不用了。每次我们取出队头的最大值即可。 优化斜率 $\tt Dp$，常常说是否要取等的情况，明显这个队列是维护斜率单调的，至于取等的情况，我们考虑斜率相同但是截距不同的情况，所以是需要删除前面的斜率相同的位置。 维护最短路，这个比较显然就不说了。 记住这个东西是先进先出就可以了。 栈就只有一个 $\tt stack$。 维护最值，还是考虑维护最大值，我们对比一下队列的维护方式。队列可以加入当前不是最大值但是之后最大值删掉之后可能产生贡献的情况，但是栈如果发现不能加入之后就不会再加入了，所以说队列是可以维护 ...

test

关于学信息的一些想法$\texttt{tnnd}$ 不知道是不是已经退役的缘故，现在有一些人就是来问我关于学信息的一些问题，我也就不一个一个回答了感觉很多部分是相同的，我就放到一篇博客里面了。 学信息有用吗？ 看程度，如果您水平很强那显然可以保送，但是对于大多数人来说，还是只有 $\tt NOIP\ 1=$ 的水平。 这个据说是可以羟基直接入围。 我六年级开始学信息来得及吗？ 首先需要明确的是学信息的时间是因人而异的，也不一定是越早越好。 当然如果之后想通过信息这条路的话，肯定是早点学信息来得好。 其次是否来得及还需要考虑自身的天赋和努力，但是这个时候开始学习时肯定不晚的。 我高中被拉去信息社团，有必要停课吗？ 如果您是天赋选手那么肯定停课，对于大部分普通的选手来说，停课是没有必要的。 信息竞赛是不是就是玩电脑啊，我们家打电脑可厉害了，你来看看有没有天赋。 $\cdots$ 听说机房里面会有人偷偷打游戏？ 废话，你看文化课教室也有人上课睡觉。 机房的氛围很重要吗？ 其实不是很重要，就算有人天天划水，你自己该学学，该问问就好了。 主 ...

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 ...

8cef0bfe5dbef7c0807e31fc24201994453d6958581aaef7b184c495cf24004f746901fa03a8a21411043fa06ca1352a306dbb6826cd51a48218a0fb0b2ff773be4e55cc25b0d11fe3ca9906b92ef9a4f22780b590cb6a03a14d40f963beeb1c258d56c7c3396a128945aa6c012f42607f1177fdcb1d68fb0e036279c138c027d4e488fa62e7a535d30e2f06a95b521fe2c83ef074daf1a3f431342b263b08f1005e68d5374efc4e99adb3d30e940c24460ad366bf0b8740f1c485d1debc8e0bed558140458b4cd7b70d40e05d5ecddf6d4b2255e0b150a93258a1a23bb38c7eadff9643f10ab3d0f46c80a5fa5b97621c185d91d046886d8 ...