记符号 \(\circledast\) 表示自己做出来的，\(\circleddash\) 表示贺的。
紫色表示紫色，黑色表示黑色。
P5176 公约数 \(\circledast\)
Description
\[\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p\gcd(ij,ik,jk)\cdot\gcd(i,j,k)\cdot\dfrac{\gcd(i,j)^2+\gcd(j,k)^2+\gcd(i,k)^2}{\gcd(i,j)\cdot\gcd(j,k)\cdot\gcd(i,k)}\\ n,m,p\leq2\cdot10^7 \]Solution
不知道怎么评上黑的。
发现 \(\gcd(ij,ik,jk)\) 很丑陋。我们知道 \(\gcd\) 的本质是质因数的指数取 \(\min\)，那么这个就是
\[\newcommand\I{c_i} \newcommand\J{c_j} \newcommand\K{c_k} \begin{aligned} &\min(\I+\J,\I+\K,\J+\K)\\ =~&\I+\J+\K-\max(\I,\J,\K)\\ =~&\I+\J+\K-(\min(\I,\J,\K)-\min(\I,\J)-\min(\I,\K)-\min(\J,\K)+\I+\J+\K)\\ =~&\min(\I,\J)+\min(\I,\K)+\min(\J,\K)-\min(\I,\J,\K)\\ \to&\gcd(i,j)\cdot\gcd(i,k)\cdot\gcd(j,k)/\gcd(i,j,k) \end{aligned} \]。一通约分，原式变为
\[\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p\gcd(i,j)^2+\gcd(j,k)^2+\gcd(i,k)^2\\ F(n,m):=\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^2\\ \to p\cdot F(n,m)+m\cdot F(n,p)+n\cdot F(m,p) \]求 \(F\) 就是机械的 Möbius 反演。直接跳到结果是
\[\sum_{x=1}^n\left\lfloor\frac nx\right\rfloor\left\lfloor\frac mx\right\rfloor\sum_{d\mid x}d^2\mu(x/d)\\ f(x):=\sum_{d\mid x}d^2\mu(x/d)\\ f(p^k)=p^{2k}-p^{2k-2} \]于是线性筛，然后数论分块。
P4965 薇尔莉特的打字机 \(\purple\circledast\)
Description
有个字符串，接下来要往后打字或退格若干次，但是每次操作都可能失灵，求有多少可能的最终字符串。
串长、操作数 \(5\cdot10^6\)。
Solution
先考虑没有删除。那么这个时候原串没用。
建一个字典树，一开始只有根。一次打字如果不失灵就相当于把当前串往字典树对应字母儿子跳，否则就是留在原地。
那么一次打字就会让所有可能当前串节点往该字母方向复制一份，并均成为可能当前串。（说不明白，语文太差。）
可以发现只这么扩展的话整棵树上每个节点都是可能当前串。
我们只关心每次打字之后字典树大小的变化量。考虑记 \(dp_c\) 表示有 \(c\) 这个儿子的节点有多少个。它们不会在打字 \(c\) 时产生贡献。再记录一个字典树总大小就能很好地状态转移了。
然后删除怎么做？发现删除就是向父亲复制一份。那么只有根节点有影响。状态转移一样很简单。注意原串删空了就没法接着删了。
标签：跳题,gcd,min,cdot,sum,打字,记录簿,随机,字典 From： https://www.cnblogs.com/hagasei/p/18115607