【BZOJ 4259】残缺的字符串

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4259
神犇题解:http://blog.csdn.net/u011542204/article/details/50708834

解题报告

考虑之前的那个DNA的匹配问题
这题似乎也可以做,只是复杂度会乘上一个26
于是考虑优化:
将简单的0/1的多项式变成这个东西: $\sum\limits_{i = 1}^n {{{({a_i} – {b_i})}^2} \cdot {a_i} \cdot {b_i}} $
或者你要展开成这个样子也可以: $\sum {a_i^2[{b_i} \ne 0] – 2\sum {{a_i}{b_i} + \sum {b_i^2[{a_i} \ne 0]} } } $
于是我们发现搞个几次FFT什么的就可以辣!
另外这题在BZOJ上还有双倍经验:http://www.lydsy.com/JudgeOnline/problem.php?id=4503

话说这题之前听鏼爷讲过,但又忘了怎么做了
这个记忆力,真是简直了

发表评论

电子邮件地址不会被公开。 必填项已用*标注