关于信息学奥赛的一些想法
模拟赛
以赛代练固然是一种挺不错的学习方式，但是我感觉一味的训练而不进行一些更深层的教学是不可取的。
举个例子：在平时做作业的时候，我们通常会拿出一定的时间来思考一些有难度的题目。这对于我们的学习帮助其实挺大的——这样才是有效的思考。而考试的时候，时间非常有限，如果拿出时间来研究一些不打打准能不能得分的题目，就是“没有策略”。信息学奥赛也是一样，我们在一次一次模拟赛的时候，看似是在思考问题，但是实际上我们不敢对一个难题花太多的时间，不然就有保龄的风险。
因此，我们需要深入的思考，而不是一次一次的模拟赛。切记，模拟赛不完全属于“深度思考”。
刷大模拟
大模拟没人愿意碰，但是有些人找虐就是想写。其实，我认为我们没必要把时间过多的放在这种没什么思维含量的地方上面。在可以预见的未来，敲代码将会变成一个 AI 的任务，因为它没有任何思维含量——准确来说，这个工作就是一门翻译，把人话翻译成 C++ 或者 Python。
大力 DS
有不少人都有过这种经历：一个题目，自己写了两个线段树、一个平衡树再加上个什么神秘 DS，最后死活调不出来，结果一问同学，发现其实根本用不到这些东西。
个人认为，没必要花 ...
Lucas定理
Part 0. 引子
众所周知：
Cmn=n!m!(n−m)!
C^n_{m}=\frac{n!}{m!(n-m)!}
Cmn=m!(n−m)!n!现在有个问题：
当 nnn，mmm 比较大的时候，直接用除法会寄掉（因为long long能够存储的数相对于阶乘而言小得可怜），此时一般会让你求出这个组合数对一个数取模的结果。但是除法不能直接取模，怎么办？
这个问题的答案还是比较显然的，我们只要用费马小定理求出阶乘的逆元。
然后第二个问题来了：
有多组测试数据，每组的取模都不一样，每一次都要求一个很大的组合数，怎么办？
对于这个问题，有一个非常简单的办法：想办法给出题人打 100 万，然后要到数据。
还有一个办法：
Part 1. Lucas 定理的证明
对于一个组合数：
Cpnmod p(p为素数,n≤p)
C^n_p \mod p(p 为素数,n \le p)
Cpnmodp(p为素数,n≤p)可以把它表示成这样的形式：
p!i!(p−i)!mod p
\frac{p!}{i!(p-i)!} \mod p
i!(p−i)!p!modp由于 ppp 是质数注意到分子（ ...
网络流（一）：最大流
Part 0. 场景
现在有一堆节点，每个节点连着一堆水管，每个水管有流量的限制（也就是说每个管子最多能流过多少水），现在从起点往里面猛灌水，问终点能得到多少水。
Part 1. 概念
弧：就是边
流量：流量
剩余流量：还能留多少水
反向弧
反向弧是一个非常重要的概念，基本上这个概念会应用于所有的算法中。
大抵就是这样：流过来多少水，就能流回去多少水。
也就是说，正反弧加一块肯定是原来的流量。这个概念其实很有用，后面细说。
Part 2. FF
FF 是远古时期的网络流算法，复杂度 O(m×Maxflow)O(m \times \text{Maxflow})O(m×Maxflow)。
这个算法说白了就是个大模拟。每一次都随便找一条从起点到终点的路径，然后给每一条边都减去这么多流量。
完了。真的。
不对！这玩意不是贪心吗？怎么证明正确性呢？或者说，大家可能非常轻松地就找到一些反例。哎哎哎你们别打我脸，我自己打：
显而易见，这里的最大流是这样两条增广路：
最大流为 444。
猛一看，这条路好像没问题。但是因为输入是随机的，你怎么会知道程序先走哪条边？如果他不是按照上面的方式来的，而 ...
高斯消元法
Part 0. 引子
小学，我们学习了一元一次方程。其标准形式如下：
ax=bax=b
ax=b
当 a≠0a \ne 0a=0 时方程有唯一解。
当 a=0,b≠0a=0,b \ne 0a=0,b=0 时方程无解。
当 a=0,b=0a=0,b=0a=0,b=0 时方程有无穷解。
到了初中，我们又学习了二元一次方程组。其标准形式如下：
{a1x+b1y=c1a2x+b2y=c2\left\{\begin{matrix}
a_1x+b_1y=c_1 \\
a_2x+b_2y=c_2
\end{matrix}\right.
{a1x+b1y=c1a2x+b2y=c2
将两个式子化作两个一次函数，则方程解情况如下：
当两直线相交的时候，方程有唯一解。
当两直线平行的时候，方程无解。
当两直线重合的时候，方程有无数解。
我们是怎么解这个方程的？
加减消元，带入消元。
说白了，高斯消元就是这样解 nnn 元一次方程。
Part 1. 高斯-约当消元法
首先，我们假设有一个方程组长这个样子：
{a11x1+a12x2+...+a1nxn=c1a21x ...
ABC281G 题解
ABC281G 题解
首先，我们会注意到显然如果存在长度为 lll 的路径，就一定会有一条长度为 l−1l-1l−1 的路径，因为每一条边的长度都是 111。
因此我们考虑在图上按照最短路径分层分层（其实就是按照 BFS 序分层）。会发现分层以后正好满足动态规划的性质。设 fi,jf_{i,j}fi,j 表示在 iii 个节点中，最后一层有 jjj 个节点的方案数，则有如下的等式：
fi,j=∑k=1i−jfi−j,k×(2k−1)j×2j(j−1)2×Cn−i+j−1jf_{i,j}=
\sum^{i-j}_{k=1}\color{red}f_{i-j,k}
\color{black}\times\color{green}(2^k-1)^j
\color{black}\times\color{blue}2^{\frac{j(j-1)}{2}}
\color{black}\times\color{purple}C^j_{n-i+j-1}
fi,j=k=1∑i−jfi−j,k×(2k−1)j×22j(j−1)×Cn−i+j−1j
下面我们来一点点拆分。
首先，kkk 表示倒 ...
manacher算法详解
Part 0. 引子
自己接触 OI 已经很长时间了，但是字符串仍然处于门外汉的尴尬境地。
于是，我决定狂补字符串。
Manacher（中文谐音马拉车），是解决最长回文串的一种高效算法。他能够在 Θ(n)\Theta(n)Θ(n) 的时间内解决这个问题，同时代码很简洁。
Part 1. 先聊聊暴力
暴力方式就是所谓的“中心扩展法”。说白了就是枚举每一个字符，然后往左右两边分别扩展，确定以这个字符为中心的回文有多长。
很明显，这个算法的时间复杂度是 O(n2)O(n^2)O(n2) 的。当然了，如果这个字符串长这个样子：
1qwertyuiopasdfghjklzxcvbnm
代码在进行计算的时候，啥也扩展不出去，每一次刚往外扩展了一格，就发现无法匹配。结果就是整个代码的运行几乎是 O(n)O(n)O(n) 的。
但是如果这个字符串长这个熊样呢？
1aaaaaaaaaaaaaaaaaaaaaaaaaaa
这个字符串和上面那个完全一样长，但是我们每一次都要扩展到两端才能停止。这就是个极为低效的 O(n2)O(n^2)O(n2) 了。
出题人肯定会用第二种数据，想办法卡掉暴力中心扩展法的。
...
9月7日——图论练习题目
NOIP2015提高组 信息传递
先读题，这个题目可以转化为一条 nnn 个点，nnn 条边的有向图，然后找到这里面的最小环。
那么我们就直接去找最小环？肯定不行啊。注意到这个题目中，
可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象
这其实就是说，这个图每个点的出度都是 111。
这个信息怎么用呢？先不急。我们先考虑特殊情况，即这个图是连通图。由于每一条边的出度都是 111，在 n−1n-1n−1 条边时这就是一个链，而有 nnn 条边的时候就是一个链连着一个环。用样例感受一下：
首先，这个图里面肯定有一个环（因为有 nnn 条边，并且这个有向图的出度为 111，如果不存在环，一定有一个点是没有出边的）。
其次，这个环肯定在链的后面（因为如果这个环后面还连着什么东西，那么这个环就一定有一个节点）
这样的话，我们随便找一个节点开始 DFS，就肯定能够找到环。
这个点在环上。这样的话，由于这个环已经到了链的末端，不可能再有出边，只要遍历一圈就一定能够找到这个环。
这个点在链上。这样的话，直接遍历到环上，转化为情况1。
最终怎么记录环的大 ...
8.20模拟测试
总述
这场难度差距比较大。T1签到题，可以直接暴力模拟，但是我直接写了个余数，然后是T2，比较简单的数学结论题，其实就是个三角形面积公式。由于搬题人事先没有了解，zzc也没作阻止（也可能是忘了），T3撞了，于是就集体A了。
接下来就是比较难的三个题了。T4其实也是结论题，然后结论题我一窍不通，然后就打了暴力，然后暴力挂了，然后就0分了（悲
T5是个很抽象的题，场上暴力还没写完就结束了（悲*2，这个题讲解的时候说要用bitset优化。
T6考试的时候我都没看，后来看了看，《根号分治》。
T2的结论
好吧好像有点偏题。这就是说在平面直角坐标系上的一个三角形，如果其中一个点是坐标系原点，那么他的面积就是
abs(x1y2−x2y1)2\frac{\text{abs}(x_1y_2-x_2y_1)}{2}
2abs(x1y2−x2y1)
如果不在也没关系，平移过去就行。于是这个题就是个简单枚举。当然了，理论上这个题目可以用海伦公式来做，但是出于 sqrt() 函数的精度问题以及计算机存储 double 类型的精度问题，这个方法不甚可取。我最开始没想到正解，于是就用海伦公式试了试，结果 ...
状压DP
Part 0. 引子
考虑这样的问题：有一排灯泡（n⩽15n \leqslant 15n⩽15），每一个灯泡可以是开着或者关着的，每次有许多操作方式，每一种会把一部分灯泡变成开着的，一部分变成关着的，初始时灯泡全部开着，问进行多少次操作才能使得这些灯泡全部熄灭？
显然这是一个DP题。由于 n<=15n<=15n<=15，一个可行的方式是这样做：
1int dp[2][2][2][2][2][2][2][2][2][2][2][2][2][2][2];
不过这样你自己都数不过来。另外，你怎么进行枚举呢？显然这样不是一个优秀的答案。我们考虑小学一年级就学过的字符串哈希，其中有一种就叫做进制哈希。不知道也没关系，其实我们可以把这里的灯泡状态变成一个二进制数，比如这样：
(101101011101000)2(101101011101000)_2
(101101011101000)2
就表示这样：
开，关，开，开，关，开，关，开，开，开，关，开，关，关，关
（当然，你也可以反过来写，都一样。）
这就是状压DP的思想，用一个二进制（当然也不绝对，也可以是三进制的，如果你觉得这个 ...