CF1622F

设 \(n=2k\)，可以得到

\[\prod_{i=1}^n i!=\prod_{i=1}^k 2i\times\left((2i-1)!\right)^2 \]

所以要考虑的本质上是 \(2^{\lfloor\frac{n}2\rfloor}(\lfloor\frac{n}2\rfloor)!\)，直接判定这两者是不是完全平方数并哪项不是删掉即可

对于 \(n=2k+1\) 的情况，最多也只会删掉 \(n!,2!,(\lfloor\frac{n}2\rfloor)!\) 三项，那么先判定序列是不是能删掉 \(0/1/2\) 项来做到合法，否则直接给出构造

考虑给每个质因子一个随机权值，那么合数的权值就是其所有出现次数为奇数的质因子权值异或和，判定是不是存在一个 \(x!\) 的权值是 \(n!\) 以及是不是存在一个 \(x!\) 的权值是 \(n!\ \oplus\ y!\ (y\in [1,n])\) 即可

设随机向量长度为 \(B\) 时，一个不是完全平方数的数字被异或成了完全平方数的概率是 \(\left(\frac{1}2\right)^B\)，本质上是 \(\sum\limits_{x\in\{even\}}\binom{n}x=\sum\limits_{x\in\{odd\}}\binom{n}x\)，其中 \(n\) 是某个数字中出现奇数次质因子的数量

在 \(|S|=n-2\) 时 \(\frac{n!}{y!}=x!\) 中 \((x,y)\) 有 \(n^2\) 种，那么正确率就是 \(\left(1-\frac{1}{2^B}\right)^{n^2}\)，在 \(B=64\) 而非 \(32\) 时才可以得到较高正确率

Luogu4240

原式进行简单的和式变换就可以得到：

\[\sum_{i=1}^{\min(n,m)}\sum_{j|i} \mu\left(\frac{j}i\right)\frac{j}{\varphi(j)}F(i,\left\lfloor\frac{n}i\right\rfloor)F(i,\left\lfloor\frac{m}i\right\rfloor) \]

其中 \(F(n,m)=\sum\limits_{i=1}^m\varphi(in)\)

处理 \(F(n,m)\) 能做到 \(\Theta(Qn)\) 复杂度，但是其实 \(i\) 比较大的时候要求的东西在每个询问中都是差不多的，所以预处理 \(x\in[1,B],y\in[1,B]\) 的所有 \(F(n,x),F(n,y)\) 的乘积并前缀和，每次询问对于 \(i\le \left \lfloor\frac nB\right \rfloor\) 的部分暴力，剩下的整除分块即可

ARC104E

由于 \(n\) 实在是太小了，枚举其全排列，对于 \(p_i>p_{i+1}\) 那么限制是 \(a_{p_i}\ge a_{p_{i+1}}\)，否则严格大于

这时候每个位置的选值集合就是本身上界减去前面严格大于的数字，同时还要做后缀 \(\min\)

现在限制变成了大于等于，可以使用格路计数的容斥来做，设上界分别是 \(a_1\sim a_n\)，\(f_i\) 表示走到了横坐标为 \(i\) 的列的方案数（不限制纵坐标），转移就是枚举第一次超出界限的位置即可

显然要暴力算组合数，因为 \(n\) 实在是太小了

CF718E

不难观察到图的直径不超过 \(15\)，预处理 \(f_{i,c},g_{c_1,c_2}\) 分别表示 \(i\) 到颜色 \(c\) 最近的距离和颜色为 \(c_1\) 某点到颜色为 \(c_2\) 某点的最短路

不难发现一对 \((i,j)[i 的最短路就是 \(\min\limits_{c}\left\{f_{i,c}+f_{j,c}+1,j-i\right\}\)

对于 \(j-i\le 15\) 的情况，选择的中转颜色的点可能是同一个，再 \(+1\) 可能产生错误，那么直接冲暴力

否则观察到 \(f_{i,c}=g_{col_i,c}/g_{col_i,c}+1\)

否则枚举 \(j\) 考虑小于之并且距离之至少为 \(16\) 的所有 \(i\)，使用二进制状压他们的 \(f_{i,c}-g_{col_i,c}\)，这些 \(i\) 的另外一个属性是他们的颜色

对于两个属性都相同的 \(i\) 到 \(j\) 是相同的，计算即可

CF997E

扫描线，一个区间是好区间的条件是 \(\max-\min-(r-l)=0\)，使用两个单调栈分别维护最小/最大值，区间加增量即可

要求的是历史权值之和，使用一个全局加权值的操作实现

由于 \(i\) 处是 \(0\) 致使全局最小值也是 \(0\)，那么 “加权值” 的判定就是子区间最小值是大区间最小值

一开始并没有注意到加权值的判定条件，那么写了个暴力过掉了所有 Codeforces 数据，不得不震惊