{"id":1773,"date":"2021-09-22T20:33:37","date_gmt":"2021-09-22T12:33:37","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1773"},"modified":"2022-08-01T23:59:51","modified_gmt":"2022-08-01T15:59:51","slug":"note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/","title":{"rendered":"Note on \u591a\u9879\u5f0f"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69f48fb28619b\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69f48fb28619b\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E9%A2%98%E5%8D%95\" title=\"\u9898\u5355\">\u9898\u5355<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E5%AD%97%E5%85%B8\" title=\"\u5b57\u5178\">\u5b57\u5178<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98\" title=\"\u80cc\u5305\u95ee\u9898\">\u80cc\u5305\u95ee\u9898<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E9%AA%A8%E7%89%8C%E9%97%AE%E9%A2%98\" title=\"\u9aa8\u724c\u95ee\u9898\">\u9aa8\u724c\u95ee\u9898<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E7%90%83%E7%9B%92%E9%97%AE%E9%A2%98\" title=\"\u7403\u76d2\u95ee\u9898\">\u7403\u76d2\u95ee\u9898<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E8%87%AA%E7%84%B6%E6%95%B0%E5%B9%82%E5%92%8C%E3%80%81%E4%BC%AF%E5%8A%AA%E5%88%A9%E6%95%B0\" title=\"\u81ea\u7136\u6570\u5e42\u548c\u3001\u4f2f\u52aa\u5229\u6570\">\u81ea\u7136\u6570\u5e42\u548c\u3001\u4f2f\u52aa\u5229\u6570<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E5%B7%AE%E5%88%86%E3%80%81%E5%89%8D%E7%BC%80%E5%92%8C\" title=\"\u5dee\u5206\u3001\u524d\u7f00\u548c\">\u5dee\u5206\u3001\u524d\u7f00\u548c<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E6%8B%86%E5%88%86%E6%95%B0\" title=\"\u62c6\u5206\u6570\">\u62c6\u5206\u6570<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E6%8A%BD%E5%8D%A1\" title=\"\u62bd\u5361\">\u62bd\u5361<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E5%9B%BE%E8%AE%BA%E8%AE%A1%E6%95%B0\" title=\"\u56fe\u8bba\u8ba1\u6570\">\u56fe\u8bba\u8ba1\u6570<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/note-on-%e5%a4%9a%e9%a1%b9%e5%bc%8f\/#%E7%BB%BC%E5%90%88%E9%A2%98\" title=\"\u7efc\u5408\u9898\">\u7efc\u5408\u9898<\/a><\/li><\/ul><\/nav><\/div>\n\n<ul>\n<li><a href=\"https:\/\/codeforces.com\/contest\/438\/submission\/120324931\">Codeforces, hos.lyric \u7684\u591a\u9879\u5f0f\u6a21\u677f<\/a><\/li>\n<li><a href=\"https:\/\/github.com\/hos-lyric\/libra\/tree\/master\/algebra\">Github, hos.lyric \u7684\u591a\u9879\u5f0f\u6a21\u677f<\/a><\/li>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/solution\/P5488\">NaCly_Fish, \u5b66\u4e60\u7b14\u8bb0\uff1a\u591a\u9879\u5f0f\u5168\u5bb6\u6876<\/a><\/li>\n<\/ul>\n<h2><span class=\"ez-toc-section\" id=\"%E9%A2%98%E5%8D%95\"><\/span>\u9898\u5355<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/training\/1008\">\u83dc\u9e21 Karry5307 \u7684\u591a\u9879\u5f0f\u9898\u5355<\/a><\/li>\n<li><a href=\"https:\/\/www.luogu.com.cn\/user\/530741#practice\">Lyric \u7684 Luogu \u5207\u9898\u8bb0\u5f55<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.luogu.com.cn\/problem\/P3706\">P3706 [SDOI2017]\u786c\u5e01\u6e38\u620f<\/a> \u6982\u7387\u751f\u6210\u51fd\u6570<\/p>\n<\/li>\n<\/ul>\n<h2><span class=\"ez-toc-section\" id=\"%E5%AD%97%E5%85%B8\"><\/span>\u5b57\u5178<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>DFT\uff1a\u79bb\u6563\u5085\u91cc\u53f6\u53d8\u6362<br \/>\nIDFT\uff1a\u79bb\u6563\u5085\u91cc\u53f6\u9006\u53d8\u6362<br \/>\nFFT\uff1aA fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT).<br \/>\nNTT\uff1a\u5feb\u901f\u6570\u8bba\u53d8\u6362<br \/>\nMTT\uff1a\u5feb\u901f\u6bdb\u7237\u7237\u53d8\u6362\uff0c\u6bdb\u7237\u7237\u5bf9 FFT \u7684\u6539\u8fdb\u4ee5\u89e3\u51b3\u4efb\u610f\u6a21\u6570<br \/>\nFWT\uff1a\u5feb\u901f\u6c83\u5c14\u4ec0\u53d8\u6362<br \/>\nFMT\uff1a\u5feb\u901f\u83ab\u6bd4\u4e4c\u65af\u53d8\u6362<\/p>\n<h2><span class=\"ez-toc-section\" id=\"%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98\"><\/span>\u80cc\u5305\u95ee\u9898<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P4389\">Luogu P4389 \u4ed8\u516c\u4e3b\u7684\u80cc\u5305<\/a><\/li>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P5339\">https:\/\/www.luogu.com.cn\/problem\/P5339<\/a><\/li>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P3784\">Luogu P3784 [SDOI2017] \u9057\u5fd8\u7684\u96c6\u5408<\/a> \u6839\u636e\u65b9\u6848\u6570\u7ed3\u679c\u53cd\u63a8\u96c6\u5408\u4e2d\u7684\u5143\u7d20\u3002<\/li>\n<li><a href=\"https:\/\/atcoder.jp\/contests\/arc145\/editorial\/4528\">https:\/\/atcoder.jp\/contests\/arc145\/editorial\/4528<\/a><\/li>\n<\/ul>\n<h2><span class=\"ez-toc-section\" id=\"%E9%AA%A8%E7%89%8C%E9%97%AE%E9%A2%98\"><\/span>\u9aa8\u724c\u95ee\u9898<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><a href=\"https:\/\/www.luogu.com.cn\/problem\/P5320\">https:\/\/www.luogu.com.cn\/problem\/P5320<\/a><\/p>\n<h2><span class=\"ez-toc-section\" id=\"%E7%90%83%E7%9B%92%E9%97%AE%E9%A2%98\"><\/span>\u7403\u76d2\u95ee\u9898<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><a href=\"https:\/\/www.luogu.com.cn\/problem\/solution\/P5162\">https:\/\/www.luogu.com.cn\/problem\/solution\/P5162<\/a><br \/>\n<a href=\"https:\/\/www.luogu.com.cn\/problem\/P5824\">https:\/\/www.luogu.com.cn\/problem\/P5824<\/a><br \/>\n<a href=\"https:\/\/www.luogu.com.cn\/problem\/P2791\">https:\/\/www.luogu.com.cn\/problem\/P2791<\/a><\/p>\n<h2><span class=\"ez-toc-section\" id=\"%E8%87%AA%E7%84%B6%E6%95%B0%E5%B9%82%E5%92%8C%E3%80%81%E4%BC%AF%E5%8A%AA%E5%88%A9%E6%95%B0\"><\/span>\u81ea\u7136\u6570\u5e42\u548c\u3001\u4f2f\u52aa\u5229\u6570<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><a href=\"https:\/\/www.luogu.com.cn\/problem\/P7102\">Luogu P7102 [W1] \u7b97<\/a><\/p>\n<h2><span class=\"ez-toc-section\" id=\"%E5%B7%AE%E5%88%86%E3%80%81%E5%89%8D%E7%BC%80%E5%92%8C\"><\/span>\u5dee\u5206\u3001\u524d\u7f00\u548c<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><a href=\"https:\/\/www.luogu.com.cn\/problem\/P5488\">Luogu P5488 \u5dee\u5206\u4e0e\u524d\u7f00\u548c<\/a><\/p>\n<h2><span class=\"ez-toc-section\" id=\"%E6%8B%86%E5%88%86%E6%95%B0\"><\/span>\u62c6\u5206\u6570<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<ul>\n<li><a href=\"http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=4651\">http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=4651<\/a><\/li>\n<li><a href=\"https:\/\/acm.hdu.edu.cn\/showproblem.php?pid=4658\">https:\/\/acm.hdu.edu.cn\/showproblem.php?pid=4658<\/a><\/li>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/solution\/P6189\">https:\/\/www.luogu.com.cn\/problem\/solution\/P6189<\/a><\/li>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P4451\">https:\/\/www.luogu.com.cn\/problem\/P4451<\/a><\/li>\n<\/ul>\n<h2><span class=\"ez-toc-section\" id=\"%E6%8A%BD%E5%8D%A1\"><\/span>\u62bd\u5361<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Coupon_collector%27s_problem\">Wikipedia, Coupon collector&#8217;s problem<\/a><br \/>\n<a href=\"https:\/\/www.luogu.com.cn\/problem\/P6633\">Luogu P6633 [ZJOI2020] \u62bd\u5361<\/a><\/p>\n<h2><span class=\"ez-toc-section\" id=\"%E5%9B%BE%E8%AE%BA%E8%AE%A1%E6%95%B0\"><\/span>\u56fe\u8bba\u8ba1\u6570<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><a href=\"https:\/\/www.shuizilong.com\/house\/archives\/graphical-enumeration\/\">https:\/\/www.shuizilong.com\/house\/archives\/graphical-enumeration\/<\/a><\/p>\n<h2><span class=\"ez-toc-section\" id=\"%E7%BB%BC%E5%90%88%E9%A2%98\"><\/span>\u7efc\u5408\u9898<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<ul>\n<li><a href=\"https:\/\/atcoder.jp\/contests\/abc260\/tasks\/abc260_h\">https:\/\/atcoder.jp\/contests\/abc260\/tasks\/abc260_h<\/a><\/li>\n<li><a href=\"https:\/\/codeforces.ml\/contest\/1580\/problem\/F\">Codeforces Round #745 (Div. 1) F. Problems for Codeforces<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Codeforces, hos.lyric \u7684\u591a\u9879\u5f0f\u6a21\u677f Github, hos.lyric \u7684\u591a\u9879\u5f0f\u6a21\u677f NaCly_Fish, \u5b66\u4e60\u7b14\u8bb0\uff1a\u591a\u9879\u5f0f\u5168\u5bb6\u6876 \u9898\u5355 \u83dc\u9e21 Karry5307 \u7684\u591a\u9879\u5f0f\u9898\u5355 Lyric \u7684 Luogu \u5207\u9898\u8bb0\u5f55 P3706 [SDOI2017]\u786c\u5e01\u6e38\u620f \u6982\u7387\u751f\u6210\u51fd\u6570 \u5b57\u5178 DFT\uff1a\u79bb\u6563\u5085\u91cc\u53f6\u53d8\u6362 IDFT\uff1a\u79bb\u6563\u5085\u91cc\u53f6\u9006\u53d8\u6362 FFT\uff1aA fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). NTT\uff1a\u5feb\u901f\u6570\u8bba\u53d8\u6362 MTT\uff1a\u5feb\u901f\u6bdb\u7237\u7237\u53d8\u6362\uff0c\u6bdb\u7237\u7237\u5bf9 FFT \u7684\u6539\u8fdb\u4ee5\u89e3\u51b3\u4efb\u610f\u6a21\u6570 FWT\uff1a\u5feb\u901f\u6c83\u5c14\u4ec0\u53d8\u6362 FMT\uff1a\u5feb\u901f\u83ab\u6bd4\u4e4c\u65af\u53d8\u6362 \u80cc\u5305\u95ee\u9898 Luogu P4389 \u4ed8\u516c\u4e3b\u7684\u80cc\u5305 https:\/\/www.luogu.com.cn\/problem\/P5339 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-1773","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-sB","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1773","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1773"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1773\/revisions"}],"predecessor-version":[{"id":1774,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1773\/revisions\/1774"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1773"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1773"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1773"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}