CodeForces-1017G

简单转化之后用树剖维护最大后缀和即可，2 操作需要把多余的值减掉。

CodeForces-1017H

对于每个 $k$ 都跑一遍莫队，时间复杂度是 $O(n\sqrt q\sqrt m)$ 的（$m$ 是 $k$ 的种类数），记得每次跑都要重新算块长。

CodeForces-1152F1

考虑从小到大插入数，发现能 $v$ 加入的位置只有开头和 $v-m\sim m$ 之后，状压即可。

CodeForces-1152F2

在 F1 的基础上用矩阵快速幂优化即可。

题目描述

• 在一个 $1$ 行 $n$ 列的棋盘上，有 $m$ 个棋子，第 $i$ 个棋子在从左往右第 $pos_i$ 列，颜色是 $col_i$。
• 现在 Alice 和 Bob 要轮流操作，操作如下：
  • 选中一个棋子以及它到右边下一个同色棋子（若不存在则到底）之间的所有棋子（包含左边不包含右边）。
  • 全部向前移动同一个距离，移动之后要保证棋子没有重叠并且棋子之间相对位置不变。
• Alice 先手，谁不能动谁就输了。

解题思路

先考虑只有一种棋子，那么每次就只移动一枚棋子。
那么我们把棋子之间的空位看成石子，那么题目就可以转化为：

• 有 $k$ 堆石子，Alice 和 Bob 轮流操作，每次可以选定一堆不是最右边的石子，取出若干石子，移动到右边相邻的堆里。
• Alice 先手，谁不能动谁就输了。

那么这就是阶梯 NIM 的模板题了，可以参考 P3480 [POI2009]KAM-Pebbles。
这里来粗略的讲一下阶梯 NIM 的做法。
为了方便起见，我们把顺序换一下，改成从第 $i$ 堆移动到第 $i-1$ 堆，移到第一堆结束。
正常的 NIM 是直接把石子扔掉，然而在阶梯 NIM 中，我们可以把奇数堆看成垃圾桶。

• 如果有人把偶数堆放到奇数堆，那么就相当于把石子扔掉了。
• 如果有人把奇数堆放到偶数堆，必胜者为了保持自己的必胜状态，一定可以把这些石子重新移到奇数堆里（第一堆是奇数堆）。

所以阶梯 NIM 就相当于只有偶数堆的普通 NIM，那么他的 SG 值就是偶数堆个数异或起来。

Lucas 定理

形式： 对于质数 $p$，和非负整数 $n$，$m$，有：

令：$n=(\overline{a_{k-1}a_{k-2}\dots a_2a_1})_p$，表示 $n$ 在 $p$ 进制下的形式。

令：$m=(\overline{b_{k-1}b_{k-2}\dots b_2b_1})_p$，表示 $n$ 在 $p$ 进制下的形式。

那么有：

$$\binom{n}{m}\equiv\prod^{k-1}_{i=0}\binom{a_i}{b_i}\pmod p$$

证明

引理 1

前置芝士

1. 费马小定理

内容

对于任意质数 $p$ 和 $a$，其中 $p\nmid a$，满足：

$$a^{p-1}\equiv 1\pmod p$$

证明

根据裴蜀定理，可以知道 $\{1\dots n\}$ 与 $\{a\dots(an)\}$ 是一一对应的，因此：

$$\begin{aligned} \prod_{i=1}^{p-1}ia&\equiv\prod_{i=1}^{p-1}i&\pmod p\\ a^{p-1}\prod_{i=1}^{p-1}i&\equiv\prod_{i=1}^{p-1}i&\pmod p\\ a^{p-1}&\equiv1&\pmod p \end{aligned}$$

杂谈

最近在 zhihu 看到很多人试图和葛立恒数比大小，我就也想了想。

我想到了一个比较大的数，但是感觉肯定比葛立恒数小，但感觉挺有意思的，就分享一下。

不知道有没有人会证明。

先定义：

$$\begin{cases} f^{1}(x)=f(x) \\ f^{a}(x)=f(f^{a-1}(x))&x\ge2 \end{cases}$$

然后定义：

$$\begin{cases} g_{1}(x)=x^x \\ g_{a}(x)=g^{g_{a-1}(x)}(g_{a-1}(x)) \end{cases}$$

这道题直接 $\operatorname{mod} \varphi(p)$ 的题解很多都是错的并且没有给出证明。

解题思路

首先这道题等价于求 $(A^{m-1}B)^{n-1}A^{m-1}$。

可以直接用高精度的矩阵快速幂，但是这里不讲。

不难发现在计算过程中矩阵一定是 $\begin{bmatrix}a&b\\0&1\end{bmatrix}$ 的形式。

所以现在问题转化为了计算型为 $A=\begin{bmatrix}a&b\\0&1\end{bmatrix}$ 的矩阵快速幂。

Part1

考虑讲矩阵对角化，也就是找到一个矩阵 $P$ 满足 $PAP^{-1}=B$ 是一个对角矩阵，也就是说:

题目大意

给定 $n$，$l$，$r$ 三个数，你需要和交互器博弈。

有一个长度为 $n$ 的区间，你和交互器轮流操作。

每次操作，操作的一方选择一个没有被染黑并且长度在 $l$ 和 $r$ 之间的区间，把它染黑。

无法操作的一方寄了，另一方获胜。

每次你操作要输出两个数 $a$ 和 $b$，表示你选择了区间 $[a,a+b-1]$。

每次交互器操作会给你两个数 $a$ 和 $b$，表示交互器选择了 $[a,a+b-1]$，若 $a=b=0$ 则表示你获胜，如果 $a=b=-1$ 则表示你寄了。

解题思路

只能说这题太妙了，场上 tourist 都没过。

题目描述

• 给定一个长度为 $n$ 的序列 $a_1,a_2\dots,a_n$。
• 对于 $1\le i\le j\le n$，你可以花费 $(i-j)^2\cdot\operatorname{min}(a_i,a_{i+1}\dots a_j)$ 的代价从 $i$ 跳到 $j$。
• 你现在要对于所有的 $1\le k\le n$，输出从 $1$ 到 $k$ 的最段路。
• $1\le a_i\le n\le4\times10^5$。

解题思路

首先考虑 $O(n^2)$ 的 DP，$f_i$ 表示从 $1$ 到 $i$ 的最短路径，转移很简单。

现在要考虑把这个 DP 优化到可以接受的时间复杂度内，考虑有以下性质。

性质1

对于 $1\le i\le j\le n$，如果直接从 $i$ 跳到 $j$，那么一定不会比经过区间最小值 $a_k$ 跳两次更优。

@wsyear强无敌，模拟赛场切黑题。

题目大意

给你一个长度为 $n$ 的排列，Alice 先会把它分成 $m$ 段。

然后 Bob 会把这 $m$ 段重新排列，而每段内部位置不变。

Alice 希望这个序列字典序最小，而 Bob 希望这个序列字典序最大。

输出重排后的序列。

解题思路

考虑贪心。

题目大意

定义两个数列相似表示：其中一个数列所有元素同时加上一个数能变成另一个数列。

现在给你 $N$ 个数列，求他们的最长相似子串。

解题思路

很显然可以先作差分，这样就把问题转换为了求 $N$ 个串的最长公共子序列。

这样就是一个字符串题了。我们发现字符集很大，所以考虑用 $SA$ 做。

我们先把所有的串拼接起来，中间加上不同的分割符。

然后进行后缀排序，此时又可以发现，只要在 $SA$ 上找到一个连续区间 $[l,r]$，使 $1\ldots N$ 在这个区间里都出现过，求 $\min_{l+1\le i\le r}h[i]$ 的最大值即可。