Skip to content

20261005G Yelkrab 笔记 ​

给定 n 个字符串,f(i,j) 表示前 i 个字符串每 j 个一组(允许有剩余字符串),每组的最长公共前缀长度和,对于每个 i 求

⨁j=1ij×f(i,j)

n,|S|≤106

最长公共前缀考虑字典树,由于同一组的字符串对 f 的贡献是最长公共前缀长度,因此转换为从根到最长公共前缀位置,每一个点都有 1 的贡献。

于是 f(i,j)=∑u∈字典树cu/j,当 i 变大时每个 cu 最多增加 1,若有 f(i,j) 变化说明 j∣cu,枚举 cu 的因数修改即可。

最近更新