{"id":2045,"date":"2022-11-14T10:06:51","date_gmt":"2022-11-14T02:06:51","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2045"},"modified":"2022-12-02T22:22:54","modified_gmt":"2022-12-02T14:22:54","slug":"permutation","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/permutation\/","title":{"rendered":"Permutation"},"content":{"rendered":"<p>\u7531\u4e8e\u4e0a\u4e00\u573a G \u9898\u6ca1\u505a\u51fa\u6765\u3002\u3002\u6253\u7b97\u91cd\u65b0\u590d\u4e60\u4e00\u4e0b\u5404\u79cd\u6392\u5217\u76f8\u5173\u7684\u77e5\u8bc6\u3002\u3002\u3002<\/p>\n<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-6a1e5bf7e5a66\" 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-6a1e5bf7e5a66\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/permutation\/#%E7%AC%AC%E4%B8%80%E9%83%A8%E5%88%86\" title=\"\u7b2c\u4e00\u90e8\u5206\">\u7b2c\u4e00\u90e8\u5206<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/permutation\/#%E9%94%99%E4%BD%8D%E6%8E%92%E5%88%97%EF%BC%88%EF%BC%89\" title=\"\u9519\u4f4d\u6392\u5217\uff08\uff09\">\u9519\u4f4d\u6392\u5217\uff08\uff09<\/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\/permutation\/#%E8%87%AA%E5%8F%8D%E6%8E%92%E5%88%97\" title=\"\u81ea\u53cd\u6392\u5217\">\u81ea\u53cd\u6392\u5217<\/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\/permutation\/#%E4%BA%A4%E9%94%99%E6%8E%92%E5%88%97\" title=\"\u4ea4\u9519\u6392\u5217\">\u4ea4\u9519\u6392\u5217<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/permutation\/#%E7%B1%BB_Catalan_%E9%80%92%E6%8E%A8%E5%85%AC%E5%BC%8F\" title=\"\u7c7b Catalan \u9012\u63a8\u516c\u5f0f\">\u7c7b Catalan \u9012\u63a8\u516c\u5f0f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/permutation\/#%E7%B1%BB_Pascal_%E9%80%92%E6%8E%A8%E5%85%AC%E5%BC%8F\" title=\"\u7c7b Pascal \u9012\u63a8\u516c\u5f0f\">\u7c7b Pascal \u9012\u63a8\u516c\u5f0f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/permutation\/#%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0\" title=\"\u751f\u6210\u51fd\u6570\">\u751f\u6210\u51fd\u6570<\/a><\/li><\/ul><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/permutation\/#%E7%AC%AC%E4%BA%8C%E9%83%A8%E5%88%86\" title=\"\u7b2c\u4e8c\u90e8\u5206\">\u7b2c\u4e8c\u90e8\u5206<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/www.shuizilong.com\/house\/archives\/permutation\/#%E5%BE%AA%E7%8E%AF%E5%88%86%E8%A7%A3\" title=\"\u5faa\u73af\u5206\u89e3\">\u5faa\u73af\u5206\u89e3<\/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\/permutation\/#%E4%B8%8D%E5%8A%A8%E7%82%B9\" title=\"\u4e0d\u52a8\u70b9\">\u4e0d\u52a8\u70b9<\/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\/permutation\/#%E9%80%86%E5%BA%8F%E5%AF%B9\" title=\"\u9006\u5e8f\u5bf9\">\u9006\u5e8f\u5bf9<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n\n<ul>\n<li>Combinatorial Problems and Exercises, 2nd Edition, L\u00e1szl\u00f3 Lov\u00e1sz, #3 Permutations<\/li>\n<li>The Art of Computer Programming, Vol. 3 Sorting and Searching, 2nd Edition, Donald E. Knuth, 5.1. Combinatorial Properties of Permutations<\/li>\n<\/ul>\n<h1><span class=\"ez-toc-section\" id=\"%E7%AC%AC%E4%B8%80%E9%83%A8%E5%88%86\"><\/span>\u7b2c\u4e00\u90e8\u5206<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<h2><span class=\"ez-toc-section\" id=\"%E9%94%99%E4%BD%8D%E6%8E%92%E5%88%97%EF%BC%88%EF%BC%89\"><\/span>\u9519\u4f4d\u6392\u5217\uff08\uff09<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<ul>\n<li><a href=\"\"><\/a><\/li>\n<\/ul>\n<h2><span class=\"ez-toc-section\" id=\"%E8%87%AA%E5%8F%8D%E6%8E%92%E5%88%97\"><\/span>\u81ea\u53cd\u6392\u5217<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<ul>\n<li><a href=\"https:\/\/mathworld.wolfram.com\/PermutationInvolution.html\">https:\/\/mathworld.wolfram.com\/PermutationInvolution.html<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Involution_(mathematics)\">https:\/\/en.wikipedia.org\/wiki\/Involution_(mathematics)<\/a><\/li>\n<\/ul>\n<h2><span class=\"ez-toc-section\" id=\"%E4%BA%A4%E9%94%99%E6%8E%92%E5%88%97\"><\/span>\u4ea4\u9519\u6392\u5217<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<ul>\n<li><a href=\"http:\/\/oeis.org\/A000111\">http:\/\/oeis.org\/A000111<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Euler_numbers\">https:\/\/en.wikipedia.org\/wiki\/Euler_numbers<\/a><\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"%E7%B1%BB_Catalan_%E9%80%92%E6%8E%A8%E5%85%AC%E5%BC%8F\"><\/span>\u7c7b Catalan \u9012\u63a8\u516c\u5f0f<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<h3><span class=\"ez-toc-section\" id=\"%E7%B1%BB_Pascal_%E9%80%92%E6%8E%A8%E5%85%AC%E5%BC%8F\"><\/span>\u7c7b Pascal \u9012\u63a8\u516c\u5f0f<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<h3><span class=\"ez-toc-section\" id=\"%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0\"><\/span>\u751f\u6210\u51fd\u6570<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li><a href=\"http:\/\/oeis.org\/A008282\">http:\/\/oeis.org\/A008282<\/a><\/li>\n<\/ul>\n<h1><span class=\"ez-toc-section\" id=\"%E7%AC%AC%E4%BA%8C%E9%83%A8%E5%88%86\"><\/span>\u7b2c\u4e8c\u90e8\u5206<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<h2><span class=\"ez-toc-section\" id=\"%E5%BE%AA%E7%8E%AF%E5%88%86%E8%A7%A3\"><\/span>\u5faa\u73af\u5206\u89e3<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<ul>\n<li><a href=\"https:\/\/www.shuizilong.com\/house\/archives\/my_problems\/\">https:\/\/www.shuizilong.com\/house\/archives\/my_problems\/<\/a><\/li>\n<\/ul>\n<h2><span class=\"ez-toc-section\" id=\"%E4%B8%8D%E5%8A%A8%E7%82%B9\"><\/span>\u4e0d\u52a8\u70b9<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<h2><span class=\"ez-toc-section\" id=\"%E9%80%86%E5%BA%8F%E5%AF%B9\"><\/span>\u9006\u5e8f\u5bf9<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\n#include &lt;lastweapon\/number&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(1e3) + 9;\r\n\r\nint a&#x5B;N], mx&#x5B;N], mn&#x5B;N], cc&#x5B;N];\r\nint n;\r\n\r\nVI circle() {\r\n    bool static used&#x5B;N]; RST(used);\r\n    VI z;\r\n    REP(i, n) if (!used&#x5B;i]) {\r\n        int x = i; used&#x5B;x] = true; int c = 1;\r\n        while (!used&#x5B;a&#x5B;x]-1]) {\r\n            x = a&#x5B;x]-1;\r\n            used&#x5B;x] = true;\r\n            ++c;\r\n        }\r\n        z.PB(c);\r\n    }\r\n    return z;\r\n}\r\n\r\n\r\nbool used&#x5B;N];\r\n\r\nvoid dfs(int k = 0) {\r\n\r\n    if (k == n) {\r\n        \/\/REP(i, n) cout &lt;&lt; a&#x5B;i] &lt;&lt; &quot; &quot;; cout &lt;&lt; endl;\r\n        VI r = circle();\r\n        ++mx&#x5B;*max_element(ALL(r))];\r\n        ++mn&#x5B;*min_element(ALL(r))];\r\n        ++cc&#x5B;SZ(r)];\r\n    } else {\r\n        REP_1(i, n) if (!used&#x5B;i]) {\r\n            used&#x5B;a&#x5B;k] = i] = true;\r\n            dfs(k+1);\r\n            used&#x5B;i] = false;\r\n        }\r\n    }\r\n}\r\n\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    \/\/freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n\t\/\/scanf(&quot;%d%d&quot;,&amp;n,&amp;MOD);\r\n\tREP_1(i, 10) {\r\n        \/\/RD(n);\r\n\r\n        RST(used); RST(mn); RST(mx); RST(cc);\r\n        n = i; dfs();\r\n        \/\/REP_1(i, n) cout &lt;&lt; mx&#x5B;i] &lt;&lt;&quot; &quot;; cout &lt;&lt; endl;\r\n        \/\/REP_1(i, n) cout &lt;&lt; mn&#x5B;i] &lt;&lt;&quot; &quot;; cout &lt;&lt; endl;\r\n        REP_1(i, n) cout &lt;&lt; cc&#x5B;i] &lt;&lt;&quot; &quot;; cout &lt;&lt; endl;\r\n\t}\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u7531\u4e8e\u4e0a\u4e00\u573a G \u9898\u6ca1\u505a\u51fa\u6765\u3002\u3002\u6253\u7b97\u91cd\u65b0\u590d\u4e60\u4e00\u4e0b\u5404\u79cd\u6392\u5217\u76f8\u5173\u7684\u77e5\u8bc6\u3002\u3002\u3002 Combinatorial Problems and Exercises, 2nd Edition, L\u00e1szl\u00f3 Lov\u00e1sz, #3 Permutations The Art of Computer Programming, Vol. 3 Sorting and Searching, 2nd Edition, Donald E. Knuth, 5.1. Combinatorial Properties of Permutations \u7b2c\u4e00\u90e8\u5206 \u9519\u4f4d\u6392\u5217\uff08\uff09 \u81ea\u53cd\u6392\u5217 https:\/\/mathworld.wolfram.com\/PermutationInvolution.html https:\/\/en.wikipedia.org\/wiki\/Involution_(mathematics) \u4ea4\u9519\u6392\u5217 http:\/\/oeis.org\/A000111 https:\/\/en.wikipedia.org\/wiki\/Euler_numbers \u7c7b Catalan \u9012\u63a8\u516c\u5f0f \u7c7b Pascal \u9012\u63a8\u516c\u5f0f \u751f\u6210\u51fd\u6570 http:\/\/oeis.org\/A008282 \u7b2c\u4e8c\u90e8\u5206 \u5faa\u73af\u5206\u89e3 https:\/\/www.shuizilong.com\/house\/archives\/my_problems\/ \u4e0d\u52a8\u70b9 \u9006\u5e8f\u5bf9 #include [&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-2045","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-wZ","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2045","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=2045"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2045\/revisions"}],"predecessor-version":[{"id":2056,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2045\/revisions\/2056"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2045"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2045"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2045"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}