{"id":2809,"date":"2023-05-11T17:27:10","date_gmt":"2023-05-11T09:27:10","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2809"},"modified":"2023-05-11T17:31:07","modified_gmt":"2023-05-11T09:31:07","slug":"sgu-208-toral-tickets","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/sgu-208-toral-tickets\/","title":{"rendered":"SGU 208. Toral Tickets"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/codeforces.com\/problemsets\/acmsguru\/submission\/99999\/205409750\">https:\/\/codeforces.com\/problemsets\/acmsguru\/submission\/99999\/205409750<\/a><\/li>\n<li><a href=\"https:\/\/vjudge.net\/problem\/SGU-208\">https:\/\/vjudge.net\/problem\/SGU-208<\/a><\/li>\n<\/ul>\n<h2>\u9898\u610f<\/h2>\n<p>\u7ed9\u5b9a\u4e00\u4e2a n\u2217m \u7684\u5355\u9762\u65b9\u683c\u7eb8\uff0c\u7136\u540e\u628a\u65b9\u683c\u7eb8\u7684\u957f\u8fb9\u5377\u8d77\u6765\uff0c\u5377\u6210\u4e00\u4e2a\u5706\u67f1\u4f53\uff0c\u518d\u628a\u6536\u5c3e\u4e5f\u63a5\u8d77\u6765\uff0c\u5f62\u6210\u4e00\u4e2a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Torus\">torus<\/a>\u3002\u6c42\u5bf9\u683c\u70b9\u8fdb\u884c\u9ed1\u767d\u67d3\u8272\u7684\u65b9\u6848\u6570\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/6\/60\/Torus_from_rectangle.gif\" alt=\"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/6\/60\/Torus_from_rectangle.gif\" \/><\/p>\n<h2>\u5206\u6790<\/h2>\n<p>Polya \u8ba1\u6570\uff0c\u6570\u636e\u8303\u56f4\u5f88\u5c0f\uff0c\u66b4\u529b\u505a\u5faa\u73af\u5206\u89e3\u5373\u53ef\u3002<br \/>\n\u96be\u70b9\u662f\u5bf9\u4e8e n == m \u7684\u60c5\u51b5\uff0c\u8981\u8003\u8651 rt90()\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/bignum&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = 20;\r\nint a&#x5B;N]&#x5B;N], b&#x5B;N]&#x5B;N]; bool v&#x5B;N]&#x5B;N];\r\nint n, m; bignum z;\r\n\r\nint f(){\r\n\tint z = 0; RST(v);\r\n\tREP(i, n) REP(j, m) if (!v&#x5B;i]&#x5B;j]) {\r\n        int x = i, y = j;  do {\r\n            v&#x5B;x]&#x5B;y] = true;  int t = a&#x5B;x]&#x5B;y];\r\n            x = t \/ m, y = t % m;\r\n        } while (!v&#x5B;x]&#x5B;y]);\r\n        ++z;\r\n    }\r\n\treturn z;\r\n\r\n}\r\n\r\nvoid rt90(){\r\n\tCPY(b, a); REP(i, n) REP(j, m) a&#x5B;j]&#x5B;n-i-1] = b&#x5B;i]&#x5B;j];\r\n\tswap(n, m);\r\n}\r\n\r\nvoid rt180(){\r\n\trt90(); rt90();\r\n}\r\n\r\nvoid rolln(){\r\n\tCPY(b, a); REP(i, n) REP(j, m) a&#x5B;i]&#x5B;j] = b&#x5B;(i+1)%n]&#x5B;j];\r\n}\r\n\r\nvoid rollm(){\r\n\tCPY(b, a); REP(i, n) REP(j, m) a&#x5B;i]&#x5B;j] = b&#x5B;i]&#x5B;(j+1)%m];\r\n}\r\n\r\nvoid init(){\r\n\tREP(i, n) REP(j, m) a&#x5B;i]&#x5B;j] = i*m + j; z = 0;\r\n}\r\n\r\nvoid Polay(){\r\n\tif (n==m){\r\n\t\tfor (int k=0;k&lt;4;k++,rt90())\r\n\t\t\tfor (int i=0;i&lt;n;i++,rolln())\r\n\t\t\t\tfor (int j=0;j&lt;m;j++,rollm())\r\n\t\t\t\t\tz += pow(bignum(2), f());\r\n\t\tz \/= 4*n*m;\r\n\t}\r\n\telse {\r\n\t\tfor (int k=0;k&lt;2;k++,rt180())\r\n\t\t\tfor (int i=0;i&lt;n;i++,rolln())\r\n\t\t\t\tfor (int j=0;j&lt;m;j++,rollm())\r\n\t\t\t\t\tz += pow(bignum(2), f());\r\n\t\tz \/= 2*n*m;\r\n\t}\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#endif\r\n\r\n    while (scanf(&quot;%d %d&quot;, &amp;n, &amp;m) != EOF){\r\n\t\tinit(); Polay();\r\n\t\tcout &lt;&lt; z &lt;&lt; endl;\r\n\t}\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/codeforces.com\/problemsets\/acmsguru\/submission\/99999\/205409750 https:\/\/vjudge.net\/problem\/SGU-208 \u9898\u610f \u7ed9\u5b9a\u4e00\u4e2a n\u2217m \u7684\u5355\u9762\u65b9\u683c\u7eb8\uff0c\u7136\u540e\u628a\u65b9\u683c\u7eb8\u7684\u957f\u8fb9\u5377\u8d77\u6765\uff0c\u5377\u6210\u4e00\u4e2a\u5706\u67f1\u4f53\uff0c\u518d\u628a\u6536\u5c3e\u4e5f\u63a5\u8d77\u6765\uff0c\u5f62\u6210\u4e00\u4e2a torus\u3002\u6c42\u5bf9\u683c\u70b9\u8fdb\u884c\u9ed1\u767d\u67d3\u8272\u7684\u65b9\u6848\u6570\u3002 \u5206\u6790 Polya \u8ba1\u6570\uff0c\u6570\u636e\u8303\u56f4\u5f88\u5c0f\uff0c\u66b4\u529b\u505a\u5faa\u73af\u5206\u89e3\u5373\u53ef\u3002 \u96be\u70b9\u662f\u5bf9\u4e8e n == m \u7684\u60c5\u51b5\uff0c\u8981\u8003\u8651 rt90()\u3002 #include &lt;lastweapon\/bignum&gt; using namespace lastweapon; const int N = 20; int a&#x5B;N]&#x5B;N], b&#x5B;N]&#x5B;N]; bool v&#x5B;N]&#x5B;N]; int n, m; bignum z; int f(){ int z = 0; RST(v); REP(i, n) REP(j, m) if (!v&#x5B;i]&#x5B;j]) { int x = i, y [&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-2809","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-Jj","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2809","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=2809"}],"version-history":[{"count":6,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2809\/revisions"}],"predecessor-version":[{"id":2815,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2809\/revisions\/2815"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2809"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2809"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2809"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}