【博弈论】博弈论与SG函数
前文
从 ICD 到 DAG 的转化
DAG（有向无环图）可以用来代表任意一个 ICG 游戏。我们把 ICG 假设我们有两种点，一种为值为 1，代表从这个状态出发，先手必胜；另一种值为 0，代表从这个状态出发，先手必败。对于两种状态，把每一条有向边看作是状态的转移，我们可以得出以下连边规则：
第二条规则也是一个道理，如果我从这个状态转移能够让我的对手进入必败状态，那么对于当前的我来说我这个状态就是必胜的。
需要注意的是，虽然我们的有向边是从起点->终点的，且终点值为 0。但是实际上我们应该倒推，从一个状态的子状态可以得到这个状态，换句话说就是从终点 0 开始向后走，用现在处理的状态得到前一个状态。
但是这样会有问题，我们 1->1 的不好处理，不仅不知道实际情况，也不好知道转移的结果，所以需要用到下文的 SG 函数来辅助求解我们每一个状态的 SG 数，用 SG 数代替 01。
Sprague-Grundy 数的推导
SG 是 Sprague-Grundy 的缩写，查阅后才发现是两个人名，它使用起来非常简单，但是推导过程有些复杂。如果我们忽略推导过程直接去研究它的使用的话，你会有一种在运用魔法的感觉。因为你完全猜测不到它其中的原理，所以我们需要详细解释一下它的推导过程，这样才能加深理解。
首先我们定义一个概念，在一个状态节点$i$中，如果$SG[i]$大于零，则是必胜状态，如果如果$SG[i]$等于零，则是必败状态。那么这样就可以分开 1->1 的情况。
那么根据我们上面的守则，我们可以写出下面的更新过程：
$$ SG_{}\left(A\right)=mex\left\lbrace SG\left(B\right)\left|A\rightarrow B\right.\right\rbrace $$
式子中的A 和 B 表示状态，$A\rightarrow B$表示$A$状态可以达到$B$状态，也就是$B$是$A$的子状态。mex 是一个定义在集合上的函数，返回的是不属于这个集合的最小非负整数。比如$mex(0, 1)= 2$，$mex(0, 2) = 1$, $mex(0,1, 2, 3)=4$。那么我们就把上面啰嗦的三句话整合成了等价的一个$mex$函数。
最后还有一点，就是我一个子状态可能包含几个“孙状态”。比如有一道例题如下：
SG 的结论推导
这个是博弈论最最困难的地方，像通过 SG 函数与$mex$你可以很轻松求出每一个状态的 SG 值，但是实际应用中总是不切实际的——你不可能枚举每一个子状态再计算。这就要求选手通过有限的打表推断出普遍规律，这总是很难的。
每一道题目的结论都不相同，但宗旨就是——把对手扔到必败状态。具体来说就是我们可以锁定最后几个失败的状态找到他们与众不同的特点，虽然在中间满足这些特点的状态不一定是必败的，但是我们可以确定 ICG 游戏一定是会结束的，所以如果你可以让对手一直保持这个特点，那么只要走到终点状态，对手一定是必败的。
SG 的结论推导需要多刷多看才能找出其奥妙所在，有时候也可以根据题面找线索，比如二分图想到最大连通分量这些。但最后还是要看选手自己对数的理解——实在不行也有 SG 陪着你不是吗，不论如何，ICG 游戏只有先手必胜和先手必败两种情况，虽然打表找规律这种方法不甚高明，但是在比赛中也无可厚非了。
via サン猫の時間漂流
前文
有两个游戏者：$A$和$B$。有$n$颗石子。这类经典的 NIM 游戏（Impartial Combinatorial Games——ICG 游戏的一种）可以通过博弈论与Sprague-Grundy 数——SG 函数解决，当然其前提要求是 ICG 游戏，也就是公平组合游戏，它往往要满足以下要求。
约定：两人轮流取走石子，每次可取 1、2 或 3 颗。$A$先取，取走最后一颗石子的人获胜。
问题：$A$有没有必胜的策略？
1. 两名选手；本文将详细介绍如何通过基础博弈论与 SG 函数通过归纳数学解决此类问题。
2. 两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个；
3. 游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身；局面的改变称为“移动”(move)。
4. 若轮到某位选手时，该选手的合法操作集合为空，则这名选手判负。
需要说明的是，棋类游戏都不是 ICG 游戏，包括封面的国际象棋。
从 ICD 到 DAG 的转化
DAG（有向无环图）可以用来代表任意一个 ICG 游戏。我们把 ICG 假设我们有两种点，一种为值为 1，代表从这个状态出发，先手必胜；另一种值为 0，代表从这个状态出发，先手必败。对于两种状态，把每一条有向边看作是状态的转移，我们可以得出以下连边规则：
1. 一个状态是必败状态当且仅当它的所有后继都是必胜状态。第一条规则的含义很清楚了，如果我不管怎么走，我走之后对于对方来说永远都是必胜的，那么对我来说我这个状态就是必败的。
2. 一个状态是必胜状态当且仅当它至少有一个后继是必败状态。
第二条规则也是一个道理，如果我从这个状态转移能够让我的对手进入必败状态，那么对于当前的我来说我这个状态就是必胜的。
需要注意的是，虽然我们的有向边是从起点->终点的，且终点值为 0。但是实际上我们应该倒推，从一个状态的子状态可以得到这个状态，换句话说就是从终点 0 开始向后走，用现在处理的状态得到前一个状态。
但是这样会有问题，我们 1->1 的不好处理，不仅不知道实际情况，也不好知道转移的结果，所以需要用到下文的 SG 函数来辅助求解我们每一个状态的 SG 数，用 SG 数代替 01。
Sprague-Grundy 数的推导
SG 是 Sprague-Grundy 的缩写，查阅后才发现是两个人名，它使用起来非常简单，但是推导过程有些复杂。如果我们忽略推导过程直接去研究它的使用的话，你会有一种在运用魔法的感觉。因为你完全猜测不到它其中的原理，所以我们需要详细解释一下它的推导过程，这样才能加深理解。
首先我们定义一个概念，在一个状态节点$i$中，如果$SG[i]$大于零，则是必胜状态，如果如果$SG[i]$等于零，则是必败状态。那么这样就可以分开 1->1 的情况。
那么根据我们上面的守则，我们可以写出下面的更新过程：
1. 首先获得一个状态的所有子状态这个面向过程的更新多少有点繁琐，我们可以写一个$mex$函数一次解决，具体写法如下：
2. 如果子状态中有 0，说明这个是一个必胜状态，给它打上一个与子状态不同的标记
3. 如果子状态都大于 0，说明这是一个必败状态，就打上标记 0
$$ SG_{}\left(A\right)=mex\left\lbrace SG\left(B\right)\left|A\rightarrow B\right.\right\rbrace $$
式子中的A 和 B 表示状态，$A\rightarrow B$表示$A$状态可以达到$B$状态，也就是$B$是$A$的子状态。mex 是一个定义在集合上的函数，返回的是不属于这个集合的最小非负整数。比如$mex(0, 1)= 2$，$mex(0, 2) = 1$, $mex(0,1, 2, 3)=4$。那么我们就把上面啰嗦的三句话整合成了等价的一个$mex$函数。
最后还有一点，就是我一个子状态可能包含几个“孙状态”。比如有一道例题如下：
在一个平面上有$n$个点勾勒了一个凸四边形的轮廓，有两个游戏者$A$和$B$，每一个人可以连接任意两个点画出一条实线，要求实线不能交叉，一个点也不能被多次选择，问谁胜？在这个题目中，我举一个例子：当$n$为 4 时，我有两种子状态：连相近的两条边，剩下两个可以连接的边；还有连对角的两条边，剩下两个孤立的点。第一个很好判断，子状态就是$SG(2)$。而第二个子状态却是用两个孙状态拼起来的，也就是一个$SG(1+1)$，这与$SG(2)$是不等价的，我们规定$SG(A + B) = SG(A) xor SG(B)$，如果有多个孙状态，就是他们的异或和，如此一来就可以正常表示一个子状态了。
SG 的结论推导
这个是博弈论最最困难的地方，像通过 SG 函数与$mex$你可以很轻松求出每一个状态的 SG 值，但是实际应用中总是不切实际的——你不可能枚举每一个子状态再计算。这就要求选手通过有限的打表推断出普遍规律，这总是很难的。
每一道题目的结论都不相同，但宗旨就是——把对手扔到必败状态。具体来说就是我们可以锁定最后几个失败的状态找到他们与众不同的特点，虽然在中间满足这些特点的状态不一定是必败的，但是我们可以确定 ICG 游戏一定是会结束的，所以如果你可以让对手一直保持这个特点，那么只要走到终点状态，对手一定是必败的。
SG 的结论推导需要多刷多看才能找出其奥妙所在，有时候也可以根据题面找线索，比如二分图想到最大连通分量这些。但最后还是要看选手自己对数的理解——实在不行也有 SG 陪着你不是吗，不论如何，ICG 游戏只有先手必胜和先手必败两种情况，虽然打表找规律这种方法不甚高明，但是在比赛中也无可厚非了。
via サン猫の時間漂流
【线性代数】矩阵乘法与线性DP优化
前言
现在有一道题目如下：
概念
什么是矩阵（matrix）
下面是一个$2 \times 2$的矩阵，其中
$$\begin{bmatrix}{a} & {b} \ {c} & {d}\end{bmatrix}$$
关于矩阵的其他内容我们不再延申，你现在只要知道矩阵是这么样的一个东西就可以了。
矩阵可以用字母代表，那么矩阵 $A_{n \times m}$ 本质上是一个 n 行 m 列的二维数组。
矩阵乘法
矩阵之间可以相乘，并且满足结合律与分配律——不满足交换律，在$n \times m(n \ne m)$这种不是
$$ C*{n\times s}=A*{n\times m}:\times B_{m\times s} $$
那么它实际上就等于：
$$ C*{ij}=\sum A*{ik}\times B_{kj}\left(1:\le:k:\le:m\right) $$
其中 k 的遍历过程也就是
写成代码形式，就和弗洛伊德很像，可以把弗洛伊德看成是魔改的矩阵乘法：
用矩阵优化线性 DP
回到前言我们说的题目，这里回顾一下：
$$ \left[{f_{i-1}},:f_{i-2}\right]\times\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]=\left[{f_i},:f_{i-1}\right] $$
因为是线性的，所以我们很容易发现，每一转移其实就是当前的状态矩阵乘上我们的$\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]$，那么每转移一次，i 就加一，我们先处理出$f_1,f_2$，那么通过$n-2$次转移，我们就可以得到$f_n$的值。
延伸
所有类似于这样的线性 DP 都可以用矩阵来转移，比如$f_i = f_{i-1} + f_{i-3} + f_{i-4}$，这种转移，我们可以构造下面这一个转移矩阵：
$$ \begin{bmatrix}1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 \ 1 & 0 & 0 & 1\end{bmatrix} $$
然后使用快速幂可以把时间复杂度从$O(N)$优化到$O(k^3 \log N)$ ，其中 k 是状态是数量，也就是转移矩阵的边长。
下面是实例代码，可以解决$f_i = f_{i-1} + f_{i-3} + f_{i-4}$求解$f_n$并且$n \leq 10^{18}$的情况。
via サン猫の時間漂流
前言
现在有一道题目如下：
输入一个整数 n ($n \leq 10^{18}$)， 求第 n 个斐波那契数。众所周知斐波那契数列的递推公式是：$f_i = f_{i-1} + f_{i-2}$。通过$O(N)$的时间递推可以在 1s 内求出前 1e8 的斐波那契数，但是题目的范围是 1e18，这要怎么办呢？这时候就要引出我们今天要学习的内容——矩阵与矩阵乘法了。
概念
什么是矩阵（matrix）
下面是一个$2 \times 2$的矩阵，其中
a，b，c，d，是里面的元素，矩阵里的元素可以是数字符号或者数学式。$$\begin{bmatrix}{a} & {b} \ {c} & {d}\end{bmatrix}$$
关于矩阵的其他内容我们不再延申，你现在只要知道矩阵是这么样的一个东西就可以了。
矩阵可以用字母代表，那么矩阵 $A_{n \times m}$ 本质上是一个 n 行 m 列的二维数组。
矩阵乘法
矩阵之间可以相乘，并且满足结合律与分配律——不满足交换律，在$n \times m(n \ne m)$这种不是
正方形的矩阵中，交换前后两个矩阵相乘会导致结果矩阵的形状不同，我们会在后面解释。矩阵相乘时，相乘矩阵的宽高必须有一个相同，否则无法配对。比如下面这个式子，把矩阵$A \times B = C$，可以这样写：
$$ C*{n\times s}=A*{n\times m}:\times B_{m\times s} $$
那么它实际上就等于：
$$ C*{ij}=\sum A*{ik}\times B_{kj}\left(1:\le:k:\le:m\right) $$
其中 k 的遍历过程也就是
相乘矩阵的宽高必须有一个相同的原因，否则匹配不了。写成代码形式，就和弗洛伊德很像，可以把弗洛伊德看成是魔改的矩阵乘法：
for(int i = 1; i <= an; i++)
for(int k = 1; k <= am; k++)
for(int j = 1; j <= bm; j++)
c[i][j] = c[i][j] + a[i][k] * b[k][j];
用矩阵优化线性 DP
回到前言我们说的题目，这里回顾一下：
输入一个整数 n ($n \leq 10^{18}$)， 求第 n 个斐波那契数。我们每一次转移可以用一个矩阵表示：
$$ \left[{f_{i-1}},:f_{i-2}\right]\times\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]=\left[{f_i},:f_{i-1}\right] $$
因为是线性的，所以我们很容易发现，每一转移其实就是当前的状态矩阵乘上我们的$\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]$，那么每转移一次，i 就加一，我们先处理出$f_1,f_2$，那么通过$n-2$次转移，我们就可以得到$f_n$的值。
延伸
所有类似于这样的线性 DP 都可以用矩阵来转移，比如$f_i = f_{i-1} + f_{i-3} + f_{i-4}$，这种转移，我们可以构造下面这一个转移矩阵：
$$ \begin{bmatrix}1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 \ 1 & 0 & 0 & 1\end{bmatrix} $$
然后使用快速幂可以把时间复杂度从$O(N)$优化到$O(k^3 \log N)$ ，其中 k 是状态是数量，也就是转移矩阵的边长。
下面是实例代码，可以解决$f_i = f_{i-1} + f_{i-3} + f_{i-4}$求解$f_n$并且$n \leq 10^{18}$的情况。
这里因为乘的顺序不一样（交换了），矩阵不能使用交换律，所以转移矩阵稍有不同。（实际上一般情况下习惯把系数放在第一行，也就是代码中转移矩阵的样子）
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;
matrix multiply(matrix a, matrix b, ll mod)
{
ll n = a.size();
matrix c(n, vector<ll>(n));
for (ll i = 0; i < n; i++)
for (ll j = 0; j < n; j++)
for (ll k = 0; k < n; k++)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
return c;
}
matrix matrix_pow(matrix a, ll n, ll mod)
{
ll m = a.size();
matrix res(m, vector<ll>(m));
for (ll i = 0; i < m; i++)
res[i][i] = 1;
while (n)
{
if (n & 1)
res = multiply(res, a, mod);
a = multiply(a, a, mod);
n >>= 1;
}
return res;
}
int main()
{
matrix a = {{1, 0, 1, 1},
{1, 0, 0, 0},
{0, 1, 0, 0},
{0, 0, 1, 0}}; // 转移矩阵
ll n;
scanf("%lld", &n); // 2, 4, 6, 9
matrix ans = matrix_pow(a, n - 4, 10007);
printf("%lld", (ll)(2 * ans[0][3] + 4 * ans[0][2] + 6 * ans[0][1] + 9 * ans[0][0]) % 10007);
return 0;
}
via サン猫の時間漂流
【题解】7月11日比赛题解备份
一．重复字符串(powerstr):
30分做法：枚举
长度范围只有 1000 时，我们可以枚举 k， 取字符串第 1 个到第 k 个字符作为子串 T，然后去验证剩下的字符串是否都是 T 重复得来
时间复杂度 O(n^2)
100分做法：KMP，Next数组
假设字符串为 S，长度为 N，子串 T 重复 K 次后得到串 S，那么 T 的长度一定为 L = N/K(要整除)，则$T = S[1...L]$，将 S 拆分成 K 份，每份长度为 L，则有
$$S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]$$
由于要保证 K 最大，势必 L 要取最小，所以根据 Next 函数的定义，有$Next[KL] = (K-1)L;$
即$Next[N] = N - L$，所以$L = N - Next[N];$
但是得出的长度 L 还要保证能被 N 整除，所以如果不能整除说明 L = N，即 K = 1；而如果能整除，那么$K = N / (N - Next[N]);$
因而我们只要对字符串 S 做一趟 KMP，对其求 Next 数组，剩下的就是上述结论
时间复杂度$O(n)$
二．Fibonacci 进制(fib):
100分做法：DP
N 很大，先尝试几个小数据。可以发现，每个 Fibonacci 表示的长度，和 Fibonacci 数大小有关（1,2,3,5,8,13,21……），这些值最高位上是 1，后面全是 0，即第一个 Fibonacci 表示长度为 i 的数是$fib[i]$。因此按照长度对 Fibonacci 表示进行分类，长度为 i 的数有$fib[i-1]$个，看做是第 i 组。那么第 i 组的总长度$len[i] = fib[i-1]*i$。
接下来，看 1 出现的次数。长度为 i 的数的表示中，第 i-1 位肯定是 0。
$Sum[i]$表示前 i 组的 1 的个数。可以得到如下式子：$Sum[i]=sum[i-1]+fib[i-1]+sum[i-2]$。第 i 组首位 1 的个数为$fib[i-1]$，$i-1$位为 0，那么最后的 i-2 位的情况，恰好为 1~i-2 组的所有情况。
整体算法也就明了了：
1. 求出 N 位所在的 Fibonacci 表示的数的长度 t
2. 求 1~t 中 Fibonacci 表示中 1 出现的个数。
3. 继续求解剩余字符的 1。
4. 最后一个暴力扫描
例如求解得到最后对应 Fibonacci 表示为 x=100100
1. 对于长度为 1~5 的 Fibonacci 表示中 1 的个数为$sum[5]$，i<=100000 中 1 的个数即为$sum[5]+1$。
2. 对于 100000<i<=100100,最高位都是 1，共有$fib[3]$个，后三位 1 的个数为$sum[2]+1$。
3. 1 的总个数为$sum[5]+1+fib[3]+sum[2]+1$。
最后细节比较多，要实现的仔细一些。
三.发奖金(reword):
100*分做法：组合+质因数分解+逆元+中国剩余定理
题目相当于求 n 个数的和不超过 m 的方案数。
首先如果是恰好等于 m，那么就等价于求方程$x_{1} + x_{2} + ... + x_{n} = m$的解的个数，利用插板法可得到公式：$C(n + m - 1, m)$ 现在要求不大于 m 的，相当于对$i = 0 ... m$对$C(n + i - 1, i)$求和，根据 pascal 递推式可以得到答案为$C(n + m, m)$ 现在就需要求$C(n + m, m) \mod P$
这里我们主要要解决如何快速计算$n! \mod P$
以及当分母有$m! \mod P$的情况
1. 当 n,m 都比较小的时候，同时 P 为比较大的素数时，可以直接利用逆元求解，当 n,m 比较大的时候，见下面两种情况（以下参考魏铭 2011 年国家集训队作业）
2. 当 P 为素数的情况：
我们发现$n! \mod P$的计算过程是以 P 为周期的，举例如下：
$$n = 10, P = 3$$ $$n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10$$ $$= 1 * 2 * 4 * 5 * 7 * 8 * 10 * 3 * 6 * 9$$ $$= (1 * 2)^3 * 3^3 * (1 * 2 * 3)$$
最后一步中的$1 * 2 *3$可递归处理。
因为 P 的倍数与 P 不互质，所以 P 的倍数不能直接乘入答案，应当用一个计数器变量 cnt 来保存答案中因子 P 的个数。
我们提前预处理出$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$，函数 calcfac(n)返回$n! \mod P$的值，power(a, b, c)返回$a^b \mod c$的值，可用快速幂在$O(logb)$的时间内完成。
于是$n! \mod p$的计算可在$O(logn)$的时间内解决。
对于分母中的 n!，方法是相似的。若 a 为正整数，$a * a’ = 1(\mod P)$，那么我们称 a’为 a 的逆元，记作 a-1，并有$b / a(\mod P) = b * a-1(\mod P)$。这样我们只需要把预处理$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$更换为$inv[i] = 1-1 * 2-1 * 3-1* … * (i – 1) -1 * i-1 \mod P$，其计算方法与分子中的 n!计算相差无几，具体可参考我的代码。求逆元可以使用扩展欧几里得算法。
3. 当 p 为合数时
对于某些测试点，我们发现 P 分解后只有 2 个因子，并且不相同，所以我们可以对这两个因子分别运行算法 2，最后用中国剩余定理合并即可。
对于剩下的数据，可以对 P 进行质因数分解，得到$P = p1^{c1} * p2^{c2} * … * pt^{ct}$。
对于每个$1≤i≤t$，以$pi^{ci}$为模运行算法 2，最后用中国剩余定理合并。这里$pi^{ci}$不一定为质数，不过只需对原算法稍加修改即可。令$P = pi^{ci}$，$fac[i] = 除去pi的倍数外i的阶乘$。例如$pi = 3,ci = 2$，那么$fac[10] = 1 * 2 * 4 * 5 * 7 * 8 * 10$，除去了 3 的倍数 3、6 和 9。阶乘依然是以 P 为周期的，calcfac(n)与算法 2 主体相同，只是统计因子个数时，应使用$ret += n / pi$而不是$ret += n / P$，递归处理时也应该是 calcfac(n / pi)而不是 calcfac(n / P)。
时间复杂度$O(t * n)$
via サン猫の時間漂流
一．重复字符串(powerstr):
30分做法：枚举
长度范围只有 1000 时，我们可以枚举 k， 取字符串第 1 个到第 k 个字符作为子串 T，然后去验证剩下的字符串是否都是 T 重复得来
时间复杂度 O(n^2)
100分做法：KMP，Next数组
假设字符串为 S，长度为 N，子串 T 重复 K 次后得到串 S，那么 T 的长度一定为 L = N/K(要整除)，则$T = S[1...L]$，将 S 拆分成 K 份，每份长度为 L，则有
$$S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]$$
由于要保证 K 最大，势必 L 要取最小，所以根据 Next 函数的定义，有$Next[KL] = (K-1)L;$
即$Next[N] = N - L$，所以$L = N - Next[N];$
但是得出的长度 L 还要保证能被 N 整除，所以如果不能整除说明 L = N，即 K = 1；而如果能整除，那么$K = N / (N - Next[N]);$
因而我们只要对字符串 S 做一趟 KMP，对其求 Next 数组，剩下的就是上述结论
时间复杂度$O(n)$
二．Fibonacci 进制(fib):
100分做法：DP
N 很大，先尝试几个小数据。可以发现，每个 Fibonacci 表示的长度，和 Fibonacci 数大小有关（1,2,3,5,8,13,21……），这些值最高位上是 1，后面全是 0，即第一个 Fibonacci 表示长度为 i 的数是$fib[i]$。因此按照长度对 Fibonacci 表示进行分类，长度为 i 的数有$fib[i-1]$个，看做是第 i 组。那么第 i 组的总长度$len[i] = fib[i-1]*i$。
接下来，看 1 出现的次数。长度为 i 的数的表示中，第 i-1 位肯定是 0。
$Sum[i]$表示前 i 组的 1 的个数。可以得到如下式子：$Sum[i]=sum[i-1]+fib[i-1]+sum[i-2]$。第 i 组首位 1 的个数为$fib[i-1]$，$i-1$位为 0，那么最后的 i-2 位的情况，恰好为 1~i-2 组的所有情况。
整体算法也就明了了：
1. 求出 N 位所在的 Fibonacci 表示的数的长度 t
2. 求 1~t 中 Fibonacci 表示中 1 出现的个数。
3. 继续求解剩余字符的 1。
4. 最后一个暴力扫描
例如求解得到最后对应 Fibonacci 表示为 x=100100
1. 对于长度为 1~5 的 Fibonacci 表示中 1 的个数为$sum[5]$，i<=100000 中 1 的个数即为$sum[5]+1$。
2. 对于 100000<i<=100100,最高位都是 1，共有$fib[3]$个，后三位 1 的个数为$sum[2]+1$。
3. 1 的总个数为$sum[5]+1+fib[3]+sum[2]+1$。
最后细节比较多，要实现的仔细一些。
三.发奖金(reword):
100*分做法：组合+质因数分解+逆元+中国剩余定理
题目相当于求 n 个数的和不超过 m 的方案数。
首先如果是恰好等于 m，那么就等价于求方程$x_{1} + x_{2} + ... + x_{n} = m$的解的个数，利用插板法可得到公式：$C(n + m - 1, m)$ 现在要求不大于 m 的，相当于对$i = 0 ... m$对$C(n + i - 1, i)$求和，根据 pascal 递推式可以得到答案为$C(n + m, m)$ 现在就需要求$C(n + m, m) \mod P$
这里我们主要要解决如何快速计算$n! \mod P$
以及当分母有$m! \mod P$的情况
1. 当 n,m 都比较小的时候，同时 P 为比较大的素数时，可以直接利用逆元求解，当 n,m 比较大的时候，见下面两种情况（以下参考魏铭 2011 年国家集训队作业）
2. 当 P 为素数的情况：
我们发现$n! \mod P$的计算过程是以 P 为周期的，举例如下：
$$n = 10, P = 3$$ $$n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10$$ $$= 1 * 2 * 4 * 5 * 7 * 8 * 10 * 3 * 6 * 9$$ $$= (1 * 2)^3 * 3^3 * (1 * 2 * 3)$$
最后一步中的$1 * 2 *3$可递归处理。
因为 P 的倍数与 P 不互质，所以 P 的倍数不能直接乘入答案，应当用一个计数器变量 cnt 来保存答案中因子 P 的个数。
我们提前预处理出$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$，函数 calcfac(n)返回$n! \mod P$的值，power(a, b, c)返回$a^b \mod c$的值，可用快速幂在$O(logb)$的时间内完成。
typedef long long LL;
LL calcfac(LL n)
{
if (n <P) return fac[n];
LL seg = n / P, rem = n % P;
LL ret = power(fac[P - 1], seg, P); //fac[P - 1]重复出现了seg次
ret = ret * fac[rem] % P; //除去seg次fac[P – 1]外，剩下的零头
cnt += n / P; //提出n / P个因子P
ret = ret * calcfac(n / P) % P; //递归处理
return ret;
}
于是$n! \mod p$的计算可在$O(logn)$的时间内解决。
对于分母中的 n!，方法是相似的。若 a 为正整数，$a * a’ = 1(\mod P)$，那么我们称 a’为 a 的逆元，记作 a-1，并有$b / a(\mod P) = b * a-1(\mod P)$。这样我们只需要把预处理$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$更换为$inv[i] = 1-1 * 2-1 * 3-1* … * (i – 1) -1 * i-1 \mod P$，其计算方法与分子中的 n!计算相差无几，具体可参考我的代码。求逆元可以使用扩展欧几里得算法。
3. 当 p 为合数时
对于某些测试点，我们发现 P 分解后只有 2 个因子，并且不相同，所以我们可以对这两个因子分别运行算法 2，最后用中国剩余定理合并即可。
对于剩下的数据，可以对 P 进行质因数分解，得到$P = p1^{c1} * p2^{c2} * … * pt^{ct}$。
对于每个$1≤i≤t$，以$pi^{ci}$为模运行算法 2，最后用中国剩余定理合并。这里$pi^{ci}$不一定为质数，不过只需对原算法稍加修改即可。令$P = pi^{ci}$，$fac[i] = 除去pi的倍数外i的阶乘$。例如$pi = 3,ci = 2$，那么$fac[10] = 1 * 2 * 4 * 5 * 7 * 8 * 10$，除去了 3 的倍数 3、6 和 9。阶乘依然是以 P 为周期的，calcfac(n)与算法 2 主体相同，只是统计因子个数时，应使用$ret += n / pi$而不是$ret += n / P$，递归处理时也应该是 calcfac(n / pi)而不是 calcfac(n / P)。
时间复杂度$O(t * n)$
via サン猫の時間漂流
【图论】双连通分量
前言
在学习双连通分量之前请先了解强连通分量，有助于理解双连通分量，其中相同的概念不再赘述。
概念
强连通分量是对于有向图而言的，而双连通分量是对于无向图而言的。
割边与割点
在无向图中， 割点：去掉一个点及与其相邻的所有边，无向图中的连通分量增加，则称该点为割点。 割边：去掉一条边，无向图中的连通分量增加，则称该边为割边。 割点与割边的关系：
1. 有割点不一定有割边，有割边一定有割点。
2. 割边的两个端点中一定有一个是割点。
什么是双连通分量
根据上面割边与割点的定义，我们可以把双连通分量分成边双和点双两种。
1. 边双：对于一个图，假如仅仅对于该图而言其中没有割边，那么我们称这个图是边双联通的。那么一个极大的边双连通子图就是母图的边双连通分量。也就是说在这个子图中任意删去一条边，每一个点之间仍然是连通的。
2. 点双：对于一个图，假如仅仅对于该图而言其中没有割点，那么我们称这个图是点双联通的。那么一个极大的点双连通子图就是母图的点双连通分量。也就是说在这个子图中任意删去一个点和那些与之相邻的边，每一个点之间仍然是连通的。
求双连通分量
先观察
via サン猫の時間漂流
前言
在学习双连通分量之前请先了解强连通分量，有助于理解双连通分量，其中相同的概念不再赘述。
我的强连通分量笔记在：【图论】强连通分量
概念
强连通分量是对于有向图而言的，而双连通分量是对于无向图而言的。
割边与割点
在无向图中， 割点：去掉一个点及与其相邻的所有边，无向图中的连通分量增加，则称该点为割点。 割边：去掉一条边，无向图中的连通分量增加，则称该边为割边。 割点与割边的关系：
1. 有割点不一定有割边，有割边一定有割点。
2. 割边的两个端点中一定有一个是割点。
详细内容请阅读：【图论】割边与割点
什么是双连通分量
根据上面割边与割点的定义，我们可以把双连通分量分成边双和点双两种。
1. 边双：对于一个图，假如仅仅对于该图而言其中没有割边，那么我们称这个图是边双联通的。那么一个极大的边双连通子图就是母图的边双连通分量。也就是说在这个子图中任意删去一条边，每一个点之间仍然是连通的。
2. 点双：对于一个图，假如仅仅对于该图而言其中没有割点，那么我们称这个图是点双联通的。那么一个极大的点双连通子图就是母图的点双连通分量。也就是说在这个子图中任意删去一个点和那些与之相邻的边，每一个点之间仍然是连通的。
需要注意的是点双与强连通分量和边双不同，它会与其他点双相交，需要注意
求双连通分量
先观察
via サン猫の時間漂流
【数据结构】邻接表与链式前向星
邻接表（使用 vector）
存图方式
遍历方式
添加方式
----------------------
链式前向星
存图方式
遍历方式
添加方式
via サン猫の時間漂流
邻接表与链式前向星更正： 使用vector存图的叫做邻接表使用数组模拟的叫做链式前向星
邻接表（使用 vector）
使用邻接表的优劣： 优势：
1. 码量少，易操作
2. 不用担心空间，不易写错
劣势：
1. cpp11 之前不能使用auto v : i形式遍历 vector
2. 在不能开启O2的题目中较慢（POJ 全占）
存图方式
struct line // 自定义结构体
{
int ver; // 指向的结点
int edge; // 边的权值
line(int v, int e) // 构造函数
{
ver = v;
edge = e;
}
};
vector<line> g[MAX]; // 新建邻接表
遍历方式
对于 C++11 后的 OJ，使用如下方式遍历：
// line是结构体的名字
// from是父节点的下标
for(line son : g[crd])
{
// 示例代码，含义为不经过父节点
if(son.ver == from) continue;
}
对于 C++11 前的 OJ，使用如下方式遍历其实这里建议使用链式前向星，因为不支持 C++11 的 OJ 很可能没有 O2
// line是结构体名字
for (line son = g.begin(); son != g.end(); son++)
// 下略……
添加方式
// N为边的数量
for(int i = 1; i < N; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back(line(v, w));
g[v].push_back(line(u, w));
}
----------------------
链式前向星
使用链式前向星的优劣： 优势：
1. 速度快，无需O2
2. 不受 C++版本限制，适用于所有题目
劣势：
1. 数组模拟链表，初学者不易理解
2. 码量多，不理解容易打错，不易 Debug
存图方式
struct line
{
int ver; // 指向的结点
int next; // 下一条边
// int edge; // 边的权值
}node[MAX * 2]; // 新建链式前向星
int head[MAX]; // 表头数组
遍历方式
for(int son = head[crd]; son; son = node[son].next)
// 下略……
添加方式
// 前向星添加边（使用函数）
// tot为所有边的数量，初始值为0
void add(int u, int v/*, int edge*/)
{
node[++tot].next = head[u];
node[tot].ver = v;
//node[tot].edge = edge;
head[u] = tot;
}
via サン猫の時間漂流
【动态规划】状态压缩DP
前言
二进制的很多应用离不开集合这个概念，我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个 int 整形是 4 个字节，也就是 32 位 bit，我们通过这 32 位 bit 上 0 和 1 的组合可以表示多大 21 亿个不同的数。如果我们把这 32 位 bit 看成是一个集合，那么每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的。那么我们可不可以用一个数来保存一维的 DP 状态呢？
这当然是可行的，动态规划的过程是随着阶段的增长，在每一个状态维护上不断扩展的。而对于某些题目，我们扩展时需要记录一个状态集合，保存状态信息，以便进行状态转移。而状态压缩则是把这一个大小不超过 N、元素小于 K 的集合看做是一个 N 位的 K 进制数，以一个$[0, K^N - 1]$之间的十进制整数的形式作为 DP 状态的一维。这样我们就可以只用一个十进制整数，就保存了一个状态信息——这就是状态压缩。
状态压缩的题目一般只有两种状态（当然也有三种状态的
集合操作
在二进制状态 DP 中，我们用一个十进制整数代表一个集合，例如：$9 -> (1001)_{2}$ ，可以等效替换为一个 bool 数组$B[4] = {1, 0, 0, 1}$。下面是集合的常用操作：
| 操作含义 | 代码 | | :abbrlink: 122ed47c mathjax: true categories:
● OI 学习笔记
● 动态规划 pubDate: 2023-06-10 00:00:00 tags:
● 优化
● 状态压缩
● DP
● 动态规划
● cpp
● OI title: 【动态规划】状态压缩 DP badge: old
----------------------
-----------------------------------: | :----------------: | | 取出整数 n 在二进制表示下的第 k 位 | (n >> k) & 1 | | 取出整数 n 在二进制表示下的第 0k-1 位（后 k 位） | n & ((1 << k) - 1) | | 把整数 n 在二进制下表示的第 k 位取反 | n ^ (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 1 | n| (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 0 | n & ( (1 << k)) | | 判断整数 n 在二进制表示下的第 k 位是否为真 | n & (1 << (k - 1)) |
上机实践
售货员的难题
构思（朴素算法）
看一下题目……最短路是吧？但是要求经过所有结点。
所以优先队列 BFS 最短路这种就不管用啦！那么既然要走过所有村庄，直接枚举全排列输出，暴力省事。时间复杂度为$O(N * N!)$，属于是必死无疑。
下面给出一段基础搜索代码，包含基础剪枝，得分$80Pt$.
via サン猫の時間漂流
前言
二进制的很多应用离不开集合这个概念，我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个 int 整形是 4 个字节，也就是 32 位 bit，我们通过这 32 位 bit 上 0 和 1 的组合可以表示多大 21 亿个不同的数。如果我们把这 32 位 bit 看成是一个集合，那么每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的。那么我们可不可以用一个数来保存一维的 DP 状态呢？
这当然是可行的，动态规划的过程是随着阶段的增长，在每一个状态维护上不断扩展的。而对于某些题目，我们扩展时需要记录一个状态集合，保存状态信息，以便进行状态转移。而状态压缩则是把这一个大小不超过 N、元素小于 K 的集合看做是一个 N 位的 K 进制数，以一个$[0, K^N - 1]$之间的十进制整数的形式作为 DP 状态的一维。这样我们就可以只用一个十进制整数，就保存了一个状态信息——这就是状态压缩。
状态压缩的题目一般只有两种状态（当然也有三种状态的
三进制题目）。这里只讨论最常见的二进制状态压缩，K 进制状态压缩可以以此类推，不再赘述。集合操作
在二进制状态 DP 中，我们用一个十进制整数代表一个集合，例如：$9 -> (1001)_{2}$ ，可以等效替换为一个 bool 数组$B[4] = {1, 0, 0, 1}$。下面是集合的常用操作：
| 操作含义 | 代码 | | :abbrlink: 122ed47c mathjax: true categories:
● OI 学习笔记
● 动态规划 pubDate: 2023-06-10 00:00:00 tags:
● 优化
● 状态压缩
● DP
● 动态规划
● cpp
● OI title: 【动态规划】状态压缩 DP badge: old
----------------------
-----------------------------------: | :----------------: | | 取出整数 n 在二进制表示下的第 k 位 | (n >> k) & 1 | | 取出整数 n 在二进制表示下的第 0k-1 位（后 k 位） | n & ((1 << k) - 1) | | 把整数 n 在二进制下表示的第 k 位取反 | n ^ (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 1 | n| (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 0 | n & ( (1 << k)) | | 判断整数 n 在二进制表示下的第 k 位是否为真 | n & (1 << (k - 1)) |
注意了！我们常说的第一位在二进制表示下其实是第零位，程序实现时一定要注意当前真正在操作的是哪一位，否则 WA 了很难找出错误。
上机实践
售货员的难题
经典例题，状态压缩 DP 入门题：P1171 售货员的难题。
构思（朴素算法）
看一下题目……最短路是吧？但是要求经过所有结点。
所以优先队列 BFS 最短路这种就不管用啦！那么既然要走过所有村庄，直接枚举全排列输出，暴力省事。时间复杂度为$O(N * N!)$，属于是必死无疑。
下面给出一段基础搜索代码，包含基础剪枝，得分$80Pt$.
#include<cstdio>
using namespace std;
int lxy[21][21],hrb[21];
int n,i,j,k,minn=1e9;
int ss(int x,int y,int z)//x表示村子编号，y表示走了几个村子，z表示用的时间
{
if(z > minn) return 0;//基本最小值剪枝
if(y == n && z + lxy[x][1] < minn)
{
minn = z + lxy[x][1];
return 0;
}//比较求最小值，其中的加lxy[x][1]意思是走回第一个村
for(int i = 2; i <= n; i++)//循环开始
{
if(hrb[i]==0&&i!=x)//深搜模板，没走就搜
{
hrb[i] = 1;//打上标记
ss(i,y + 1, z + lxy[x][i]);
hrb[i] = 0;//回溯
}
}
return 0;
}
int main()
{
scanf("%d", &n);
for(i = 1;i <= n; i++)
for(k = 1;k <= n; k++)
scanf("%d", &lxy[i][k]);//输入
ss(1, 1, 0);//开搜
printf("%d",minn);
}
via サン猫の時間漂流
【动态规划】LIS与LCS（最长上升子序列）
引子-LIS 问题
这几天在学习DP（动态规划），里面第一个接触到的问题就是LIS问题，这里简单概述如下:
----------------------
LIS 的朴素解法
最朴素的想法就是用一个数组$DP[i]$表示在$1-i$范围内的 LIS 长度，初始化$DP[i]$为$1$（它自己一个数作为一个 LIS）。如果在小于$1-i$的范围内有满足 LIS 定义的情况，就可以转移$DP[i]$的值，代表选入这个范围和$A[i]$做为 LIS 的一部分。
我们要遍历到$DP[i]$时同时遍历所有在$1-i$内的状态，显然每次转移都是$O(N)$的时间复杂度，总复杂度为$O(N^2)$，状态转移方程如下：
$DP[i] = max(DP[i], DP[j] + 1) | (j < i)$
显然$O(N^2)$的时间复杂度是无法满足 OIer 的，因此我们要进行优化。
----------------------
LIS 的贪心二分优化
优化思路
为什么朴素算法慢呢？因为我们把所有情况枚举了一遍，而最后留下的只有一种。LIS 的朴素算法在那些本不需要枚举的状态上浪费了时间，自然就不行了。
我们知道，LIS 是一个严格单增的数列，那么在两个 LIS 长度相同的情况下，我们希望它能扩展到的长度尽可能长，自然是希望LIS 结尾元素尽可能小。那么思路就有了，我们使用一个数组$G[i]$保存长度为$i$的 LIS 的结尾元素值记录当前最长的 LIS 长度为$tot$，对于每一个$A[i]$，如果$A[i] > G[tot]$，说明当前可以把$A[i]$接到这一条所谓最长的 LIS 后面，则$G[++tot] = A[i]$。
那么我们的问题就是如何维护$G$数组。其实很简单，思路就是我们上面的思路，但是有一个问题，如果$A[i] \leq G[tot]$，应该怎么办呢？
那么根据我们的优化思路，我们要尽可能确保当前$G$数组里面存储的是当前长度为$i$的 LIS 序列的最优解，也就是
二分优化
显然，$G$数组是一个单调递增的数组，自然地可以使用二分查找优化时间复杂度。把时间复杂度降到$O(N,log,N)$级别。
代码整合
那么到目前为止，我们亲爱的$DP$数组就寿终正寝了，换成了我们新的$G$数组（
下面是代码示例，基础 LIS：
LIS 例题
这里给出一道 LIS 模板题：导弹拦截 LIS 经典。
将拦截的导弹的高度提出来成为原高度序列的一个子序列，根据题意这个子序列中的元素是单调不增的（即后一项总是不大于前一项），我们称为单调不升子序列。本问所求能拦截到的最多的导弹，即求最长的单调不升子序列。（其实只要判断改一下就好啦！）
第一问
没什么好说的，跑一次示例代码完事。
第二问
那么既然是单调不升子序列，我们考虑朴素算法，那么$G$数组就要求存储最大的值，每次执行完一次计算，就把选中的元素移除。重复计算，直到全部移除，记录计算次数，输出为答案。
但是这样显然太笨了！我们要优化优化优化！
我们不妨改变一下$G$数组的含义，用$G[i]$存第$i$个系统当前能够拦截的高度，同时我们把这些系统按从小到大排列——类似于原来的$G$数组。显然每次遍历到导弹$A[i]$时，我们拿最小的$G[i] \geq A[i]$是最优解。然后更新$G[i]$的值，显然更新之后排列还是从小到大，$G$数组仍然是单调递增的，因此不需要重新排序。当然如果没有满足$G[i] \geq A[i]$的情况，就新增一个系统。
只要我们仍然保存时间复杂度在$O(N,log,N)$ 级别，可以通过$10^5$的数据。
代码整合
下面是 AC 代码：
via サン猫の時間漂流
引子-LIS 问题
这几天在学习DP（动态规划），里面第一个接触到的问题就是LIS问题，这里简单概述如下:
给定一个长度为$N$的数列$A$，求数值单调递增的子序列的的长度最长是多少？其中 LIS（最长上升子序列）指的是从序列 A 中选择若干个 i，使得$i_{1}<i_{2}<i_{3}...<i_{n}$的同时满足$A_{i_{1}}<A_{i_{2}}<A_{i_{3}}...<A_{i_{n}}$。
----------------------
LIS 的朴素解法
最朴素的想法就是用一个数组$DP[i]$表示在$1-i$范围内的 LIS 长度，初始化$DP[i]$为$1$（它自己一个数作为一个 LIS）。如果在小于$1-i$的范围内有满足 LIS 定义的情况，就可以转移$DP[i]$的值，代表选入这个范围和$A[i]$做为 LIS 的一部分。
我们要遍历到$DP[i]$时同时遍历所有在$1-i$内的状态，显然每次转移都是$O(N)$的时间复杂度，总复杂度为$O(N^2)$，状态转移方程如下：
$DP[i] = max(DP[i], DP[j] + 1) | (j < i)$
显然$O(N^2)$的时间复杂度是无法满足 OIer 的，因此我们要进行优化。
----------------------
LIS 的贪心二分优化
优化思路
为什么朴素算法慢呢？因为我们把所有情况枚举了一遍，而最后留下的只有一种。LIS 的朴素算法在那些本不需要枚举的状态上浪费了时间，自然就不行了。
我们知道，LIS 是一个严格单增的数列，那么在两个 LIS 长度相同的情况下，我们希望它能扩展到的长度尽可能长，自然是希望LIS 结尾元素尽可能小。那么思路就有了，我们使用一个数组$G[i]$保存长度为$i$的 LIS 的结尾元素值记录当前最长的 LIS 长度为$tot$，对于每一个$A[i]$，如果$A[i] > G[tot]$，说明当前可以把$A[i]$接到这一条所谓最长的 LIS 后面，则$G[++tot] = A[i]$。
那么我们的问题就是如何维护$G$数组。其实很简单，思路就是我们上面的思路，但是有一个问题，如果$A[i] \leq G[tot]$，应该怎么办呢？
那么根据我们的优化思路，我们要尽可能确保当前$G$数组里面存储的是当前长度为$i$的 LIS 序列的最优解，也就是
结尾元素尽可能小的情况。所以我们要在$G$数组中找到第一个大于$A[i]$的元素$G[j]$，用$A[i]$更新$G[i]$。可是如果单纯遍历，复杂度又双叒叕回到了$O(N^2)$级别，所以……
二分优化
显然，$G$数组是一个单调递增的数组，自然地可以使用二分查找优化时间复杂度。把时间复杂度降到$O(N,log,N)$级别。
代码整合
那么到目前为止，我们亲爱的$DP$数组就寿终正寝了，换成了我们新的$G$数组（
什么NTR剧情）。下面是代码示例，基础 LIS：
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX 100005
#define INF 1e9
using namespace std;
int A[MAX]; //存数字
int G[MAX]; //我们亲爱的G数组
int tot = 1;
int main()
{
int N = 0; //长度
for(int i = 1; i <= N; i++)
{
scanf("%d", &A[i]);
G[i] == INF; //初始化为1e9
}
G[1] = A[1]; //我们开始的起点
for(int i = 2; i <= N; i++)
{
if(A[i] > G[tot]) //只要能插入，就先插入
G[++tot] = A[i]; //初始化最后一个元素值
else
{
int l = 1, r = tot, mid; //新建变量
while (l < r)
{
//基础二分查找
mid = (l + r) >> 1;
if(G[mid] > A[i]) r = mid;
else l = mid + 1;
}
G[l] = min(G[l], A[i]); //赋值，加MIN保险
}
}
printf("%d", tot); //输出答案
return 0;
}
LIS 例题
这里给出一道 LIS 模板题：导弹拦截 LIS 经典。
将拦截的导弹的高度提出来成为原高度序列的一个子序列，根据题意这个子序列中的元素是单调不增的（即后一项总是不大于前一项），我们称为单调不升子序列。本问所求能拦截到的最多的导弹，即求最长的单调不升子序列。（其实只要判断改一下就好啦！）
第一问
没什么好说的，跑一次示例代码完事。
注意这里$G$数组递减！请修改二分查找！
第二问
那么既然是单调不升子序列，我们考虑朴素算法，那么$G$数组就要求存储最大的值，每次执行完一次计算，就把选中的元素移除。重复计算，直到全部移除，记录计算次数，输出为答案。
但是这样显然太笨了！我们要优化优化优化！
我们不妨改变一下$G$数组的含义，用$G[i]$存第$i$个系统当前能够拦截的高度，同时我们把这些系统按从小到大排列——类似于原来的$G$数组。显然每次遍历到导弹$A[i]$时，我们拿最小的$G[i] \geq A[i]$是最优解。然后更新$G[i]$的值，显然更新之后排列还是从小到大，$G$数组仍然是单调递增的，因此不需要重新排序。当然如果没有满足$G[i] \geq A[i]$的情况，就新增一个系统。
只要我们仍然保存时间复杂度在$O(N,log,N)$ 级别，可以通过$10^5$的数据。
代码整合
下面是 AC 代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAX 100005
#define INF 1e9
using namespace std;
int A[MAX]; //存数字
int G[MAX]; //我们亲爱的G数组
int tot = 1;
int main()
{
int N = 0; //长度
while(~scanf("%d",&A[++N])); --N;
G[1] = A[1]; //我们开始的起点
for(int i = 2; i <= N; i++)
{
if(A[i] <= G[tot]) //只要能插入，就先插入
G[++tot] = A[i]; //初始化最后一个元素值
else
{
int l = 1, r = tot, mid;
while (l < r)//获得下标，注意这里G数组递减
{
//基础二分查找
mid = (l + r) >> 1;
if(G[mid] >= A[i]) l = mid + 1;
else r = mid;
}
G[l] = max(G[l], A[i]); //赋值，加MAX保险
}
}
printf("%d\n", tot); //输出答案一
//重置数据
tot = 1;
memset(G, INF, sizeof(G));
G[1] = A[1];
for(int i = 2; i <= N; i++)
{
int l = 1, r = tot, mid;
while (l < r)//获得下标，当然也可能没有
{
//基础二分查找
mid = (l + r) >> 1;
if(G[mid] >= A[i]) r = mid;
else l = mid + 1;
}
if(G[l] >= A[i]) G[l] = A[i]; //如果找得到，赋值
else G[++tot] = A[i]; //如果找不到，初始化一个新的系统
}
printf("%d\n", tot); //输出答案二
return 0;
}
via サン猫の時間漂流
人生海海读后感
音频
https://www.bilibili.com/audio/au4807062/
原文
说实话，我已经忘记了，把“写人生海海读后感”加到 To Do List 上是什么时候了。太久远了，而我到现在才写。在我已忘却的时间里，我其实遇到了一个困难。但具体什么我也记不清，也许是写文章写得多了之后，就愈发怕起来，怕自己新写的达不到之前的高度。真的，如此胆小是很痛苦的。我基本上每一篇文章都先手写再转到电脑上，本身并不做什么修改。可之前的一篇《云端》却被我改得面目全非。我好像在学习麦家，学习他每天只写几百字多删改的习惯。这显然是我不擅长的。我擅长的是笔随心动，是灵机一动的巧思。总是逐字推敲，反而让我逐渐丧失了讲故事的能力，然后只能仰天长啸，哎！是应该改改，是应该“让我这辆破车重新上路”。
我想到之前一次，在开会的时候无所事事，打开本子，想到写什么便写什么，不用思考地洋洋洒洒地写了一面。我现在也学习这样，这种最舒服的状态。我脑中第一个跳出的词是鸡奸犯，然后的话是其他的一些下流的词汇，这真是我印象最深的东西。“人生海海”，这书名，我本以为是什么心灵鸡汤，而我也正是奔着这去的。可等我看到书里的内容，迎面而来的首先是一种“人类无非是喜欢‘屎尿屁’”的真实，然后紧接着是震惊与惊喜。震惊在于书中的内容与麦家本人演讲的风格差别也太大了，至少表面上看来是如此；惊喜在于内容莫名有一种在学校偷看禁书的刺激感。也许是因为我是青春期的孩子，看到一个围绕着那个东西展开的故事，里面还有一些六七十年代的事情，所以会激动吧。有时我觉得，这真是最真实的小说没有了，因为现实生活中怎么可能逃得开那些东西？但其他小说都只字不提，可能是不重要吧。
不重要，说到这个，这么久过去了，我才写这篇读后感，倒是给我起到了一个提炼的作用，或者说，我已经把我记忆中不重要的东西忘得差不多了。里面的故事很有意思，但怎么也没有写在这里的必要，我又不是那些二十分钟带你精读一本的快餐式博主，把佳肴嚼碎了再喂给别人，多少有点恶心。那个名词还在我脑中晃荡，鸡奸犯。说实话，我刚开始并不知道这是什么意思，我知道强奸是强迫别人，那么鸡奸总不能是“鸡哔”别人。书中说，这是再恶劣的词没有了，谁沾上，谁就完蛋了。等我明白了之后，我觉得是极对的。
我现在得改改观点，要我说，这故事就是围绕误会展开的，不管是上校在村里，还是在外面和那个女人的故事。一切的原因，都只是他肚皮底下的一行字，一行在最恶劣的词之外的最恶劣的一行字，也是我最失望的一行字。我如饥似渴地在书中跳跃，同书中村里的人、城里的人一样，无比渴求的想知道，那一行字到底有多么的不堪。等来的不过是，是那个上校在那个日本女人家里留下的印记。我觉得为何不公开呢？既解决了矛盾，又可以平反，也不用再惹出这么多难过的事。好吧，这是上校的伤疤，只有他疯了之后，他才愿意将其见人，并在上面画一棵小树吧。
在这种环境下，写东西真的困难，尤其是写得稍微长了些，总是得分成几天来写。这让我又回到先前的害怕来，害怕我忘记了自己要写什么，应该写什么。不过其实我反而没什么好担心的，毕竟我压根没想过后面应该怎么写，或者说，我压根想不出后面应该写什么。那就从心所欲吧。我说，自然而然的，他会给你一个出口。这好像是我在读《人山海海》时觉得剧情快要下不去了，忽地，它给你一个强烈而又合乎情理的转折，一下子拨云见雾，然后你才能发现其中的矛盾是什么，而他们背后的逻辑却又是同一个。
转折发生得太快了，让这个真实的小说忽然变得荒诞。我全家被村里人唾弃，与爷爷好了一辈子老保长，则一下子翻了面。我晚上不敢再出门，因为随时有可能飞过来一块砖给自己拍死。我被分到最差的客桌，甚至最后不得不背井离乡，逃到西班牙才得以生存。被第三章吓呆了，我，真的，明明是围绕上校展开的故事，这灾祸怎么忽得降临到了“我”头上呢？好心办错事，酒后吐真言，一切都毁在爷爷明白的一辈子里了。
上校的周围就这么一圈人，明白了一世，糊涂了一时，在所有矛盾与纠织不清的因果中了结了一生，当然最后也是自食其果，或是装傻、装疯卖傻，或是用余生去弥补。
现在想来有些惭愧的是，我竟忘了最后照顾上校直至离开的那个人的名字了。也许她是一切的源头，容许我简略讲讲内容：大抵是上校在抗美援朝战争中，好像，她他发生了关系。之后她屡次求爱无果，一气之下将其告上了法庭，要还她清白。她做出了她一生中最糟糕的一次决定，不仅把上校打回了村里，还毁了她自己的名声，从此到哪儿都不受待见，孤苦一人；而我也在这文中写下了最糟糕的一段，擅自概括内容，把作者用了极大笔墨捯饬的前因后果删改得不成样子。甚至其实后文还有暗示，与她发生关系的压根不是上校，纯是因为黑灯瞎火看不清人，自此误解。她不知道上校拒绝她根本不是因为……只是因为他本人小腹的那一行字，他怕他让她蒙羞，怕他对不起她。
上校疯了，彻底疯了。为什么疯了，我不记得了，大抵是发烧给脑子烧糊了吧。反正不重要，重要的是突然出现了一个女人，一个外乡人，找到村里来，日夜照顾上校，好似一生只为他一人。村里人都说，这是天上的仙女下了凡，是上校救人修来的福分。一切只有她自己明白，这恰恰是她酿成的苦果，现在她要在人们欢送的掌声中，用余生去弥补。
但这时，“我”是不知道的，在西班牙，“我”连怎么活下去都是个难题，哪还了解这些。寄回家的书信，也少有回信，不管仍是写，谁想全到了她的手里。“我”，上校的最好的朋友的儿子，没想到与她建立了这样的单方面的联系。在西班牙，发生的种种也很重要，只可惜不是主线。写到这一步，我得停停，去写点真正的，“读后感的”文字。别再讲故事，别再叙旧情。
可是，没了故事，情感便无处可移。我呆坐了十分钟，一个字也写不下来。既如此，只好寻出路，不单单是书籍本身。我想到了，想到了麦家的演讲，就是那个我说过风格差别很大的，我也曾写过的演讲。一部破车，重新上路？什么是破车，怎样，算是上路呢？在这部小说中，我好像有了一点头绪……麦家，作家，谁不是一辆曾经翻倒在路边的破车？只是有的自重太大，倒下就再起不能（爷爷）；有的惊慌失措，又因为还有更重要的人，只能停留，或做坚守（父亲）；其他的，则是丢掉了之前的往往，重拾希望，重新上路。“我”是如此，她也是如此，上校更是如此。我从不觉得上校真的疯了，他疯，只是他修补自己的手段吧。是受困于人的倔强的解决方案，只有这样，他才可以坦然面对自己的伤疤……如此，故事也该结束了。
写到现在，我已经痛苦得很，写不太下去了。即使我用想写什么就写什么的想法来宽慰自己，也难有太大的作用。可能是写得太多又少，马上结束盘算着文章发布后的事，人心又静不下来。我觉得写这一篇是提炼不出我要表达什么的，不论怎样都好似是对原文的冒犯。在这思潮枯竭的最后，我终于又想到了一个场景。
那是小瞎子，一个造谣者，苦苦将爷爷逼死。他瘫坐在地上，那时“我”正好从西班牙回来，某种意义上也是功成名就。“我”在上俯视他，他在下仰视“我”，同时乞求着几文钱。“谢谢你，大人不计小人过。”他用脚在泥地里抠出几个字来，因为他的舌头早就被割掉。虽然当他风生水起之后，又成为了之前那个令人生厌的刺头，但“我”还是给了他钱，甚至包了他在小店的费用，村里人都很不可思议，作为读者的我也一样。如果是我，我定然不会可怜他，我想，哎，也许不落井下石，就是“我”这部破车上路的诀窍吧，什么时候我不会再因此感到诧异，大抵什么时候，我才可以把这本书看明白吧。
via サン猫の時間漂流
音频
https://www.bilibili.com/audio/au4807062/
原文
说实话，我已经忘记了，把“写人生海海读后感”加到 To Do List 上是什么时候了。太久远了，而我到现在才写。在我已忘却的时间里，我其实遇到了一个困难。但具体什么我也记不清，也许是写文章写得多了之后，就愈发怕起来，怕自己新写的达不到之前的高度。真的，如此胆小是很痛苦的。我基本上每一篇文章都先手写再转到电脑上，本身并不做什么修改。可之前的一篇《云端》却被我改得面目全非。我好像在学习麦家，学习他每天只写几百字多删改的习惯。这显然是我不擅长的。我擅长的是笔随心动，是灵机一动的巧思。总是逐字推敲，反而让我逐渐丧失了讲故事的能力，然后只能仰天长啸，哎！是应该改改，是应该“让我这辆破车重新上路”。
我想到之前一次，在开会的时候无所事事，打开本子，想到写什么便写什么，不用思考地洋洋洒洒地写了一面。我现在也学习这样，这种最舒服的状态。我脑中第一个跳出的词是鸡奸犯，然后的话是其他的一些下流的词汇，这真是我印象最深的东西。“人生海海”，这书名，我本以为是什么心灵鸡汤，而我也正是奔着这去的。可等我看到书里的内容，迎面而来的首先是一种“人类无非是喜欢‘屎尿屁’”的真实，然后紧接着是震惊与惊喜。震惊在于书中的内容与麦家本人演讲的风格差别也太大了，至少表面上看来是如此；惊喜在于内容莫名有一种在学校偷看禁书的刺激感。也许是因为我是青春期的孩子，看到一个围绕着那个东西展开的故事，里面还有一些六七十年代的事情，所以会激动吧。有时我觉得，这真是最真实的小说没有了，因为现实生活中怎么可能逃得开那些东西？但其他小说都只字不提，可能是不重要吧。
不重要，说到这个，这么久过去了，我才写这篇读后感，倒是给我起到了一个提炼的作用，或者说，我已经把我记忆中不重要的东西忘得差不多了。里面的故事很有意思，但怎么也没有写在这里的必要，我又不是那些二十分钟带你精读一本的快餐式博主，把佳肴嚼碎了再喂给别人，多少有点恶心。那个名词还在我脑中晃荡，鸡奸犯。说实话，我刚开始并不知道这是什么意思，我知道强奸是强迫别人，那么鸡奸总不能是“鸡哔”别人。书中说，这是再恶劣的词没有了，谁沾上，谁就完蛋了。等我明白了之后，我觉得是极对的。
我现在得改改观点，要我说，这故事就是围绕误会展开的，不管是上校在村里，还是在外面和那个女人的故事。一切的原因，都只是他肚皮底下的一行字，一行在最恶劣的词之外的最恶劣的一行字，也是我最失望的一行字。我如饥似渴地在书中跳跃，同书中村里的人、城里的人一样，无比渴求的想知道，那一行字到底有多么的不堪。等来的不过是，是那个上校在那个日本女人家里留下的印记。我觉得为何不公开呢？既解决了矛盾，又可以平反，也不用再惹出这么多难过的事。好吧，这是上校的伤疤，只有他疯了之后，他才愿意将其见人，并在上面画一棵小树吧。
在这种环境下，写东西真的困难，尤其是写得稍微长了些，总是得分成几天来写。这让我又回到先前的害怕来，害怕我忘记了自己要写什么，应该写什么。不过其实我反而没什么好担心的，毕竟我压根没想过后面应该怎么写，或者说，我压根想不出后面应该写什么。那就从心所欲吧。我说，自然而然的，他会给你一个出口。这好像是我在读《人山海海》时觉得剧情快要下不去了，忽地，它给你一个强烈而又合乎情理的转折，一下子拨云见雾，然后你才能发现其中的矛盾是什么，而他们背后的逻辑却又是同一个。
转折发生得太快了，让这个真实的小说忽然变得荒诞。我全家被村里人唾弃，与爷爷好了一辈子老保长，则一下子翻了面。我晚上不敢再出门，因为随时有可能飞过来一块砖给自己拍死。我被分到最差的客桌，甚至最后不得不背井离乡，逃到西班牙才得以生存。被第三章吓呆了，我，真的，明明是围绕上校展开的故事，这灾祸怎么忽得降临到了“我”头上呢？好心办错事，酒后吐真言，一切都毁在爷爷明白的一辈子里了。
上校的周围就这么一圈人，明白了一世，糊涂了一时，在所有矛盾与纠织不清的因果中了结了一生，当然最后也是自食其果，或是装傻、装疯卖傻，或是用余生去弥补。
现在想来有些惭愧的是，我竟忘了最后照顾上校直至离开的那个人的名字了。也许她是一切的源头，容许我简略讲讲内容：大抵是上校在抗美援朝战争中，好像，她他发生了关系。之后她屡次求爱无果，一气之下将其告上了法庭，要还她清白。她做出了她一生中最糟糕的一次决定，不仅把上校打回了村里，还毁了她自己的名声，从此到哪儿都不受待见，孤苦一人；而我也在这文中写下了最糟糕的一段，擅自概括内容，把作者用了极大笔墨捯饬的前因后果删改得不成样子。甚至其实后文还有暗示，与她发生关系的压根不是上校，纯是因为黑灯瞎火看不清人，自此误解。她不知道上校拒绝她根本不是因为……只是因为他本人小腹的那一行字，他怕他让她蒙羞，怕他对不起她。
上校疯了，彻底疯了。为什么疯了，我不记得了，大抵是发烧给脑子烧糊了吧。反正不重要，重要的是突然出现了一个女人，一个外乡人，找到村里来，日夜照顾上校，好似一生只为他一人。村里人都说，这是天上的仙女下了凡，是上校救人修来的福分。一切只有她自己明白，这恰恰是她酿成的苦果，现在她要在人们欢送的掌声中，用余生去弥补。
但这时，“我”是不知道的，在西班牙，“我”连怎么活下去都是个难题，哪还了解这些。寄回家的书信，也少有回信，不管仍是写，谁想全到了她的手里。“我”，上校的最好的朋友的儿子，没想到与她建立了这样的单方面的联系。在西班牙，发生的种种也很重要，只可惜不是主线。写到这一步，我得停停，去写点真正的，“读后感的”文字。别再讲故事，别再叙旧情。
可是，没了故事，情感便无处可移。我呆坐了十分钟，一个字也写不下来。既如此，只好寻出路，不单单是书籍本身。我想到了，想到了麦家的演讲，就是那个我说过风格差别很大的，我也曾写过的演讲。一部破车，重新上路？什么是破车，怎样，算是上路呢？在这部小说中，我好像有了一点头绪……麦家，作家，谁不是一辆曾经翻倒在路边的破车？只是有的自重太大，倒下就再起不能（爷爷）；有的惊慌失措，又因为还有更重要的人，只能停留，或做坚守（父亲）；其他的，则是丢掉了之前的往往，重拾希望，重新上路。“我”是如此，她也是如此，上校更是如此。我从不觉得上校真的疯了，他疯，只是他修补自己的手段吧。是受困于人的倔强的解决方案，只有这样，他才可以坦然面对自己的伤疤……如此，故事也该结束了。
写到现在，我已经痛苦得很，写不太下去了。即使我用想写什么就写什么的想法来宽慰自己，也难有太大的作用。可能是写得太多又少，马上结束盘算着文章发布后的事，人心又静不下来。我觉得写这一篇是提炼不出我要表达什么的，不论怎样都好似是对原文的冒犯。在这思潮枯竭的最后，我终于又想到了一个场景。
那是小瞎子，一个造谣者，苦苦将爷爷逼死。他瘫坐在地上，那时“我”正好从西班牙回来，某种意义上也是功成名就。“我”在上俯视他，他在下仰视“我”，同时乞求着几文钱。“谢谢你，大人不计小人过。”他用脚在泥地里抠出几个字来，因为他的舌头早就被割掉。虽然当他风生水起之后，又成为了之前那个令人生厌的刺头，但“我”还是给了他钱，甚至包了他在小店的费用，村里人都很不可思议，作为读者的我也一样。如果是我，我定然不会可怜他，我想，哎，也许不落井下石，就是“我”这部破车上路的诀窍吧，什么时候我不会再因此感到诧异，大抵什么时候，我才可以把这本书看明白吧。
via サン猫の時間漂流
Q 胜记略
Introduction
本文基本上保持原稿，仅有极个别错字删改。
Original Text
初看觉得懂了，再看又不懂了。忽得捏不准记叙的是喜还是悲，表达的是褒还是贬。总觉得在那个世间，有点“得胜”的本领是有必要的，但又觉得在批判，所以我自己并不知写什么才好。
文中说阿Q没什么“行状”，既如此，那我便给他捏个形状：阿Q是有自尊心的，也并不是一无是处。做工做得来，赌博也是可以的。只可怜于自身没有什么硬实力，脊梁又太软，被打几下，就连自己是虫豸也说得来的。不论什么方法，阿Q得胜的方式很简单，就是“合理化”。只要把自己看得足够弱，或把对面看得足够轻，那一切都是合理的。既然是合理的，那就怪不到自己身上，顶多是怪世道沧桑罢了。你说这有道理么？我觉得是有道理的。因为世界本身太不合理了：别人不喜欢的事物非要提; 一言不慎就动手开打。就连赌赢了也不遵守规矩，自导自演地抢走了……世界不合理，可人又是要合理性的，所以只得在不合理的世界中编造合理的理由，才能正常地生活下去。不然正像文中所说，阿Q早就遭了瘟，哪儿还有后来呢？
不止是阿Q，在这个世界中，人人都有自己的得胜技巧。先前的庄家————说过了，你赢钱没事，我再抢回来就行；又癞又胡的王癞胡，平日里肯定也是被大家笑话的角色，你看他不还是找准机会暴揍了阿Q一顿么；处处受人嫌的小尼姑，若是没有排解的法子，早就被淹死在乡里乡亲的唾沫中与笑声中了。我半睡不醒地写了两大页，现在才终于找到些许明白：阿Q之类，无非是一个小的缩影罢了。谁是阿Q与行状，又不重要。但一群人的行为不是孤立没有原因的，反映的最后，就是这个吃人的社会。
你觉得阿Q可怜，那其实大家也都很可怜；你觉得阿Q可恨，那其实大家也都挺可恨。一群人病了，病因便不在人。我写到最后终于明白了鲁迅先生所写的，感叹先生文章之传神，同时也感叹我总算没有浪费时光。
Postscript
其实这篇是上周的一次语文作业。说来惭愧，我长这么大没有完整地看过《阿Q正传》，所以在写之前也只不过是看了语文书里面的一点点内容而已。那天撰写此篇时，因为脑袋空空，犯困得紧。还好最后总算是憋出一些东西，所以也还算是满意交差。
只是后面语文老师给我们看了《阿Q正传》的电影，越看越觉得我之前写得胡乱。总觉得不是这样，但是还是说不清。更令人惊奇的是，本以为就这样了，老师还把这篇当作好文展了出来——有了这层认同，我想这篇总还是有点内容。但到最后还是理不清，仅作抛砖引玉之计，希望读者可以有自己的看法。
via サン猫の時間漂流
Introduction
本文基本上保持原稿，仅有极个别错字删改。
Original Text
初看觉得懂了，再看又不懂了。忽得捏不准记叙的是喜还是悲，表达的是褒还是贬。总觉得在那个世间，有点“得胜”的本领是有必要的，但又觉得在批判，所以我自己并不知写什么才好。
文中说阿Q没什么“行状”，既如此，那我便给他捏个形状：阿Q是有自尊心的，也并不是一无是处。做工做得来，赌博也是可以的。只可怜于自身没有什么硬实力，脊梁又太软，被打几下，就连自己是虫豸也说得来的。不论什么方法，阿Q得胜的方式很简单，就是“合理化”。只要把自己看得足够弱，或把对面看得足够轻，那一切都是合理的。既然是合理的，那就怪不到自己身上，顶多是怪世道沧桑罢了。你说这有道理么？我觉得是有道理的。因为世界本身太不合理了：别人不喜欢的事物非要提; 一言不慎就动手开打。就连赌赢了也不遵守规矩，自导自演地抢走了……世界不合理，可人又是要合理性的，所以只得在不合理的世界中编造合理的理由，才能正常地生活下去。不然正像文中所说，阿Q早就遭了瘟，哪儿还有后来呢？
不止是阿Q，在这个世界中，人人都有自己的得胜技巧。先前的庄家————说过了，你赢钱没事，我再抢回来就行；又癞又胡的王癞胡，平日里肯定也是被大家笑话的角色，你看他不还是找准机会暴揍了阿Q一顿么；处处受人嫌的小尼姑，若是没有排解的法子，早就被淹死在乡里乡亲的唾沫中与笑声中了。我半睡不醒地写了两大页，现在才终于找到些许明白：阿Q之类，无非是一个小的缩影罢了。谁是阿Q与行状，又不重要。但一群人的行为不是孤立没有原因的，反映的最后，就是这个吃人的社会。
你觉得阿Q可怜，那其实大家也都很可怜；你觉得阿Q可恨，那其实大家也都挺可恨。一群人病了，病因便不在人。我写到最后终于明白了鲁迅先生所写的，感叹先生文章之传神，同时也感叹我总算没有浪费时光。
Postscript
其实这篇是上周的一次语文作业。说来惭愧，我长这么大没有完整地看过《阿Q正传》，所以在写之前也只不过是看了语文书里面的一点点内容而已。那天撰写此篇时，因为脑袋空空，犯困得紧。还好最后总算是憋出一些东西，所以也还算是满意交差。
只是后面语文老师给我们看了《阿Q正传》的电影，越看越觉得我之前写得胡乱。总觉得不是这样，但是还是说不清。更令人惊奇的是，本以为就这样了，老师还把这篇当作好文展了出来——有了这层认同，我想这篇总还是有点内容。但到最后还是理不清，仅作抛砖引玉之计，希望读者可以有自己的看法。
via サン猫の時間漂流
云端
Para 1
正月初六，我犯了一个原则性问题，把我的生活抛给了一个不可名状的未知数中。虽然它使我的生命分崩离析的概率小到比周围空气爆炸的概率还荒谬，但正像从0到1的“突破”，有这种概率的出现已使我惶惶不可终日了。直到现在，那个未知数还不能被确定……在这每天的思想斗争中，我突然再一次地觉得我的生命，与我所珍视的一切是那么脆弱。我所努力拥有或幸运遇到的一切，都有可能因为我的一个错误而全部爆掉。那可怕的玩意压着我的头，让我跪在地上承认我的错误我的罪，让我不得不珍惜这不确定的每一天。
类似可能随地断线的事情我经过很多次，但哪一次都没有像这一次一样漫长且煎熬。那一回吧，和父亲去爬一座山，山的路径是石头砌好的，是和尚化缘修来的。对于那时的我，无非只相当于爬爬楼梯，哪儿是真去爬山呢？我自然的而然地走在队伍的最前面，把父亲甩在后头。也就是那之后，父亲逢人就说：这小家伙体力好得很，是领头羊呢——每次他这般胡诹的时候，我老早在上边催促了。
又是很自然的，到了山顶。这山不是一座三角锥，而仿佛是从平地上突兀升起的一整块，四周都是悬崖峭壁。站在边上，就有一种不自觉想下跳的趋势。没有了往上的石阶，我说，原路回去吧。父亲却瞄见了前方的道路，怂恿我从那里下山去。显然，那不是属于景区的一条路。与所有景区横竖交叉出来的小路一样，它没有石砌的台阶，有的是黄黄的、被踩实了的土地与四周的杂草。多好的探险呐，父亲推着我。我只知父命不可违，也就去了。
自然的，先前领队的我成了探路的先锋，像只真正的领头羊在石矶间跳跃。这确实是一条下山的路，但也只是向下，全然不知通往何方。土地是实的没错，可上面还有一层沙，踩上去，也就是沙沙、沙沙——沙沙地滑落下去。踩在石头上尚且还好，可一切都太突然了，我右脚一迈，就踩到了一层沙上。又是斜坡，待我意识到时，我的右腿已经被拖拽着走了，幸好人小，两脚大开步时还可以勉强站住。可这样两手挥舞的样子，怎么停得下来？前方是一块突出的巨石和绿葱葱的远景，左边有一棵孤零零的树。大脑还没有思考，整个人就趴在了那小树上。幸好就几秒钟，速度还不快。我死命拽着树不撒手，人望前的石头一探，才发现什么都没了——远景遥不可及，低头便是绝壁。
但当时的我没什么感觉，肾上腺素还没反应过来，就又回到了正确道路上。要说有点变化的，可能就只是多了一些尘土，手没放开过树木而已。父亲趁这功夫终于赶了上来，看见我抓着树干，笑嘻嘻的说我怎么被这难住了。盯着他轻松的样子，我一时竟忘了告诉他我差点就掉下去了、就再也见不到了。想着，为什么爸爸完全不怕会滑倒呢？看了看一旁的小树，我觉得它可撑不住。
到了山下的一户村子里，已是离开景区很远了。山凹凹里没再多岔路，只得沿出村的马路走着。说是马路，其实和下山路差不太多。人已经乏了，但想到之前的事，再走走吧，脚踏实地的感觉真好。
Para 2
也就是那个暑假，我的一位同学离开了。我想她总是没抓住什么东西，不然也不至于呜呜淹死在江水中了。但是我不知道她到底应该抓住些什么，我只知道那天她是一个人从同学家走回来的，走到两村街的小桥上，兀得没了身影。是失足了？还是情愿放弃一切的纵身一跃？我也不知道。我只知道他的父母在她定位信号消失的地方打捞了四天三夜，最后才捞上来一具浮肿的尸体。家委会在班级群里收集善款，有同学质疑：为什么不是他的父母来收？越说越难听……作为班长的我因为管理不当被老师训了一顿。除了少了一个在操场边上独自坐着、若有所思的同学之外，这可能是对我唯二的影响。
死人，总是会有的，但我不想讲死。小时候想不通，现在觉得乏味了。那后来倒在我班级面前的、倒在血泊中的尸体，即使在当天被吓得不轻，没几天也就忘却了。就连寝室里回去要登记，我也觉得是很正常的事。前几年不登记人员的散漫态度，在我眼里才是不正常的存在。
Para 3
小时候，不知道水循环，老师就把水比作一个个水宝宝：它们从大海上出发，攒着一股劲儿，乌泱泱的爬到空中，循着气流飘到了中国大地上空。它们有的钻进干涸的土地里，哺育出美丽的花朵；有的扑进长江母亲的怀抱，成了一朵奔涌的浪花；还有的则化作雪花，落在皑皑的喜马拉雅之巅——或化甘泉、或成冰原，等待人们的发现。我傻傻的望着，望着在水壶里没有半点声响的一块水。我想，这些水宝宝见到我之前，经历了什么呢？如果有一部纪录片可以记录水的一生，那该有有多酷啊！那时候很喜欢看纪录片，我想人们既然可以拍出诸如《动物世界》、《地球脉动》等片子，那么拍一个水宝宝的纪录片，想来也不过分。
可是除了一身顽皮的小孩子以外，谁还会去关注它们呢。况且拍摄难度太大，用动画模拟一下已经是大发慈悲了。只是这样它们就并不是真的存在我水杯里的一滴水，所以我的愿望，很快就从务实的纪录片，转成可以回溯事物经历的超能力了。
Para 4
清明，又爬山。“清明时节雨纷纷"不是假的。雨水把地面浇得湿漉漉的，这次我没再跑在前头，等着父亲慢吞吞的上来，然后抓着他的手说：“你带着我走吧，我怕滑。”父亲还是和之前一样，稳稳当当的，一步一个泥泞。每一顿，都好像把脚扎根在了土地里。
Para 5
我住在一座小城里，很宁静的小城，和书本上说的一模一样。
我很享受这里，觉得外面的人很疯狂，理解不来，但又笃信那是潮流。在宁静的小城里呆着，时常觉得很孤僻。我跳到云上，但还是向往宁静，还是住在小城里。
有人对我说：“我要去地狱里燃烧了。”我是看不得有人去死的，因为看得太多了，那些东西也到底挥之不去……想着祂总得抓住点什么，可我毕竟在云上，即使跳出城外，也找不到方向去寻那一双手。幸好云上大家都是善良的吧，我的身影早已被乌泱泱的队伍盖得没了影。想跟上，却发现是原地转圈，最后也没有人找到祂。直到第二天传来一句：“没事儿了，昨天药效太猛没跳下去，昏了。”
疯狂的人还活在世上，并且活得并不像他们所说的一样——到众叛亲离的地步。毕竟我到现在还没有受到过这种乌泱泱的待遇。
可小城里的人，却真的是越来越少了。没能跟上队伍的我，最终还是要降落的。没地方去，只得落到原本的小城里——和书本上说的，大相径庭。
Para 6
上学了。回家的路上，我低着头说了一堆。我说我以后不能再这么暴躁了，我要改。父亲笑嘻嘻的说：“你暴躁吗？我没感觉到啊。”唉唉，我老是不耐烦的样子，你忘了吗？我说，我现在十分珍惜每一天，因为也许何时就不说再见的结束了，能活到现在也是一个奇迹——他好像在专心开车，所以没有搭理我。
你不觉得我说这些很奇怪吗？我没忍住，问了一句。“不奇怪啊，这说明你不再是象牙塔里的孩子，不再只是听从老师的教诲、一板一眼的考虑书本上的问题。你会思考人、会思考社会，说明你变得成熟了，这很正常。”
via サン猫の時間漂流
Para 1
正月初六，我犯了一个原则性问题，把我的生活抛给了一个不可名状的未知数中。虽然它使我的生命分崩离析的概率小到比周围空气爆炸的概率还荒谬，但正像从0到1的“突破”，有这种概率的出现已使我惶惶不可终日了。直到现在，那个未知数还不能被确定……在这每天的思想斗争中，我突然再一次地觉得我的生命，与我所珍视的一切是那么脆弱。我所努力拥有或幸运遇到的一切，都有可能因为我的一个错误而全部爆掉。那可怕的玩意压着我的头，让我跪在地上承认我的错误我的罪，让我不得不珍惜这不确定的每一天。
类似可能随地断线的事情我经过很多次，但哪一次都没有像这一次一样漫长且煎熬。那一回吧，和父亲去爬一座山，山的路径是石头砌好的，是和尚化缘修来的。对于那时的我，无非只相当于爬爬楼梯，哪儿是真去爬山呢？我自然的而然地走在队伍的最前面，把父亲甩在后头。也就是那之后，父亲逢人就说：这小家伙体力好得很，是领头羊呢——每次他这般胡诹的时候，我老早在上边催促了。
又是很自然的，到了山顶。这山不是一座三角锥，而仿佛是从平地上突兀升起的一整块，四周都是悬崖峭壁。站在边上，就有一种不自觉想下跳的趋势。没有了往上的石阶，我说，原路回去吧。父亲却瞄见了前方的道路，怂恿我从那里下山去。显然，那不是属于景区的一条路。与所有景区横竖交叉出来的小路一样，它没有石砌的台阶，有的是黄黄的、被踩实了的土地与四周的杂草。多好的探险呐，父亲推着我。我只知父命不可违，也就去了。
自然的，先前领队的我成了探路的先锋，像只真正的领头羊在石矶间跳跃。这确实是一条下山的路，但也只是向下，全然不知通往何方。土地是实的没错，可上面还有一层沙，踩上去，也就是沙沙、沙沙——沙沙地滑落下去。踩在石头上尚且还好，可一切都太突然了，我右脚一迈，就踩到了一层沙上。又是斜坡，待我意识到时，我的右腿已经被拖拽着走了，幸好人小，两脚大开步时还可以勉强站住。可这样两手挥舞的样子，怎么停得下来？前方是一块突出的巨石和绿葱葱的远景，左边有一棵孤零零的树。大脑还没有思考，整个人就趴在了那小树上。幸好就几秒钟，速度还不快。我死命拽着树不撒手，人望前的石头一探，才发现什么都没了——远景遥不可及，低头便是绝壁。
但当时的我没什么感觉，肾上腺素还没反应过来，就又回到了正确道路上。要说有点变化的，可能就只是多了一些尘土，手没放开过树木而已。父亲趁这功夫终于赶了上来，看见我抓着树干，笑嘻嘻的说我怎么被这难住了。盯着他轻松的样子，我一时竟忘了告诉他我差点就掉下去了、就再也见不到了。想着，为什么爸爸完全不怕会滑倒呢？看了看一旁的小树，我觉得它可撑不住。
到了山下的一户村子里，已是离开景区很远了。山凹凹里没再多岔路，只得沿出村的马路走着。说是马路，其实和下山路差不太多。人已经乏了，但想到之前的事，再走走吧，脚踏实地的感觉真好。
Para 2
也就是那个暑假，我的一位同学离开了。我想她总是没抓住什么东西，不然也不至于呜呜淹死在江水中了。但是我不知道她到底应该抓住些什么，我只知道那天她是一个人从同学家走回来的，走到两村街的小桥上，兀得没了身影。是失足了？还是情愿放弃一切的纵身一跃？我也不知道。我只知道他的父母在她定位信号消失的地方打捞了四天三夜，最后才捞上来一具浮肿的尸体。家委会在班级群里收集善款，有同学质疑：为什么不是他的父母来收？越说越难听……作为班长的我因为管理不当被老师训了一顿。除了少了一个在操场边上独自坐着、若有所思的同学之外，这可能是对我唯二的影响。
死人，总是会有的，但我不想讲死。小时候想不通，现在觉得乏味了。那后来倒在我班级面前的、倒在血泊中的尸体，即使在当天被吓得不轻，没几天也就忘却了。就连寝室里回去要登记，我也觉得是很正常的事。前几年不登记人员的散漫态度，在我眼里才是不正常的存在。
Para 3
小时候，不知道水循环，老师就把水比作一个个水宝宝：它们从大海上出发，攒着一股劲儿，乌泱泱的爬到空中，循着气流飘到了中国大地上空。它们有的钻进干涸的土地里，哺育出美丽的花朵；有的扑进长江母亲的怀抱，成了一朵奔涌的浪花；还有的则化作雪花，落在皑皑的喜马拉雅之巅——或化甘泉、或成冰原，等待人们的发现。我傻傻的望着，望着在水壶里没有半点声响的一块水。我想，这些水宝宝见到我之前，经历了什么呢？如果有一部纪录片可以记录水的一生，那该有有多酷啊！那时候很喜欢看纪录片，我想人们既然可以拍出诸如《动物世界》、《地球脉动》等片子，那么拍一个水宝宝的纪录片，想来也不过分。
可是除了一身顽皮的小孩子以外，谁还会去关注它们呢。况且拍摄难度太大，用动画模拟一下已经是大发慈悲了。只是这样它们就并不是真的存在我水杯里的一滴水，所以我的愿望，很快就从务实的纪录片，转成可以回溯事物经历的超能力了。
Para 4
清明，又爬山。“清明时节雨纷纷"不是假的。雨水把地面浇得湿漉漉的，这次我没再跑在前头，等着父亲慢吞吞的上来，然后抓着他的手说：“你带着我走吧，我怕滑。”父亲还是和之前一样，稳稳当当的，一步一个泥泞。每一顿，都好像把脚扎根在了土地里。
Para 5
我住在一座小城里，很宁静的小城，和书本上说的一模一样。
我很享受这里，觉得外面的人很疯狂，理解不来，但又笃信那是潮流。在宁静的小城里呆着，时常觉得很孤僻。我跳到云上，但还是向往宁静，还是住在小城里。
有人对我说：“我要去地狱里燃烧了。”我是看不得有人去死的，因为看得太多了，那些东西也到底挥之不去……想着祂总得抓住点什么，可我毕竟在云上，即使跳出城外，也找不到方向去寻那一双手。幸好云上大家都是善良的吧，我的身影早已被乌泱泱的队伍盖得没了影。想跟上，却发现是原地转圈，最后也没有人找到祂。直到第二天传来一句：“没事儿了，昨天药效太猛没跳下去，昏了。”
疯狂的人还活在世上，并且活得并不像他们所说的一样——到众叛亲离的地步。毕竟我到现在还没有受到过这种乌泱泱的待遇。
可小城里的人，却真的是越来越少了。没能跟上队伍的我，最终还是要降落的。没地方去，只得落到原本的小城里——和书本上说的，大相径庭。
Para 6
上学了。回家的路上，我低着头说了一堆。我说我以后不能再这么暴躁了，我要改。父亲笑嘻嘻的说：“你暴躁吗？我没感觉到啊。”唉唉，我老是不耐烦的样子，你忘了吗？我说，我现在十分珍惜每一天，因为也许何时就不说再见的结束了，能活到现在也是一个奇迹——他好像在专心开车，所以没有搭理我。
你不觉得我说这些很奇怪吗？我没忍住，问了一句。“不奇怪啊，这说明你不再是象牙塔里的孩子，不再只是听从老师的教诲、一板一眼的考虑书本上的问题。你会思考人、会思考社会，说明你变得成熟了，这很正常。”
via サン猫の時間漂流
