{"id":1070,"date":"2014-11-07T09:24:14","date_gmt":"2014-11-07T01:24:14","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1070"},"modified":"2015-02-17T00:31:40","modified_gmt":"2015-02-16T16:31:40","slug":"hdu-2481-toy","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/hdu-2481-toy\/","title":{"rendered":"HDU 2481. Toy"},"content":{"rendered":"<h3>Brief description: <\/h3>\n<p>\u5916\u9762\u6709\u4e00\u5708 n \u4e2a\u7ed3\u70b9\uff0c\u4e2d\u5fc3\u6709\u4e00\u4e2a\u7ed3\u70b9\u4e0e n \u4e2a\u7ed3\u70b9\u90fd\u76f8\u8fde\uff0c\u95ee\u8fd9\u4e2a\u5171 2n \u6761\u8fb9\u7684\u8f6e\u72b6\u56fe\u7684\u751f\u6210\u6811\u7684\u65b9\u6848\u6570\u3002<br \/>\n\u65cb\u8f6c\u76f8\u540c\u89c6\u4e3a\u7b49\u4ef7\u3002<\/p>\n<p><!--more--><\/p>\n<h3>Analysis:<\/h3>\n<h5>Burnside \u5f15\u7406\uff1a<\/h5>\n<p>\u76f8\u5f53\u4e8e\u67d3\u8272\u6709\u9650\u5236\u3002\u3002\u56e0\u6b64\u53ea\u80fd\u9000\u5230 <code>Burnside \u5f15\u7406<\/code>\u3002\u3002\u3002\u3002\u3002<\/p>\n<p>\u56de\u5fc6 <a href=\"https:\/\/www.shuizilong.com\/house\/archives\/poj-2154-color\/\">POJ 2154. color<\/a> \u4e2d\u7684\u65b9\u6cd5\u3002\u3002<\/p>\n<p>\uff08\u7f6e\u6362 $$\\rho_i$$ \u7684\u5faa\u73af\u6570\u4e3a gcd(i, n)\uff09<br \/>\n\uff08gcd(i, n) == d \u7684\u7f6e\u6362\u3002\u3002\u6709 phi(n\/d) \u79cd\u3002\u3002\uff09<\/p>\n<p>\u4e3a\u4e86\u4f7f\u5f97\u7ecf\u8fc7\u7f6e\u6362\u540e\u7684\u67d3\u8272\u4e0d\u53d8\u3002\u3002\u5fc5\u987b\u6bcf\u4e2a\u5faa\u73af\u4e2d\u7684\u67d3\u8272\u65b9\u5f0f\u76f8\u540c\u3002\u3002\u3002\u3002<br \/>\n\u4e5f\u5c31\u662f\u76f8\u5f53\u4e8e\u6c42 T(d)\u3002\u3002\u3002\u8fd9\u91cc\u7684 T() \u8868\u793a\uff0c\u4e0d\u8003\u8651\u65cb\u8f6c\u65f6\u7684\u65b9\u6848\u6570\u3002\u3002<br \/>\n\u8fd9\u6837\u6211\u4eec\u5c31\u6210\u529f\u7684\u628a\u95ee\u9898\u8f6c\u6362\u4e3a\u4e86\u6c42\u4e0d\u8003\u8651\u65cb\u8f6c\u65f6\u7684\u65b9\u6848\u6570\u3002<\/p>\n<h5>\u4e0d\u8003\u8651\u65cb\u8f6c\uff1a<\/h5>\n<p>\u4efb\u610f\u53d6\u4e24\u4e2a\u7ed3\u70b9\u8ba8\u8bba a, b\u3002\u90a3\u4e48\u603b\u6570\u4fbf\u662f a, b \u65ad\u5f00\u7684\u79cd\u6570\u4e0e a, b \u8fde\u5728\u4e00\u8d77\u7684\u79cd\u6570\u7684\u548c\u3002<br \/>\nf(n) \u8868\u793a\u5916\u5708\u6709 n \u4e2a\u7ed3\u70b9\u65f6\uff0c\u800c a, b \u662f\u65ad\u5f00\u7684\u79cd\u6570\u3002<br \/>\ng(n) \u8868\u793a\u5916\u5708\u6709 n \u4e2a\u7ed3\u70b9\u65f6\uff0c\u800c a, b \u662f\u8fde\u5728\u4e00\u8d77\u7684\u79cd\u6570\u3002<\/p>\n<p>\u90a3\u4e48\u6709 T(n) = f(n) + g(n)<\/p>\n<p>$$!f_n = \\sum_{i=0}^{n-1} (n-i) f_i $$<br \/>\n$$!f_0 = 1$$<\/p>\n<p>$$!g_n = \\sum_{i=0}^{n-1} i(i-1) f_{n-i}$$<br \/>\n$$!g_1 = 0$$<\/p>\n<p>\u8fd9\u91cc f_n \u6570\u5217\u6070\u597d\u662f <a href=\"http:\/\/oeis.org\/A088305\">http:\/\/oeis.org\/A088305<\/a><\/p>\n<p>\u7ecf\u8fc7\u4e00\u756a\u5316\u7b80\u5316\u7b80\u3002\u3002<\/p>\n<p>\u5f97\u5230<\/p>\n<p>$$!f_n = 3 f_{n-1} &#8211; f_{n-2} $$<br \/>\n$$!g_n = 2(f_n-f_{n-1}-1) $$<\/p>\n<p>\u6ce8\u610f\u8fb9\u754c\u5373\u53ef\u3002\u3002<\/p>\n<p><a href=\"http:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=2950118\">http:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=2950118<\/a><\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n...\r\nLL f(int n){\r\n    if (!n) return 1;\r\n    return pow(A0, n).d&#x5B;0]&#x5B;1];\r\n}\r\n\r\nLL g(int n){\r\n    if (n==1) return 0;\r\n    return pdtll(2, dffll(dffll(f(n), f(n-1)), 1));\r\n}\r\n\r\nLL T(int n){\r\n    if (n==1) return 1;\r\n    return (f(n)+g(n)) % MOD;\r\n}\r\n...\r\nvoid dfs(int k = 0, int d = 1){\r\n    if (k == SZ(fac)){\r\n        INCll(z, pdtll(get_phi(n\/d), T(d)));\r\n    }\r\n    else{\r\n        REP(i, fac&#x5B;k].se+1){\r\n            dfs(k+1, d);\r\n            d *= fac&#x5B;k].fi;\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<h3>References:<\/h3>\n<p><a href=\"http:\/\/blog.csdn.net\/acm_cxlove\/article\/details\/7868589\">http:\/\/blog.csdn.net\/acm_cxlove\/article\/details\/7868589<\/a><br \/>\n<a href=\"http:\/\/hi.baidu.com\/spellbreaker\/item\/d8bb3bda5af30be6795daa93\">http:\/\/hi.baidu.com\/spellbreaker\/item\/d8bb3bda5af30be6795daa93<\/a><br \/>\n<a href=\"http:\/\/endlesscount.blog.163.com\/blog\/static\/8211978720122149120772\/\">http:\/\/endlesscount.blog.163.com\/blog\/static\/8211978720122149120772\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description: \u5916\u9762\u6709\u4e00\u5708 n \u4e2a\u7ed3\u70b9\uff0c\u4e2d\u5fc3\u6709\u4e00\u4e2a\u7ed3\u70b9\u4e0e n \u4e2a\u7ed3\u70b9\u90fd\u76f8\u8fde\uff0c\u95ee\u8fd9\u4e2a\u5171 2n \u6761\u8fb9\u7684\u8f6e\u72b6\u56fe\u7684\u751f\u6210\u6811\u7684\u65b9\u6848\u6570\u3002 \u65cb\u8f6c\u76f8\u540c\u89c6\u4e3a\u7b49\u4ef7\u3002<\/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-1070","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-hg","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1070","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=1070"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1070\/revisions"}],"predecessor-version":[{"id":1071,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1070\/revisions\/1071"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1070"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1070"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1070"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}