【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

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

14 thoughts to “【BZOJ 4259】残缺的字符串”

  1. 980926 190722Hi there! Someone in my Myspace group shared this site with us so I came to give it a look. Im surely loving the info. Im bookmarking and will be tweeting this to my followers! Outstanding weblog and amazing style and style. 127911

  2. 324627 66694The electronic cigarette uses a battery and a small heating component the vaporize the e-liquid. This vapor can then be inhaled and exhaled 184780

  3. 943384 539901I typically cant discover it in me to care enough to leaves a comment for articles on the internet but this was really pretty good, thanks and maintain it up, Ill check back once again 723501

  4. 500164 513269So, is this just for males, just for females, or is it for both sexes If it s not, then do girls need to do anything different to put on muscle 262759

  5. 664726 233952Id ought to talk to you here. Which is not some thing Which i do! I like reading an article that can make people believe. Also, thank you for permitting me to comment! 22302

  6. Hey there, You’ve performed a fantastic job. I’ll definitely digg it and in my view suggest to my friends. I’m sure they’ll be benefited from this site.

Leave a Reply

Your email address will not be published. Required fields are marked *