【数论】初等数论与线性代数综合（整合中）
前言
此篇为导航，由几篇子博客构成。
导航
via サン猫の時間漂流
前言
此篇为导航，由几篇子博客构成。
导航
● 关于数学符号：队列中
● 高斯消元入门：队列中
● 矩阵乘法入门：【线性代数】矩阵乘法与线性 DP 优化 | SaroProck
● 生成函数入门：【线性代数】生成函数在非常系数与非齐次的线性递推关系的应用(编辑中) | SaroProck
via サン猫の時間漂流
【数论】费马小定理
前言
费马小定理（Fermat's Little Theorem）是数论中的一个重要定理，它与素数和模运算相关。定理的表述如下：
对于任意素数 $p$，如果 $a$ 是一个整数，且 $a$ 不是 $p$ 的倍数，则有 $a^{p-1} ≡ 1 (\mod p)$。
应用
模逆元计算
在模运算中，给定两个整数 $a$ 和 $p$，我们想要找到整数 $b$，使得 $(a \times b) \mod p = 1$。这里 $a$ 和 $p$ 必须互质，即它们没有共同的因子。费马小定理提供了一种计算模逆元的方法：
根据费马小定理，如果 $a$ 和 $p$ 互质（$a$ 不是 $p$ 的倍数），则有 $a^{p-1} ≡ 1 (\mod p)$。将等式两边同时乘以 $a^{-1}$（a 的模 p 逆元），得到 $a^{-1} ≡ a^{p-2} (\mod p)$。这意味着 $a^{p-2}$ 就是 $a$ 在模 $p$ 下的逆元。
所以，如果要计算 $a$ 在模 $p$ 下的逆元，只需计算 $a^{p-2} \mod p$，即可得到 $b$，使得 $(a \times b) \mod p = 1$。
via サン猫の時間漂流
前言
费马小定理（Fermat's Little Theorem）是数论中的一个重要定理，它与素数和模运算相关。定理的表述如下：
对于任意素数 $p$，如果 $a$ 是一个整数，且 $a$ 不是 $p$ 的倍数，则有 $a^{p-1} ≡ 1 (\mod p)$。
应用
模逆元计算
在模运算中，给定两个整数 $a$ 和 $p$，我们想要找到整数 $b$，使得 $(a \times b) \mod p = 1$。这里 $a$ 和 $p$ 必须互质，即它们没有共同的因子。费马小定理提供了一种计算模逆元的方法：
根据费马小定理，如果 $a$ 和 $p$ 互质（$a$ 不是 $p$ 的倍数），则有 $a^{p-1} ≡ 1 (\mod p)$。将等式两边同时乘以 $a^{-1}$（a 的模 p 逆元），得到 $a^{-1} ≡ a^{p-2} (\mod p)$。这意味着 $a^{p-2}$ 就是 $a$ 在模 $p$ 下的逆元。
所以，如果要计算 $a$ 在模 $p$ 下的逆元，只需计算 $a^{p-2} \mod p$，即可得到 $b$，使得 $(a \times b) \mod p = 1$。
via サン猫の時間漂流
【博弈论】博弈论与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 サン猫の時間漂流
