2023.8.22 模拟赛

GloriousCc / 2023-08-23 / 原文

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\),问任意点对距离的和。