Teek is Loading...
主题
给定 n 个字符串,f(i,j) 表示前 i 个字符串每 j 个一组(允许有剩余字符串),每组的最长公共前缀长度和,对于每个 i 求⨁j=1ij×f(i,j)n,|S|≤106
给定 n 个字符串,f(i,j) 表示前 i 个字符串每 j 个一组(允许有剩余字符串),每组的最长公共前缀长度和,对于每个 i 求
n,|S|≤106
最长公共前缀考虑字典树,由于同一组的字符串对 f 的贡献是最长公共前缀长度,因此转换为从根到最长公共前缀位置,每一个点都有 1 的贡献。
于是 字典树f(i,j)=∑u∈字典树cu/j,当 i 变大时每个 cu 最多增加 1,若有 f(i,j) 变化说明 j∣cu,枚举 cu 的因数修改即可。