考试LIST [2021.05]
2021.05.03
$\texttt{Location:NOI2021}$
得分：$\texttt{85/300,Rank1}$。
[05.03]-错误
事实上 $\texttt{T2}$ 是最可做的，但是却没有给足够的时间。说明以后需要多加训练找最可做题的能力，从而加快进度并保证得分。
[05.03]-部分正解
$\texttt{T1}$
很抱歉，因为 $\text{std}$ 假了，所以这篇题解咕了。
$\texttt{T2}$
首要思路是贪心地判断当前是否可以走 $\text{R}$，如果走了 $\text{R}$ 之后最优走法仍然不超过限制，则走 $\text{R}$，否则不得不走 $\text{L}$。
然后很抱歉，细节咕了。
$\texttt{T3}$
首先考虑一个简单的二分方法。
二分的时候循环交替询问 $\text{[l, mid]}$ 和 $\text{[mid+1, r]}$，问出 $1$ 就往那边走。
发现这个东西从哪边开始问可能比较重要，因为找到一边直接得到 $1$ 显然比较好。所以考虑每次不以 $1:1$ 来划分区间，调调参可以拿到 $\text{40pts}$。
为什么一定要分两段呢？事实证明 分为三段之后，比例为 $2:2:1$ 然后交替询问，即可通过。可能需要玄学调参。（还没写）
2021.05.04
$\texttt{Location:NOI2021}$
得分：$\texttt{?/300,Rank?}$。
[05.04]-错误
事实上 $\texttt{T2}$ 是最可做的，但是却没有给足够的时间。说明以后需要多加训练找最可做题的能力，从而加快进度并保证得分。
[05.04]-部分正解
咕咕咕
咕咕咕
2021.05.09
$\texttt{Location:ZHZX}$
得分：$\texttt{86/300,Rank23}$。
[05.09]-错误
$\texttt{T1}$ 的结论推得过于慢了，对于这类等价类型的题目还不够熟悉。
$\texttt{T3}$ 没有快速理解题意，导致浪费了一些时间。
[05.09]-部分正解
$\texttt{T1}$
考虑将等价串通过一些方式变为相同的样子，从而计算。
首先排掉全 $\texttt{a}$ 串和全 $\texttt{b}$ 串，他们只能完全相等才等价。进一步发现，$\texttt{b}$ 的个数实际上是不变的，但 $\texttt{a}$ 是有所变化的。发现对于一个 $\texttt{b}$，左侧的 $x$ 个 $\texttt{a}$ 可以通过若干次代换变到右边去，右边也可以变到左边，令两个 $\texttt{b}$ 之间有 $x_i$ 个 $\texttt{a}$，那么可以发现：
$$ \sum_{i=1}^k (-1)^{k-1} x_i \pmod 3 $$
是不变量。两个串的这个东西相等，且 $\texttt{b}$ 的个数相等，是等价的充要条件。
考虑使用多项式来快速计算这个东西。具体来说，我们设一个前缀的多项式表示所有前缀的上述值的生成函数，这个生成函数包括两维——$\texttt{b}$ 的个数和上述值，那么一个子串实际上就会变成两个前缀的二维多项式进行运算，具体来说，在 $\texttt{b}$ 个数一维做差卷积，在上述值一维做循环卷积。
但是这个差可能不对，因为我们要令第一个 $\texttt{a}$ 的连续段的权值为 $1$，这么算可能会变为 $-1$。因此，我们还需要根据端点所在段的奇偶性来将其分类。至于这个二维 $\text{DFT}$，可以先对一维进行 $\text{DFT}$，然后大小为 $3$ 的一维直接暴力卷积。或者由于模数下存在 $3$ 次单位根，所以也可以模拟 $\text{DFT}$，实际上，暴力卷积可以减少很多讨论。
时间复杂度 $\mathcal{O}(n\log n)$。
$\texttt{T2}$
咕了
$\texttt{T3}$
神仙提答题。
大概意思是给定了 $4$ 种可以对命题使用的运算，然后要通过手动推导/代码推导来求出各种各样的结论，到现在还只拿了 $36\text{pts}$......
这种题目首先要通读一遍题面，不能漏掉信息，接着跟着提答的编号来做，当然有时候也需要考虑跳过一些任务。但是实际上这个东西也不会考吧......算个娱乐题？但是难度十分不娱乐就是了
[05.09]-总结
$\texttt{T1}$
本题是一道较为传统的题型，也给我们一些启发。对于此类等价问题，首先考虑找到变化中不变的量，这有时候需要进行一些猜测，或者是足够的手玩。同时尤其需要注意，这类题有一定几率是以群论知识为背景的，因此可以对其构建相关的模型。
找到不变量之后，需要进一步推导相关的充要条件，并且将其朝着较为容易计算的方向靠拢（例如本题就将字符串与一个 $\bmod 3$ 相关的等式进行连接从而优化计算）。接着就是考虑计算、维护这类较为传统的不变量了，对于维护问题，一般使用一些数据结构；而相关计数问题，则有时候需要考虑多项式。
2021.05.10
$\texttt{Location:ZHZX}$
得分：$\texttt{88/300,Rank43}$。
真的垫底了
[05.10]-错误
$\texttt{T2}$ 已经差不多会了正解，但是空间压不下来。在空间复杂度的控制方面没有足够的经验。
$\texttt{T3}$ 实际上是很可做的，但是考场上却只是把眼光放在部分分上。因此不能太过于知足了。
[05.10]-部分正解
$\texttt{T1}$
给定一棵 $n$ 个节点的树，满足一个节点要么没有儿子，要么有两个儿子。每个节点有一个权值。从深度深的位置开始向上，每次节点 $x$ 权值加上 $x$ 左端点权值、$x$ 右端点权值的差。多次单点修改，每次修改后求根节点权值。
$1\le n\le 2\times 10^5,0\le \text{值域}\le 20$。
发现单次操作十分不好做，因此考虑将所有操作一并进行处理。
建立一个线段树，第 $i$ 个位置表示第 $i$ 次操作之后当前节点的权值。
首先一个点的修改操作可以变成在其线段树上若干区间加（不同的区间加不同的值），然后考虑将两个儿子合并上来之后会发生什么。考虑一个暴力的做法，线段树合并的时候，把两棵线段树暴力做差，判断当前区间中是否都 $\le 0$，如果如此，则区间打上一个 $\times(-1)$ 的标记。
由于是在线段树合并，所以考虑在其中一棵线段树只剩一个节点（还没有展开）的时候，另一棵线段树上就变成了整个子树减，记录子树内权值的 $\max,\min$ 就可以快速判断当前需要继续递归还是可以直接打标记。
这样看似十分暴力，但实际上复杂度是正确的。考虑使用势能的角度来进行证明。令一棵线段树的势能是线段树内权值的极差，发现在两个线段树合并之后，最劣的情况下只是一棵树的 $\max$ 减去另一棵的 $\min$，一棵树的 $\min$ 减去另一棵的 $\max$。这样极差最大，但是这个极差仍然是原本两棵线段树极差之和。
再考虑暴力向下递归做减法来判断是否需要 $\times(-1)$。若当前区间都需要 $\times(-1)$ 或者都不需要，则子树内极差不变。否则发现必然是线段树上一个儿子要 $\times(-1)$，另一个不要。画在数轴上就是 $0$ 左右各有一个，然后把 $0$ 左侧的点翻过来。容易发现极差不会变大，所以势能不变大。
因此所有除了区间加之外的操作都不会加大势能，同时值域只有 $20$，所以总势能增加量是 $n\times v$ 的，则复杂度是 $\mathcal{O}(nv\log n)$。
$\texttt{T2}$
给定一个串 $T$ 和若干询问串 $S_i$，询问串有通配符 $?$。求每个询问串在串 $T$ 中出现多少次。
$|T|\le 10^5, \sum|S_i|\le 10^6,1\le q\le 10^5, c\le 10^5$，其中 $c$ 为 $?$ 个数。
明明不是难题但是卡我空间是真实的嘛......
回想一下没有 $?$ 要怎么做。建立 $\text{SuffixAutomaton}$，然后每次拿串在匹配边上走，然后记录 $\text{Parent Tree}$ 子树大小即可。
发现他说问号不超过 $10^5$，所以如果按照 $?$ 把串划分开，那么串不超过 $q+c$ 个。考虑求出这些不带通配符的串的 $\text{endpos}$ 集合，然后一个串的实际 $\text{endpos}$ 就是其划分后的串加一些移动之后的 $\text{and}$。
直接 $\text{bitset}$ 维护 $\text{endpos}$ 空间是 $\mathcal{O}(\dfrac{n^2}{\omega})$（与 $n$ 同阶记作 $n$），只需要 $\text{1200MB+}$。
考虑经典但是我不知道的 $\text{bitset}$ 卡空间大法——分块。设一块大小为 $B$，然后记录两个块之间的所有块的 $\text{and}$。这里空间是 $\mathcal{O}(\dfrac{n^3}{B^2\omega})$，然后就可以 $\mathcal{O}(B)$ 地求一个 $\text{endpos}$ 集合了。
我这里 $B$ 取 $2000$，就可以通过本题。
$\texttt{T3}$
给定序列 $\{a_n\}$，对于 $a$ 的每个长度 $\ge k$ 的前缀，求出将其划分为 $k$ 个非空段之后权值 $\max$。一段区间 $[l,r]$ 的权值是 $v_{\text{mex}(l,r)}$。
$1\le n\le 10^5,1\le k\le 50, 0\le a_i\le 10^9,v_i\le v_{i+1}$。
显然对于固定的右端点，左端点递减则 $\text{mex}$ 不降。设 $\text{dp}_{i,j}$ 表示长度为 $i$ 的前缀划分为 $j$ 个区间的最大权值。由于 $v_i$ 不降，所以 $\text{dp}_{i,j}$ 对于固定的 $j$，其值随着 $i$ 增加而单调不降。因此，对于一个段 $[l,r]$ 使得以他们为左端点时与右端点间 $\text{mex}$ 均为定值，那么从 $r-1$ 处转移过来一定最优。
考虑一个暴力的东西，考虑维护 $\text{mex}$ 相等的连续段，每加入一个新的值 $x$ 并以他为右端点，则 $\text{mex}$ 为 $x$ 的连续段会进行分裂，暴力用线段树维护区间的分裂，$k$ 段的话就直接分层即可。实际上复杂度没问题。
简略证明一下，倒过来，那么每次就在删除最后一个点。令这个点值为 $a$，那么找到上一个出现的位置 $p$，那么从 $p+1$ 开始，其 $\text{mex}$ 才会有变化（因为对于 $\le p$ 的位置，有一个位置可以替代 $a$），然后对 $p+1$ 及其右边的所有位置的 $\text{mex}$ 对 $a$ 做 $\text{chkmin}$。由于 $\text{mex}$ 序列是单调的，所以实际上就是一个区间赋值了。
不难发现这个赋值只会做 $n$ 次，所以倒过来复杂度是对的。那么正过去也是对的。复杂度 $\mathcal{O}(nk\log n)$。或者这么证明：一开始只有一段，每次分裂一些段，至多分裂成 $n$ 段，也就是至多分裂 $n$ 次，所以复杂度是对的。
[05.10]-总结
$\texttt{T1}$
本题又是对势能线段树的巧妙运用。值域 $\le 20$ 是一个极强的条件了，所以应该考虑从这个方面来进行复杂度的控制。
同时本题也启发我们，在单次询问操作不好做的时候，可以考虑将多次询问一起求解，然后使用数据结构等方式来进行复杂度优化。需要注意的是，不见得要修改互相独立才可以这么用，本题中就将修改互不独立改为了时间上的区间修改，这也是很好的思路。
$\texttt{T2}$
本题给出一种对通配符的处理方法：跳过。虽然看起来很不正经，但是实际上在通配符不多的时候，划分区间就不会很多，这样在一定程度上可以保证复杂度。
接着给出的 $\text{trick}$ 就是将 $\text{bitset}$ 分块，这是一种较为常见的用时间换空间的方式。另一种表现形式是将算法进行若干次，每次只考虑一个块内的点的贡献，这需要块之间贡献容易计算或者没有贡献。
$\texttt{T3}$
首先观察特殊性质——$k\le 50$，发现 $\mathcal{O}(nk)$ 是可以接受的复杂度，所以考虑分层进行 $\text{dp}$，然后就应该套路地考虑使用数据结构进行维护。同时记住经典的结论：区间 $\text{mex}$ 的变化量在移动的时候不大，然后就可以考虑维护连续段，从而维护 $\text{dp}$ 值了。
同时，本题还有一个重要的点，那就是根据 $v_i\le v_{i+1}$，从而推出在一定限制下 $\text{dp}$ 数组不降，这就把前驱状态的数量从 $\mathcal{O}(n)$ 级别变成了 $\mathcal{O}(\text{mex连续段个数})$ 级别了。因此以后要积极推单调性，有时会有很好的效果。
2021.05.11
$\texttt{Location:ZHZX}$
得分：$\texttt{42/300,Rank49}$。
又垫底了
[05.11]-错误
$\texttt{T3}$ 明明是刚刚总结过的 $\text{trick}$，考场上已经差不多写完了，却又没有写过。
[05.11]-部分正解
$\texttt{T1}$
给定一个栈，栈空间有限制。每一天可以在栈顶加入一个肉罐头、弹出一个罐头或者什么都不干。有 $m$ 次操作，第 $i$ 次发生在第 $t_i$ 天操作之后，会从栈底将连续 $d_i$ 个肉罐头变空。如果不足 $d_i$ 个则解不合法。设 $f(x)$ 为栈空间为 $x$ 时，最后剩下的肉罐头个数的 $\max$，如果没有合法方案，则值为 $-1$。
求 $\sum_{i=0}^{n} 233^i f(i)$。
$1\le m\le 10^5, 1\le n\le 10^{18}$。
考虑先找出最小需要的栈容量。
显然的是，如果有一个时刻需要吃罐头，但这个时刻与上一次吃罐头的时刻之间的时间不足以加入这么多的罐头，那么就将两次吃罐头合并。这样吃罐头之间就两两不交了。
那么使得栈空间最小的方案一定是每次一吃就将栈中所有肉罐头吃完。那么每次就先弹出一些罐头，如果没有罐头了就保持不变，最后再加入若干罐头。把这个过程看做一个折线，弹出罐头折线下降，不同则折现持平，加入罐头则折线上升。不难发现，折线段数是 $\mathcal{O}(m)$ 级别。
接着考虑加大答案。显然的，我们想将下降的、持平的折线尽量改成上升的。同时，越后面的操作的限制可以认为越少，所以从后往前调整，考虑加大答案。
对于一段持平的曲线，只需要将当前持平改为上升就可以使得答案加大 $1$。但是下降不一样，下降需要先改为持平，此时使用的栈空间 $+1$，但答案并不会 $+1$。因为此时相当于将”弹出一个空罐头“变成什么都不干，所以并不会增大答案。然后剩下的就是数学推导的部分了，大概需要推几个类似等比数列的东西。
时间复杂度 $\mathcal{O(m)}$。
$\texttt{T2}$
定义 $f(x,y)=\sum_{k=0}^x (-1)^{|k\cap y|}$，其中 $\cap$ 是按位与，绝对值表示 $\text{popcount}$。$T$ 组询问，每次给定 $l,r,u,v$，求 $\sum_{i=l}^r\sum_{j=u}^v f(i, j)$。
$1\le T\le 3\times 10^5, 0\le l,r,u,v\le 10^{18}$。
考虑求出：
$$ \sum_{i=0}^x \sum_{j=0}^y f(i,j) $$
然后就类似一个矩阵差分的形式了。考虑在 $f$ 计算式中的 $k$，和 $y$ 的取值。观察二进制位，若 $x$ 某一位是 $1$，$k$ 这一个位置是 $0$ 或者没有顶满上界，那么 $y$ 只有在后面所有位都是 $0$ 的时候才会有非 $0$ 的贡献，且是 $2$ 的整次幂。因为如果 $y$ 后面位上有 $1$，可以证明其贡献恰好抵消掉了。
然后考虑数位 $\text{dp}$，具体细节咕了。
$\texttt{T3}$
现在有若干初始为空的集合，集合中元素是二元组 $(x,y)$。现在要支持 $q$ 次以下操作：
1.在集合 $a$ 中插入元素 $(x,y)$，保证 $x$ 互不相同。
2.将集合 $b$ 中所有元素加入集合 $a$，保证集合 $a,b$ 中元素无交。
3.查询集合 $a$ 中，第一维 $x\in[l,r]$ 的所有二元组的第二维的和。
$1\le q,x,y,l,r\le 2\times 10^5$。$\text{2s, 64MB}$。
考虑 $\text{bitset}$。
前两个操作很好维护，考虑第三个要怎么维护。很简单的想法是对 $\text{bitset}$ 分块，然后就可以根号求解和了。但是发现由于要存 $n$ 个 $\text{bitset}$，所以空间是 $\mathcal{O}(\dfrac{q^2}{\omega})$，卡不过去。
所以换一种分块形式，发现一个块中元素之间没有任何影响，且块之间也只有相同位置的元素会有互相影响。因此每次只考虑 $\sqrt{q}$ 个位置，然后将算法循环 $\sqrt{q}$ 次，时间复杂度 $\mathcal{O}(\dfrac{q^2}{\omega})$，空间复杂度 $\mathcal{O}(\dfrac{q\sqrt{q}}{\omega})$。
[05.11]-总结
$\texttt{T1}$
考场想到这个方向上来了，但是没有深入思考。这题能够给我的一些小想法在于，将一些较为抽象的东西转化为图像的形式，然后对着图像进行求解可能有更好的效果。剩下的我就没啥可以总结的了
$\texttt{T2}$
打表打表打表打表打表打表打表打表
对于任意和二进制相关的题目，一定要从分位考虑的方向进行思考，从每一位独立的性质开始推导结论。例如本题中就考虑了对于一个位，什么样的情况下没有贡献了，从而转化为数位 $\text{dp}$。
同时，有时候这种求和嵌套的题也不见得是要推导很多的柿子才可以做，转化为数位 $\text{dp}$ 或者根据组合意义进行求解有时候也是一种方向。
$\texttt{T3}$
对于集合操作的题，实际上就类似一个二进制数字的操作（与或非等），这类问题如果没有很好的解决方法，不放考虑 $\text{bitset}$。他在优化暴力做法的方向上有很好的效果。同时，分块压空间！！！
2021.05.12
$\texttt{Location:ZHZX}$
得分：$\texttt{300/300,Rank8}$。
阿克！！！
[05.12]-错误
$\texttt{T1}$ 明明可以更快解决，却没有及时发现十分简单的性质。
$\texttt{T2}$ 做法较为复杂，导致花费了很长的时间。
[05.12]-部分正解
$\texttt{T1}$
给定 $n,m$，求：
$$\sum_{i=1}^n\sum_{j=1}^m \varphi(\gcd(i,j))$$
$1\le n, m\le 10^9$。
用脚推推柿子：
$$ \sum_{i=1}^n\sum_{j=1}^m \varphi(\gcd(i,j)) $$
$$ \sum_{d=1}^{\min(n,m)} \varphi(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor} [\gcd(i,j)=1] $$
$$ \sum_{d=1}^{\min(n,m)} \varphi(d)\sum_{p=1}^{\min(n,m)} \mu(p) \left\lfloor\dfrac{n}{dp}\right\rfloor \left\lfloor\dfrac{m}{dp}\right\rfloor $$
$$ \sum_{T=1}^{\min(n,m)} \left\lfloor\dfrac{n}{T}\right\rfloor \left\lfloor\dfrac{m}{T}\right\rfloor \sum_{d|T} \varphi(d)\mu(\dfrac{T}{d}) $$
后面是 $\varphi * \mu$，可以线性筛，这就可以做线性了。
观察前面，发现是个数论分块，套上杜教筛就可以做 $\mathcal{O}(n^{\frac{2}{3}})$ 了。
$\texttt{T2}$
给定 $n\times m$ 的矩阵，满足 $n,m$ 都是 $6$ 的倍数。从 $(1,1)$ 开始，一开始蓄力为 $1$。每次可以从 $(x,y)$ 走到 $(x\pm 1,y\pm 1)$，蓄力 $+1$；或者若当前蓄力为 $k$，则可以从 $(x,y)$ 跳到 $(x,y\pm k)$ 或 $(x\pm k, y)$。
构造方案不重不漏地走完整个矩阵。
$1\le n, m\le 1000, 6|n,m$。
发现是 $6$ 的倍数这个性质很奇妙，所以自然地想到把矩阵分成很多个 $6\times 6$ 的小矩阵，然后拼起来。
对于 $6\times 6$ 的矩阵，可以直接暴搜一些方案出来，他们要具有一定的性质，例如从哪里开始，到哪里结束，蓄了多少力等。然后打表存下来拼接即可。
$\texttt{T3}$
给定 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子。$\text{Alice}$ 和 $\text{Bob}$ 轮流取石子，$\text{Alice}$ 先手。每个人一轮可以从一堆石子里选出 $>0$ 个石子，无法选择的人输。
询问对于每一个位置 $x$，有多少石子区间包含 $x$，且存在一种方法，使 $\text{Alice}$ 和 $\text{Bob}$ 在这个区间上玩上述游戏，$\text{Alice}$ 第一步从第 $x$ 堆中选择一些石子后 $\text{Alice}$ 必胜。
$1\le n\le 10^5, 1\le a_i\le 10^9$。
就是个简单的 $\text{nim}$ 游戏。考虑一个区间的异或和 $s$ 和一个在区间中的位置 $x$。若这个区间对位置 $x$ 有贡献，则有：$s\text{ xor }a_x<a_x$。也就是说，$\text{Alice}$ 如果想赢，则需要在取完石子之后异或和为 $0$，那么需要留下 $s\text{ xor }a_x$ 个石子，且留下的石子个数不能超过 $a_x$。
发现这个条件是充要的。这个条件满足，当且仅当 $a_x$ 在 $\text{highbit}(s)$ 这一位上是 $1$。因为只有这样，两个数字异或之后才会变小。
考虑枚举 $x$，维护数组 $\text{sum}_i$ 表示 $\text{highbit}(s)=2^i$ 且包含 $x$ 的区间个数。那么位置 $x$ 的值就是所有 $a_x$ 为 $1$ 的位置的 $\text{sum}$ 的和。
观察在 $x$ 向右移动一步的时候，$\text{sum}$ 数组的变化。首先，只有一个前缀从 $x$ 右边变到 $x$ 的左边，其他的位置实际上都恰好异或上一个 $a_x$，所以他们之间的异或的 $\text{highbit}$ 不变。
那么就只需要考虑 $x$ 这个前缀从右边变到左边。只需要减去他和左边值的贡献，再加上与右边值的贡献即可。可以用两棵 $\text{01trie}$ 维护，时间复杂度 $\mathcal{O}(n\log a_i)$。
中间在 $\texttt{ZHZX}$ 的题鸽了，随缘补。
2021.05.26
$\texttt{Location:NOI2021}$
得分：$\texttt{120/300,Rank3}$。
[05.26]-错误
测了 $\texttt{T1}$ 空间忘了测 $\texttt{T2}$ 然后保龄了。
$\texttt{T2}$ 细节没有写对。
[05.26]-部分正解
$\texttt{T1}$
显然需要用的段数单调不降，方案数直接从上一层（当前段数-1）的位置转移。
用线段树维护即可。复杂度 $\mathcal{O}(n\log n)$。
$\texttt{T2}$
置换中长 $l$ 的环在 $k$ 次复合之后会变成 $\gcd(l, k)$ 个长度为 $\dfrac{l}{\gcd(l,k)}$ 的环。所以把所有相同的长度拿出来，他们之前可能是一个环。不同长度的环是独立的，相同长度的环只有存在 $l$ 使得 $v=\gcd(l,k)$ 的 $v$ 可能之前是一个环，由于 $k$ 很小所以可以直接抓出来。做个背包状 $\text{dp}$ 乱乘一点系数即可。复杂度 $\mathcal{O}(n\text{d}(k))$。
$\texttt{T3}$
$k=1$ 是最小割简单模型。现在 $2^n$ 个集合中已经找到了最优解的集合，假设选择了 $a_1,a_2\cdots a_c$，没选 $a_{c+1}\cdots a_n$。考虑将剩下 $2^n-1$ 个集合划分成若干种，然后求解这些集合中的最优解。
方式是强制一些选择或者不选择，大概分为 $1-c$ 中某个数字强制不选择，前面强制选择；$c+1-n$ 中某个数字强制选择，$1-c$ 强制选择，前面强制不选择。
复杂度 $\mathcal{O}(nk\text{maxflow}+nk\log(nk))$，实则跑得飞快。
2021.05.27
$\texttt{Location:NOI2021}$
得分：$\texttt{0/300,Rank5}$。
[05.27]-错误
就没在打
[05.27]-部分正解
$\texttt{T1}$
斜线涉及的行是一个区间。不妨先染斜线，然后再染行。
考虑留空一些斜线，然后就会存在一些行是不满的，这时候考虑使用染行来进行填充。为了不算重，我们只染留空的斜线涉及的行的并。这中间可以染一些行，但是不能染出一条新的斜线，否则就会算重。也就是不能有一个区间中的元素全部被选择。那么变为：
给定 $n+m-1$ 个区间 $[l_i,r_i]$，选择一些区间，在区间并中选择元素。但是不能把一个选择的区间中的元素全部选择，计算方案数。
考虑 $\text{dp}$。由于斜线涉及的区间是单调的，类似滑动窗口。所以设 $\text{dp}_{i,j}$ 表示前 $i$ 个区间，选择第 $i$ 个区间，第 $i$ 个区间的最后 $j$ 个元素被选择的方案数。转移则枚举上一个选择的区间，然后根据两个区间之间的关系进行分类讨论即可。
$\texttt{T2}$
很强的题。
但是很难写，所以咕了。
$\texttt{T3}$
鸽了。
[05.27]-总结
对于本场这种较为考察思路的场，我的进程并不是很顺利。对于 $\texttt{T1}$ 的算重，没有找到好的规避方式，导致后续做题不顺。
2021.05.29
$\texttt{Location:NOI2021}$
得分：$\texttt{139/300,Rank2}$。
[05.29]-错误
$\texttt{T1}$ 没有推出任何有用的结论，导致只有 $\text{40pts}$。
$\texttt{T2}$ 上花了很多时间，最后没有观察到题目中的关键数据范围，导致没有能得到正解。
$\texttt{T3}$ 是数据结构，但是没有给到足够的时间来思考。
[05.29]-部分正解
$\texttt{T1}$
$$ \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n \left\lfloor\dfrac{n}{i\times j\times k}\right\rfloor[\gcd(i,j)=1] $$
观察柿子，其中特殊的是 $[\gcd(i,j)=1]$。别急着反演，看看这个 $k$ 到底啥意思。是不是就是枚举了两个数字的 $\gcd$，那么剩下的部分 $i,j$ 需要互质。因此 $i\times j\times k$ 是不是意味着两个数字的 $\text{lcm}$！
因此上述柿子把 $k$ 提前，意思就变成了枚举两个数字的 $\gcd$。因此这个柿子可以写成：
$$ \sum_{i=1}^n\sum_{j=1}^n \left\lfloor\dfrac{n}{\text{lcm}(i,j)}\right\rfloor $$
再看，$\left\lfloor\dfrac{n}{\text{lcm}(i,j)}\right\rfloor$ 是不是就是 $[1,n]$ 中 $\text{lcm}(i,j)$ 的倍数！那么又可以写成：
$$ \sum_{i=1}^n\sum_{j=1}^n \sum_{k=1}^n [i|k][j|k] $$
$$ \sum_{k=1}^n \Big(\sum_{i=1}^n [i|k]\Big)\Big(\sum_{j=1}^n [j|k]\Big) $$
$$ \sum_{k=1}^n \sigma_0^2(k) $$
上 $\text{Min25}$ 筛即可。
$\texttt{T2}$
考虑 $\text{burnside}$ 引理。显然有 $n!m!$ 个置换，可以认为是行置换和列置换进行一种组合得到的。
通过各种方式可以发现，若行置换的环大小序列是 $\{a_x\}$，列置换环大小序列是 $\{b_y\}$，那么组合起来的置换的等价类个数为：
$$ \sum_{i=1}^x\sum_{j=1}^y \gcd(a_i,b_j) $$
那么这个置换的不动点个数就是：
$$ c^{\sum_{i=1}^x\sum_{j=1}^y \gcd(a_i,b_j)} $$
那么答案就只和两个置换的环大小有关了。
观察到 $n\times m\le 1000$，这意味着 $\min(n,m)\le \sqrt(1000)$！这个数字十分小，所以可以直接考虑整数拆分了。
不妨令 $n\le m$，那么对 $n$ 整数拆分。现在拆出序列 $\{a_k\},\{c_k\}$，满足 $\sum_{i=1}^k a_i\times c_i=n$，考虑有多少置换满足这个条件。令序列 $\{b_p\}$ 是可重的 $\{a_k\}$ 序列，即 $a_i$ 在 $b$ 中有 $c_i$ 个，那么置换个数应该是：
$$ \dfrac{\binom{n}{b_1, b_2\cdots b_p} \times \prod_{i=1}^p (b_i-1)!}{\prod_{i=1}^k c_i!} $$
先选出每个环中的元素，进行圆排列，相同大小的环没有顺序，所以除一下。算出来是：
$$ \dfrac{n!}{\prod_{i=1}^k a_i^{c_i}\times c_i!} $$
用这一个柿子，先做整数拆分，然后类似地对 $m$ 一边做一个类似背包的 $\text{dp}$ 来计数即可，由于枚举环大小和环个数，所以一次 $\text{dp}$ 是 $\mathcal{O}(m^2\log m)$ 的（调和级数）。
时间复杂度 $\mathcal{O}(\text{p}(n)\times m^2\log m)$，其中 $\text{p}(n)$ 是拆分数。
$\texttt{T3}$
考虑对答案根号分治查询。
对于答案长度 $>T$ 的情况，对序列进行分块。那么必然这个答案区间跨过两个端点。维护一下一个块从左往右、从右往左能走多远即可。
对于答案长度 $\le T$ 的情况，将询问离线，枚举长度。那么就是把所有这个长度的区间拿出来，贪心地选择最有可能满足条件的即可。显然 $T=\sqrt{n}$ 时最优。
时间复杂度 $\mathcal{O}(n\sqrt{n})$。