CF1051C Vasya and Big Integers 题解

Problem - 1051E - Codeforces

Vasya and Big Integers - 洛谷

• 感谢女队提交记录推荐给我的一道题 \(Orz\)

• 首先 \(O(n^2)\) 的 \(dp\) 是 simple 的，如果你没看出来你可能是像我一样把题目看错了

• 设 \(dp_i\) 表示考虑前 \(i\) 个的方案数，转移枚举长度后比较字典序。虽然看起来是 \(O(n^3)\) 的，但长度不相等的可以直接 \(O(1)\) 判断

• 一个重要的性质：比较字符串 \(a,b\) 字典序等价于比较 \(a_{lcp(a,b)+1},b_{lcp(a,b)+1}\)

• 求 \(LCP\)？

  1. 哈希+二分

  2. \(ExKMP\)

• 复杂度 \(O(n \log n)\) 或 \(O(n)\)

• 综上，女队 \(tql\)