2023.8.22 模拟赛

A

BFS

B

一个长 \(n(n\le 1e5)\) 的字符串 \(S\)，长 \(m(m\le 30)\) 的字符串 \(T\)，
\(S\) 的每个位置有权值 \(a_i\)。
\(q(q\le 1e5)\) 次询问 \(l,r\)，
求 \(T\) 作为一个子序列出现在 \(S(l,r)\) 中的所有方案中，\(T\) 出现的位置的权值和。

先考虑 \(a_i=1\)。显然有 \(f_{i,j}=f_{i-1,j}+[S_i=T_j]f_{i-1,j-1}\).
考虑使用矩阵。
有 \([f_{i-1,0},f_{i-1,1},...,f_{i-1,m}]\times A =[f_{i,0},f_{i,1},...,f_{i,m}]\)
对于 \(\forall j,A_{j,j}=1,A_{j-1,j}=[S_i=T_j]\)。
考虑维护区间的乘积即可，一个想法是直接线段树，然而这是不优的。
考虑前缀积和前缀积的逆。
这道题还未完成，但剩余超出笔者能力。

C

仙人掌上的“负载平衡问题”。
首先考虑树，在考虑环，最后合起来即可。

D

有一棵树 \((n\le 10^{10})\)，\(i\) 的父亲是 \(i/d(i)\)，其中 \(d(i)\) 是 \(i\) 最小质因子，距离为 \(1\)，问任意点对距离的和。