暑假（5）
NOIP2023模拟测试赛（二十二）
A
考虑一个 \(\Theta(n^5)\) 暴力 dp，设 \(dp_{i,l,r}\) 表示考虑前 \(i\) 行，第 \(i\) 行 \(k\) 天后删剩区间 \([l,r]\) 的概率。
转移枚举上一行的 \([l',r']\)，如果有交集就可以转移。这一行删剩 \([l,r]\) 的概率是
\[\binom{k}{l-1}p^{l-1}(1-p)^{k-l+1}\binom{k}{m-r}p^{m-r}(1-p)^{k-m+r} \]有交集，等价于不满足 \(r'<l\) 且不满足 \(l'>r\)。这两个是独立的，我们可以用全部概率减去这两种的概率来转移。
对于 \(r'<l\) 显然可以维护一个前缀和，\(pre_{i,x}\) 表示所有 \(r\le x\) 的 \(dp_{i,l,r}\) 之和。
对于 \(l'>r\) 也一样，维护一个 \(suf\)。那么复杂度就降到了 \(\Theta(n^3)\)。
再优化，考虑设新的 \(dp1_{i,l},dp2_{i,r}\) 分别表示左/右端点为 \(l\) 或 \(r\) 的 \(dp_{i,l,r}\) 之和。
转移，对于 \(dp1_{i,l}\) 有：（\(sum\) 表示 上一行概率之和）
\[dp1_{i,l}\gets\sum_{r=l}^m(sum-pre_{i-1,l-1}-suf_{i-1,r+1}){\color{red}\binom{k}{l-1}p^{l-1}(1-p)^{k-l+1}}\binom{k}{m-r}p^{m-r}(1-p)^{k-m+r} \]红色部分可以提出去，\(sum-pre-{i-1,l-1}\) 作为定值也可以提出去算，预处理右边一坨后缀和就好了。
然后就是要算
\[\sum_{r=l}^msuf_{i-1,r+1}\binom{k}{m-r}p^{m-r}(1-p)^{k-m+r} \]沃趣，这个式子求和的东西和 \(l\) 无关，直接每一行做完预处理一下即可。
\(dp2\) 也是一样处理。复杂度 \(\Theta(n^2+k)\) 或者也可以不 \(+k\)。
B
随便定一个根比如 \(1\)。将题目中的链分成两种，第一种是直链，即 \(u,v\) 有祖孙关系，否则为第二种曲链。
发现所有曲链只要选了 \(1\) 就能满足。所以先考虑直链，如果满足完曲链的条件就不用选 \(1\) 了。
如果树是一条链，有一个经典的贪心，将直链的偏上面的点按深度从大到小排序。
然后从深度大的点往小的考虑，每次看这条链是否已被满足条件，如果不满足，发现选偏上的点的儿子一定最优，即深度越小越好。
树上也一样，将链按上面的点的深度从大到小排序后，选链上合法的深度最小的点一定是最优的。
用树状数组加点，检测这条链是否被满足条件即可。复杂度线性对数。
ps：我也不知道为什么选 \(1\) 做根就是对的，换句话说，为什么每个点作为根的答案都一样。
C
对所有路径考虑的问题，可以点分治。这样问题变成求当前根下不同子树之间的贡献。
根有多个子树，设为 \(v_{1\sim m}\)。考虑每次求一个子树 \(v_k\) 对之前 \(v_{1\sim k-1}\) 的贡献。
假设子树 \(v_{1\sim k-1}\) 的所有点集合为 \(A\)，子树 \(v_k\) 的所有点集合为 \(B\)。那么就是求
\[\sum_{x\in A}\sum_{y\in B}\varphi(a_xa_y)(dep_x+dep_y) \]设 \(V1_i\) 表示 \(A\) 中等于 \(i\) 的值的个数，\(V2_i\) 表示 \(B\) 中等于 \(i\) 的值的个数，\(D1_i\) 表示 \(A\) 中值等于 \(i\) 的点的 \(dep\) 之和，\(D2_i\) 表示 \(B\) 中值等于 \(i\) 的点的 \(dep\) 之和。则就是要求
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n\sum_{x\in A}\sum_{y\in B}\varphi(ij)(dep_x+dep_y)[a_x=i][a_y=j] &=\sum_{i=1}^n\sum_{j=1}^n\varphi(ij)\sum_{x\in A}\sum_{y\in B}dep_x[a_x=i][a_y=j]+dep_y[a_x=i][a_y=j]\\ &=\sum_{i=1}^n\sum_{j=1}^n\varphi(ij)(D1_iV2_j+V1_iD2_j)\\ \end{aligned}\]有 \(\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\)，于是
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n\varphi(ij)(D1_iV2_j+V1_iD2_j) &=\sum_{i=1}^n\sum_{j=1}^n\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}(D1_iV2_j+V1_iD2_j)\\ &=\sum_{d=1}^{n}\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}\frac{\varphi(id)\varphi(jd)d}{\varphi(d)}(D1_{id}V2_{jd}+V1_{id}D2_{jd})[\gcd(i,j)=1]\\ &=\sum_{d=1}^{n}\sum_{k=1}^{n/d}\mu(k)\frac d{\varphi(d)}\sum_{i=1}^{n/kd}\sum_{j=1}^{n/kd}\varphi(ikd)\varphi(jkd)(D1_{ikd}V2_{jkd}+V1_{ikd}D2_{jkd})\\ &=\sum_{s=1}^{n}\sum_{d|s}\mu(\frac sd)\frac d{\varphi(d)}\sum_{i=1}^{n/s}\sum_{j=1}^{n/s}\varphi(is)\varphi(js)(D1_{is}V2_{js}+V1_{is}D2_{js})\\ &=\sum_{s=1}^{n}\sum_{d|s}\mu(\frac sd)\frac d{\varphi(d)}\left(\left(\sum_{i=1}^{n/s}\varphi(is)D1_{is}\right)\left(\sum_{j=1}^{n/s}\varphi(js)V2_{js}\right)+\left(\sum_{i=1}^{n/s}\varphi(is)V1_{is}\right)\left(\sum_{j=1}^{n/s}\varphi(js)D2_{js}\right)\right)\\ \end{aligned}\]维护后面四个东西即可，每次加入一个点会对所有它的因数 \(s\) 的部分有贡献，且可以 \(\Theta(1)\) 修改。
所以加入一个数 \(x\) 是 \(\Theta( d(x) )\) 的。题目保证所有数因数个数之和是小的。
复杂度 \(\Theta(\log n\times \sum_i d(a_i))\)。
NOIP2023模拟测试赛（二十三）
A
容易发现要么白赢要么平局。阿巴讨论一下即可。
具体地，分有白点和没有白点讨论，再对度数、叶子、奇偶什么的讨论一下。
B
C
扫描线扫 \(j\)，维护所有的 \(g(i,j)\)。
发现 \(g(i,j)\) 其实就是 \([i,j]\) 中第一个满足 \(nxt_x>r\) 的 \(x\)。考虑扫描线右端扩展一个数 \(j+1\)。
则找到 \(x=pre_{j+1}\)，那么原先 \(g(i,j)=x\) 的要修改成下一个满足 \(nxt>j+1\) 的数了。
可以用线段树维护 \(g(i,j)\) 的区间修改，再用 st 表或者其他求出 \(x\) 后一个满足 \(nxt>j+1\) 的数。
考虑查询，发现其实就是历史版本和，那么线段树维护区间加区间历史和即可。
\(\Theta(n\log n)\)。
NOIP2023模拟测试赛（二十四）
A
考虑对于给定序列如何求密度。发现每次将一段最短的包含 \(1\sim c\) 的前缀删去，能删多少次密度就是多少。
为什么呢？密度肯定大于等于这样的划分次数，因为每一段都能选出一个想要的数。
密度也不会大于它。假设这样求出的密度为 \(p\)，我们发现，有一个长度为 \(p+1\) 的子序列不可能在原序列中出现过，构造方式如下：
- 划分成 \(p\) 段后，选择每一段最后一个数组成一个子序列，最后再加一个任意数。
由于每段最后一个数在此段只出现一次（尽量最短划分），前 \(p\) 个数只有一种选择，第 \(p+1\) 个数就没得选了。
这样我们就得到了一种求密度的方法。现在考虑在这个方法上 dp：
- \(dp_{i,p}\) 表示只考虑区间 \([i,n]\)，选的子序列强制选 \(i\)，密度为 \(p\) 的方案数。
初始状态要稍微预处理一下，即 \(p=0\)。
转移，考虑枚举 \(i\) 开头新的一段 \([i,j]\)，以及后面子序列第一个数位置 \(k\)：
\[dp_{i,p}\gets\sum_{j=i}^nf_{i,j}\sum_{k=j+1}^n dp_{k,p-1} \]\(f_{i,j}\) 表示 \([i,j]\) 强制选 \(i,j\)，选出一个包含 \(1\sim c\) 的子序列的方案数。
注意这里 \(a_j\) 是最后一个选的数，代表它仅出现一次，因此不能再选 \([i,j]\) 内的其他 \(a_j\)。
\[f_{i,j}=\left(2^{c_{a_i}-1}\right)\prod_{x\not=a_i,a_j}\left(2^{c_x}-1\right) \]\(c_x\) 表示 \(x\) 在 \([i,j]\) 中出现次数。\(f\) 容易用上式预处理。
\(dp\) 式子中的第二个 \(\Sigma\) 容易后缀和处理。这样，复杂度就是 \(\Theta(n^3)\)。
但是会发现密度最大为 \(n/c\)，所以复杂度变成 \(\Theta(\frac{n^3}c)\)。
\(c\) 很小的时候过不了。那么考虑设计一个针对 \(c\) 较小的算法。
考虑状压 dp。设 \(dp_{i,j,S}\) 表示考虑 \([1,i]\)，已经分了 \(j\) 段，最后一段中已经包含 \(S\) 中的数的方案数。
这里 \(S\) 是由 \(1\sim c\) 中的数组成的集合。
直接转移，复杂度 \(\Theta(n\times\frac nc\times2^c)=\Theta(\frac{n^22^c}c)\)。
结合两个算法即可通过。取分治界 \(c=\Theta(\log n)\) 得复杂度 \(\Theta(\frac{n^3}{\log n})\)。
B
新科技，咕咕咕
C
形如 S，*S，S* 的计算是平凡的，考虑 S*T。
建 SAM，枚举 S*T 中 S 在 SAM 中的等价类。假设我们得到这个等价类的 \(\text{endpos}\) 集合，对于每个 \(\text{endpos}\) 中的位置 \(x\)，把它 \(+1\) 就是星号的位置，加 \(2\) 就是 \(T\) 的开始位置。
那么就是求，所有 \(x+2\) 位置的后缀有多少个本质不同的前缀。求出来后乘上等价类中串数就是该节点的贡献。
这个问题可以考虑 SA，将这些后缀排序后，用所有的前缀数减去相邻的 LCP 长度即为不同前缀数量。
但是不能枚举 \(\text{endpos}\) 内每个位置。考虑启发式合并，用 set 维护每个节点的排序后的后缀。
将一个数插入 set 时删去前驱与后继之间的贡献，加入自己与前驱、与后继的贡献。
复杂度即为 \(\Theta(n\log^2n)\)。
NOIP2023模拟测试赛（二十五）
A
首先，\(x+y\) 是这个问题的循环节。可以自己画图看看。
其次，可以证明答案一定以 \(x+y\) 为循环节密铺。
考虑 \((x+y)|n\) 的情况，如果答案不是以 \(x+y\) 为循环节，我们找出其中每一段长为 \(x+y\) 中点最多的，用它密铺 \(n\) 得到一个新的答案，这个答案一定更优，因为找的是点最多的。
那么如果 \((x+y)|n\)，问题就变成找一个 \(x+y\) 的段能放最多的点。
可以状压 dp，假设 \(x>y\)。设 \(dp_{i,S}\) 表示前 \(i\) 位，后 \(x\) 位状态为 \(S\) 的最大点数。
这样转移复杂度是 \(\Theta((x+y)2^x)\) 的，能过。然后乘上一个 \(\frac n{x+y}\) 就是答案。
如果 \(x+y\) 不整除 \(n\)，也是一样的道理，答案仍然是以 \(x+y\) 为循环节。证明同理。
但是最后有一小段和整段的不一样。假设 \(k=n\bmod(x+y)\)，我们令状压转移的时候，如果放的位置 \(\le k\) 贡献为 \(\lfloor\frac n{x+y}\rfloor+1\) 否则为 \(\lfloor\frac n{x+y}\rfloor\) 即可。
复杂度 \(\Theta((x+y)2^x)\)。
B
C
一个给胸上锁的方案是合法的，当且仅当，对于所有买锁的方案，这些锁能开的胸总价值小于等于锁的价值。
也可以说，对于所有胸的集合，开这些胸所需的锁价值大于胸的价值。
如果把每个胸、锁拆成对应的价值数目的点数，即每个胸拆成 \(a_i\) 个点，锁拆成 \(b_i\) 个点，
为一个胸上锁的时候将对应拆出的点两两连边。那么这个上锁方案合法的条件，根据 Hall 定理，就是所有胸代表的左部点有完美匹配。
点数如此小的情况下，可以直接记忆化搜索求解这个匹配过程。
设 \(dp_{i,j,S}\) 表示前 \(i\) 个胸，第 \(i\) 个胸考虑到第 \(j\) 个小点，右边的每一个锁已经用的点数的压缩状态 \(S\)，的最小权值。
搜索时考虑这个胸的这个点要匹配右边的哪个锁，如果这个胸没上过这个锁代价就要加上 \(c_{i,j}\)。
因此还要记录每个锁是否被用过。可以按顺序考虑每个锁，状态中加入 \(k,vis\) 表示到了第几个锁，当前锁是否被用过。
复杂度就是状态数，大概是 \(24\times5^6\times2\times6\)。
D
典题不想写
标签：frac,shu,jia,sum,varphi,Theta,post,复杂度,dp From： https://www.cnblogs.com/iorit/p/18052665