(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 zzy的小号

这是一道简单组合题，代码长度极短，按照题意模拟即可，分四种情况
1、大小写的 o 和数字 0，当前位置的可能性种类 3
2、大小写的 l 和大小写的 i，当前位置的可能性种类 4
3、除 o 和 l 和 i 以外的字母，当前位置的可能性种类 2
4、除 0 外的数字，当前位置的可能种类为 1 考虑各个位置之间没有影响，那么答案即用乘法原理统计即可
时间复杂度 O(n)

T2 Jxc军训

这是一道用于混淆视听的水题，2000 的数据范围只是用于骗大家去想 dp（逃）
可以发现，云的位置实际没有影响，注意是被晒到的概率不是不被晒到的概率！所以答案就是
在题目中给出了费马小定理，那么可以知道 x -1  x p-2 (mod p) ，所以只要快速幂求出
x p  2 就可以了
时间复杂度 O（logMod）

T3 zzf的好矩阵

首先可以很容易想到，操作的顺序并不会影响最终结果，那么无需考虑操作的次序。
那么假设所有操作的最终结果是对第 i 行每个数加 x i ，对第 j 列的每个数加上 y j 。
由于最终得到的矩阵各数互不相同，则 x1 , x 2 ,, x p 互不相同，y1 , y2 ,, yp 互不相同。
为了考虑方便，不妨设 x1 小于 x 2 小于 x p ，可以发现若交换 x i 和 x j 的值相当于是交换第 i
行和第 j 行，同理，假设 y1 小于 y2 小于 yp ，那么可以发现，得到的矩阵每一行从左到右递 增，每一列从上到下递增。
那么由上面的假设可以发现 a11 =1, a12 = 2 或 a 21=2 ，那么先假设 a12 = 2 ，否则，相 当于将所得矩阵按照主对角线作对称。
仔细想一想这个所得的矩阵，肯定有同学会有感觉 1,2,, p 全在同一行中，那么现在 来证明一下（其实不证明也是可以做的，不想看证明的同学可以直接看结论）
Proof.
利用反证法证明
假设1,2,, k 在第一行中，k+1 不在第一行中。那么可以发现，a 2,1 k  1 ，这是因为，
a1,1  1, a1, 2  2 ，所以 a 2, 2  a 2,1  1 ，以及矩阵每一列从上到下递增，每一列从左到右递增，但是1,2,, k 都在第一行中，那么只可能 a 2,1 k  1 。
那么现在，将连续的 k 个整数称为一个块，那么只需证明，矩阵的第一行恰由若干个块 构成，即前 k 个构成一个块，第 k+1 到第 k+k 个构成一个块……
若不能这样构成，那么设前 n 组 k 个数均为块，之后的 k 个数不成为块，或者之后不足
k 个数，那么对于 j=1,2,, n , y( j1) k 1 , y( j1) k  2 ,, y jk 构成块，这样，矩阵的前 nk 列可以分成 pn 个 1k 的子矩阵 a i ,( j1) k 1 , a i ,( j1) k  2 ,, a i , jk (i  1,2,, p; j  1,2,, n) ，每个子矩阵的 k 个数构成块。
现 在 假 设，故从而 a1,nk 1  k 必定在前 nk 列中，这样 a1,nk 1  k 含在某个 1k 的块中，但 a1,nk 1 ， a1,nk 1  k 都不在该块中，矛盾。 所以，第一行恰由若干个块构成。
又因为，有 k|p，但1  k  p ，而 p 是质数，矛盾
所以，数表的第一行恰为1,2,, p ，第 k 行必定为（k  1）p  1, (k  1)p  2,, kp
Proof.End
因为，当现在所得的这个矩阵在交换行，交换列，关于主对角线对称总能转化为唯一的 形式
所以，好矩阵的个数为 。
此题这样就做完啦

T4 applese的生日

首先有一个结论：每块蛋糕分成的每一块的大小是相同的 基于这个结论，每次找到当前划分最大块所在的大块并将其划分数+1,检查是否满足题目的要求 考虑这个结论为什么是正确的： 考虑一个蛋糕切的刀数不变，那么可以想到假如分割得到的块是不同的，那么可能的贡献是增加最大和最小之间的差值，那么这样答案只会更劣，所以可以想到分成的每个块的大 小是相同的那么只要按照上面模拟就可以了，这题妥妥的送温暖题啊

T5 VVQ 与线段
分两种情况,线段相交和线段包含。 先按照左端点排序
1、线段相交的情况用线段树维护 l+r 的最小值
2、线段包含的情况维护 r-l 的最大值。

T6 抓fafa的qzh
这道题非常地暴力，思路也非常的简单。
首先很容易得到 O(nq+qq)的暴力。就是对于每次询问暴扫之前的每次插入操作，然 后树上差分再前缀两遍，即使通过非递归使常数比较小，但是很难卡过。
然后观察到 q 比 n 小很多（n 大约是查询次数的三倍），可以想到 O(qq)的暴力。就是 对于每次询问暴扫之前的每次插入操作，直接用 RMQ-lca 讨论一下 O(1)得到对答案的贡献。
分三种情况讨论：
两个等差数列求个和就好了。 O(qq)的复杂度看上去好多了，但是常数原因，其实还是很慢，即使 10s 也很难卡过去。
然后我们可以考虑把两种暴力结合一下分块。 观察到第一种暴力可以稍微修改一下，写成树形动规的形式，可以 O(n+x)的复杂度求
出 x 条路径对 n 个点每一个点的贡献。
然后可以考虑每 q^2/3 次插入操作后将所有插入操作按可爱值排序后按块大小为 q^2/3 分块，那么每次查询只要暴力枚举还未加入重构的插入操作，暴力枚举块边界的插入操作， 加上整块的答案就好了。假设 n,q 同阶，此时暴力重构预处理总复杂度和查询总复杂度同阶。
几种优化：
1:快读，合理的 register 和 inline。（标程有）
2:带常数重新确定重构频率。（标程有）
3:带常数重新确定块大小。（标程无）
4:树形 dp 的时候通过预处理欧拉序和 dfs 序强行非递归。（标程有）
5:通过离线，当查询到下次重构的距离小于到上次重构的距离时，通过下次重构的答案减去 还未执行的插入操作。（标程无）
6:循环展开，缓存优化等。（标程无） 由此可见，标程的实现非常劣。所以大家写的程序跑得比标程快很多其实很正常。
总时间复杂度 O(小常数)

其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305