模拟赛

T1

考虑每个格子最终的颜色，可以得出其对应的行和列的先后顺序

然后暴力的考虑添加每个列的位置就好

需要判断是否无解，最终的答案就是每个块内部随便排的方案数的乘积

T2

考虑在每段序列的结束处统计贡献

不妨设 $f_{i,j}$ 表示当前位置在 $i$ ，当前的最长不降子序列

考虑枚举最长上升子序列的长度为 $d$

在此基础上跑dp，设 $f_{i,j}$ 表示当前位置为 $i$ ，最长上升子序列中

对于一个序列的最长上升子序列，有

$$ans=n+\max_{i\in[0,n]}sum_i-sum_n-i$$
我们考虑转换一下，要让最长上升子序列最大，同时令 1 的数量尽可能多，其实也就是要让 $ans \times n+count_1$ 最大，也就是

$$pans=\max_{i\in[0,n]}n\times(sum_i-sum_n+n-i)+$$

考虑枚举 $ans$ 和 $c1$，此时问题就变成了问 “从右往左数第 $c1$ 个 $1$ 的位置大于 $ans-c1$ 且第 $c1+1$ 个 $1$ 的位置小于”

设 $f_{i,j,k,l}$ 表示当前在第 $i$ 位，前面共有 $j$ 个 $0$ ，目前的最长不降子序列为 $长k,l个1$ 的产生概率

T3

要求的即为
$$\begin{eqnarray} f(X)&=&\sum_{l=1}^{n}\sum_{r=l}^{n}[gcd(\max_{i\in[l,r]}a_i,\min_{i\in[l,r]}a_i)=X]\
&=&\sum_{l=1}^{n}\sum_{r=l}^{n}[X\mid \max_{i\in[l,r]}a_i][X\mid \min_{i\in[l,r]}a_i][gcd\left(\frac{\max_{i\in[l,r]}a_i}{X},\frac{\min_{i\in[l,r]}a_i}{X}\right)=1]\
&=&\sum_{d=1}^{\left \lfloor\frac{n}{X} \right\rfloor }\mu(d)\sum_{l=1}^{n}\sum_{r=l}^{n}[Xd\mid \max_{i\in[l,r]}a_i \wedge Xd\mid \min_{i\in[l,r]}a_i]\end{eqnarray}$$
发现这是一个调和级数问题，问题就变成了如何求

$$g(X)=\sum_{l=1}^{n}\sum_{r=l}^{n}[X\mid \max_{i\in[l,r]}a_i \wedge X\mid \min_{i\in[l,r]}a_i]$$
考虑从右往左枚举每个点 $i$ 作为最大值时的贡献，枚举 $a_i$ 的约数

对于小于其的部分可以单调栈，每个单调栈上开一个桶维护后缀的，有此约数的数的个数

然后对于其作为最大值的贡献，需要找到其右侧第一个大于等于他的位置，也就是对应单调栈上的一个前缀，拿前缀减后缀即可

这个桶使用可持久化数组维护即可

然后就得到了 $O(nlog^3n)$ 的做法

但是我们发现其实并不需要可持久化，具体的，将其需要减去的后缀的位置离线下来，然后在其第一次出现时减去贡献即可

然后我们还需要反过来跑一遍

总时间复杂度： $O(nlog^2n)$

![[day2.pdf]]