寒假做题记录
猜猜我寒假经历了什么？
本来应该打线段树板子的晚上，我的Elementary OS正式“驾崩”，于是我装了很多天系统（以及摸鱼），度过了一个充实的寒假。
寒假的尾巴做了一些题目，就记一下寒假尾巴做过的这些题目吧。
我的答案仓库是Click Me!。根据题号你能找到我的答案，但是我的很多答案有很大的提高和优化空间，欢迎你与我探讨！
0x01. 模板题
这里应该是线段树的模板题，纪念一下，3月再补吧
喜闻乐见的什么都没有。
0x02. 趣题
这个假期也就主要打了Codeforces和AtCoder，所以绝大部分题目都来自于此。
第一题是来自TopCoder的。
人生中的第一场TopCoder SRM，不得不说作为Codeforce规则的起源，这种规则真的紧张刺激，尤其是看聊天区有人在看我的Solution的时候，无敌紧张。
看题，给出两个整数$n$和$x$，在$1\sim n$区间中任选$x$个数的一个子集$S$，把这个子集中的最小元素$\min(S)$看作这个集合的代表元素。问这么选择下的$2^S$的数学期望。
首先数学期望定义是很明确的，出现的值乘以概率，由于这里面的选择随机，也就是等可能性选择，所以期望就是简单的总和除以方案数。
方案数是十分容易求的，$\binom{n}{x}$，关键问题在于这个总和上。首先考虑这样一个子问题：包含$1$的选择方法有多少？实际上是另一个组合问题：我们确定了$1$，从剩下的$n-1$个元素中选择$x-1$个元素有多少种方法？很简单，就是$\binom{n-1}{x-1}$。接下来来考虑$2$的情况：由于在$1$的情况中，已经包含了$2$的部分情况，这一部分可以求得为$\binom{n-2}{x-2}$。那么$2$的选择方法有$\binom{n-1}{x-1}$，我们拿掉这些情况就有$\binom{n-1}{x-1}-\binom{n-2}{x-2}=\binom{n-2}{x-1}$种情况。以此类推，$3$就有$\binom{n-3}{x-1}$种方法……直到$x$时有$\binom{x-1}{x-1}$种情况为止。那么最终答案就是如下的简单式子：
$$ \frac{2^1\cdot\binom{n-1}{x-1}+2^2\cdot\binom{n-2}{x-1}+\cdots+2^x\cdot\binom{x-1}{x-1}}{\binom{n}{x}} $$
一个循环就能计算了。
上面这个过程还有一种更直观的方法：我们从$1$开始迭代，那么当我们把含$1$的组全部筛选掉之后，$2$的选择时自然不能考虑$1$，所以本来$2$可以从剩下$n-1$个元素中选择，现在$1$也被排除，只剩下$n-2$个元素了，自然是$\binom{n-2}{x-1}$。
比较好玩的数学问题，从公式推导上有考虑的价值。（然而比赛的时候手动验算算错了，后面写了个demo发现是对了一波就过了。要是不搞这些幺蛾子说不定分数还能更高。
一道比较有趣的方程问题。
给出一个9宫格，如下编号：
$$\begin{matrix}c_{1,1} & c_{1,2} & c_{1,3} \\ c_{2,1} & c_{2,2} & c_{3,3} \\ c_{3,1} & c_{3,2} & c_{3,3}\end{matrix}$$
对于每一个数，满足$c_{i,j}=a_i+b_j$。问是否存在这样的六元组$(a_1,a_2,a_3,b_1,b_2,b_3)$，使得上述命题成立。
这个题一上来很容易拆成$9$个方程的方程组去做，然而这个题实际上难度只是AtCoder Beginners Contest的第三题而已，肯定不会这么大动干戈。
首先观察一个很基本的事实：任何一个数的得出方法有多个。考虑$c_{1,1}=a_1+b_1, c_{2,1}=a_2+b_1$，马上就能得出$a_2-a_1=c_{2,1}-c_{1,1}$。根据这样的观察，我们可以解出$a_2-a_1,a_3-a_2,a_3-a_1$，那我们几乎可以立即得出$a_2-a_1+a_3-a_2=a_3-a_1$，这样通过两条路就解出了同一个解。假如上述命题成立，这样的等式一定成立，同时还可以对$b_2-b_1+b_3-b_2=b_3-b_1$做出验证，假如这两条都满足，毫无疑问命题成立。
官方题解则提供了另一种做法：首先根据观察，这样的解一定有无穷多个：考虑解元组$(a_1,a_2,a_3,b_1,b_2,b_3)$：
$$ (p_1,p_2,p_3,q_1,q_2,q_3) $$
我们可以对任意的一个偏移量$x$如下构造$(a_1’,a_2’,a_3’,b_1’,b_2’,b_3’)$：
$$ (p_1+x,p_2+x,p_3+x,q_1-x,q_2-x,q_3-x) $$
毫无疑问，$(a_1’,a_2’,a_3’,b_1’,b_2’,b_3’)$也是一组可行解，也就是说，这样的解有无穷多个。那也就是说，$\exists x\in\mathbb{Z},a_1=p_1+x=0$。那到这里其实就很简单了，我们直接令$a_1=0$，然后代入解出一个解元组，之后逐条验证即可。
这一题有趣的地方在于不定方程的处理，我们并不是直接开始高斯消元，而是从一些基本的数学原理入手反向验证，是一道开拓思维的好题目。
前缀和是区间统计的一大利器。
给出$n$长度的一个序列$A=a_1,a_2,\cdots,a_n$，同时给出一个$n-1$长度的字符串$S$，这个字符串的含义为：假如$S_i=1$，那么$a_i$可以和$a_{i+1}$任意多次按任意顺序互换，否则不行。问你根据给定的状况能否把这个序列排成上升序的。
一个排序问题。这里我们如下考虑：假如$a_j=i$，那么意味着$a_j$应该在$a_i$现在的位置上。由于这种交换没有步骤限制，我们可以在行动范围内任意的做出一些临时操作，所以我们的问题简化成了：$a_j$能否来到$i$这个位置。接下来考虑这样的$S=01111000110$，显而易见的是，$a_2\sim a_5$与$a_9\sim a_{10}$是可以无限互换的，那实际上这里就变成了一个很简单的情况：我们只需要考虑$j-i$这段区间内是否是连续的$1$。接下来我们考虑如何获得这个信息：我们把连续的$1$统计成距离，遇到$0$就重新统计，那么上面的$S$转化过后可得如下序列：$0,1,2,3,4,5,0,0,0,1,2,0$，那么我们就很容易可以计算两点间距离，上述问题就转化成$S’_i\ge j-i$的问题。那这样我们只需要扫一遍$S$做一下距离统计，再扫一遍原序列即可，$\mathcal{O}(n)$。
这一题又一次利用到了前缀和的统计优点，可以说前缀和统计是一个必备的区间统计技巧了，树状数组也是利用了这一个性质。
很有趣的一道题目。
这有一棵树，树有许多树枝，依次编号为$2\sim y$，同时，在$2\sim p$上各有一只蚂蚱，这些蚂蚱的跳跃能力很强：假如这只蚂蚱在$x$号树枝上，那么它可以跳跃到$2\cdot x, 3\cdot x,\cdots,\lfloor\frac{y}{x}\rfloor\cdot x$上。现在给出$y$和$p$，求最高的，不会被蚂蚱跳到的树枝的编号，如果没有这样的树枝，输出$-1$即可。
学过埃筛的一定知道这样的一个结论：一个数的两个不同的成对因子一定落在这个数的平方根两侧，也就是说，$\forall p<q, x=p\cdot q$满足$2\le p\le\sqrt{x}<q\le x$。这一题实际上就利用了这一个结论：我们对每一个数$k$来确认如下事实：$\exists x\in[2,p], x^2\le k\land x|k=0$，假如满足，那这个$k$不满足条件。那么我们直接倒序遍历$[p,y]$，来确认是否存在这样的$k$，存在即输出，否则输出$-1$即可。
这一点观察其实十分的简单：能够整除$x$的因子必定有一半在$[2,\lfloor\sqrt{x}\rfloor]$里面，所以我们检测这里面所有因子即可。更深入思考其实有一个更强的结论：第一个小于等于$x$的质数一定满足要求。所以我们直接使用埃筛的筛法寻找第一个数就可以了。
来自于质数筛的一个小结论，就这样变成了一道十分有趣的数论题，这也正是数学的魅力。
0x03. 难题
其实这两个月遗留了很多难题，但是刚好遇上开学，所以也没来得及补，这些题就留给下个月吧～