{"html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fbostan_mori_advanced\" title=\"Bostan\u2013Mori \u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\uff08\u767a\u5c55\uff09 - AtCoderInfo\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","author_name":"atcoder","published":"2026-06-05 10:37:13","title":"Bostan\u2013Mori \u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\uff08\u767a\u5c55\uff09","height":"190","categories":["\u591a\u9805\u5f0f\u30fb\u5f62\u5f0f\u7684\u3079\u304d\u7d1a\u6570","\u7dda\u5f62\u6f38\u5316\u7684\u6570\u5217","C-recursive","Fiduccia \u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0","Bostan\u2013Mori \u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0","\u8ee2\u7f6e\u539f\u7406","FFT"],"blog_title":"AtCoderInfo","type":"rich","provider_url":"https://hatena.blog","blog_url":"https://info.atcoder.jp/","version":"1.0","image_url":null,"author_url":"https://blog.hatena.ne.jp/atcoder/","width":"100%","provider_name":"Hatena Blog","url":"https://info.atcoder.jp/entry/algorithm_lectures/bostan_mori_advanced","description":"1. \u6982\u8981 \u672c\u8b1b\u5ea7\u3067\u306f\uff0cBostan\u2013Mori \u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u95a2\u3059\u308b\u767a\u5c55\u7684\u306a\u8a71\u984c\u3092\u6271\u3044\u307e\u3059\uff0e \u524d\u56de\u306e\u8b1b\u5ea7 \u7dda\u5f62\u6f38\u5316\u7684\u6570\u5217\u306e\u7b2c K \u9805 \u3067\u306f\uff0c\u7dda\u5f62\u6f38\u5316\u7684\u6570\u5217\u306e\u7b2c $K$ \u9805\u3092\u9ad8\u901f\u306b\u6c42\u3081\u308b\u65b9\u6cd5\u3068\u3057\u3066\uff0cFiduccia \u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068 Bostan\u2013Mori \u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u89e3\u8aac\u3057\u307e\u3057\u305f\uff0e\u672c\u8b1b\u5ea7\u3067\u306f\u3053\u306e\u3046\u3061 Bostan\u2013Mori \u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\uff0c\u3088\u308a\u767a\u5c55\u7684\u306a\u8a71\u984c\u3092\u53d6\u308a\u4e0a\u3052\u307e\u3059\uff0e \u672c\u8b1b\u5ea7\u306e\u524d\u534a\u3067\u306f\uff0c\u6b21\u306e\u3088\u3046\u306a\u554f\u984c\u3092\u7d71\u4e00\u7684\u306b\u89e3\u3051\u308b\u3053\u3068\u3092\u78ba\u8a8d\u3057\u307e\u3059\uff0e \u6709\u7406\u5f0f\u8868\u793a\u3055\u308c\u305f\u5f62\u5f0f\u7684\u3079\u304d\u7d1a\u6570\u306e\u9023\u7d9a\u3059\u308b\u4fc2\u6570 $A_L, A_{L+1},\\ldots, A_R$ \u3092\u6c42\u3081\u308b\uff0e \u6570\u5217\u3092 $K$ \u9805\u3060\u3051\u305a\u3089\u3057\u305f\u2026"}