省选模拟 1.11~
1.11
T1 的暴力 DP 写了很久，心里也觉得不太稳，但过了大样例就没管，结果爆 0 了。。。还是不能有侥幸心理
T2 想到了正解结论但写了个暴力维护没过样例，以为假了，而且时间也不太够
T3 想到了正解结论的弱化版，还是缺少观察
首先是时间分配不太合理，在感知到 T2 可做的情况下还花了大量时间做 T1，不太划算
其次是有些浮躁，能想出一些东西但不够深入
「没啥了，没啥，就挺自卑的，挺难受的，感觉啥也不是——pyt」
序列（ARC100F）
序列 \(A\) 出现多次算多次，那么可以枚举出现位置算有多少个彩色序列，直接算很难，考虑算补集（有多少个非彩色序列包含 \(A\)）。
直接 DP 需要状压（判断 \(A\) 是否出现），减小状态的关键是观察 \(A\) 在不同情况下的性质，分类讨论采用不同 DP 方式
具体做法官方题解很详细了
有向图（CF1361E）
「至少 \(20\%\) 结点有趣」显然是用来随机化找到一个有趣点的
建 dfs 树，如果树中存在前向边/横叉边那么根一定不合法，否则树上都是返祖边，考虑其他点是否合法
结论：一点合法的充要条件是其子树中的返祖边仅有一条指向子树外（该点祖先），且该点祖先合法
正确性显然
实现方法貌似有很多
图形（CF1290F）
设每个向量选了 \(k_i\) 次，那么合法的 \(\{k_{1},\cdots,k_{n}\}\) 一定唯一对应一个凸包，因此本质是数序列。同时可以发现，凸包横坐标极差为 \(\sum_{x_{i}>0}k_{i}x_{i}\)
朴素做法是枚举每个 \(k_i\) 或状压当前 \(\sum k_{i}x_{i}\)。
类似「NOIP2021 T2」，考虑按位 DP 来凑出 \(k\)。枚举 \(k_i\) 在当前位的取值，结合上一位的进位可以得到 \(\sum_{x_{i}>0}k_{i}x_{i}\)，合法的条件是 \(\sum_{x_{i}>0}k_{i}x_{i}，\sum_{x_{i}<0}k_{i}x_{i}\) 当前位相同。
为了保证 \(\sum_{x_{i}>0}k_{i}x_{i}\le m\)，还需要记当前及以后位是否 \(\le m\)
这个 trick 大概对于 \(\sum^{n}k_{i}x_{i}=m\)，\(n,x\) 很小而 \(m\) 很大的题都适用
1.13
没啥大问题，唯一的遗憾就是最后 30min 没有玩 T1 的 \(k\le3\) 而是去打 T3 的表
守序划分问题
结论：一个划分是守序的，等价于 \(\forall k\in(1,n],\exists i,\min A_{i}
必要性：若不满足，则可将 \(A\) 根据 \(\max\) 与 \(k\) 的大小划分为两个集合 \(S,T\)，则有 \(\forall i\in S,j\in T,\max A_{i}
充分性：考虑归纳构造。先将 \(A\) 以 \(\min\) 排序，设前 \(i\) 个 \(A\) 已排列成环，根据结论一定存在 \(j\le i,\min A_{j}<\min A_{i+1}<\max A_{j}\)，又有 \(\min A_{j-1}<\min A_{i+1}\)，可以将 \(A_{i+1}\) 放在 \(A_j\) 之前
发现我们只关心每个 \(A\) 的 \(\min,\max\)，且不关心其具体大小，可以以此 DP。从小到大枚举每个数 \(i\)，考虑其放到那个集合中。
设 \(f[i,j,k]\) 为前 \(i\) 个数，分成 \(j\) 个集合，其中 \(k\) 个的 \(\max\ge i\)，转移有四种：
- \(i\) 放到原来集合中：\(f[i+1,j,k]+=k\times f[i,j,k]\)
- \(i\) 放到原来集合中并作为最大值：\(f[i+1,j,k-1]+=k\times f[i,j,k]\)
- \(i\) 新开一个集合（作为最小值）：\(f[i+1,j+1,k+1]+=f[i,j,k]\)
- \(i\) 新开一个集合并作为最大值（即该集合中只有一个元素 \(i\)）：\(f[i+1,j+1,k]+=f[i,j,k]\)
欧拉函数
做法很多：分块，莫队，线段树+bitset。标算是 \(\text{poly}\log\) 的
显然难点在于单点修改、区间乘积的 \(\varphi\)，即 \(\prod(1-\frac{1}{p})\)。（每个质因子只贡献一次，所以本质是数颜色）
修改本质是删除和插入，而删除可以看作插入的逆元，分别考虑每个质数的插入。使用 set 维护集合 \(\{i|p\mid a_{i}\}\)（即质因子包含 \(p\) 的位置集合）
这类问题的经典想法是容斥。记 \(w=1-\frac{1}{p}\)，在 \(i\) 位置插入时，求出其前驱 \(pre\)，后继 \(suf\)，然后在 \((pre,suf),(i,i)\) 上乘 \(w\)，\((pre,i),(i,suf)\) 上乘 \(\frac{1}{w}\)，这样查询 \([l,r]\) 时只需要查正方形 \((l,l)\sim(r,r)\) 的权值积，这是一个朴素的三维偏序
时间复杂度为 \(O(n\log^{2})\)。但 \(40000\) 内的数最多有 \(6\) 个不同质因子，每次修改需要在平面上加入 \(6\) 个点，因此常数很大