{"id":70,"date":"2011-03-24T07:48:20","date_gmt":"2011-03-23T23:48:20","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=70"},"modified":"2012-03-03T07:49:06","modified_gmt":"2012-03-02T23:49:06","slug":"zoj-3256-tour-in-the-castle","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/zoj-3256-tour-in-the-castle\/","title":{"rendered":"ZOJ 3256. Tour in the Castle"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u8d77\u70b9\u7ec8\u70b9\u56fa\u5b9a\u7684\u201c\u4e00\u6761\u8def\u5f84\u201d\u95ee\u9898\u3002<br \/>\n\uff08.. H <= 10^9\uff0cW <= 7 ..\uff09\n<!--more--><\/p>\n<h3>Analyse :<\/h3>\n<p>&#8230; <\/p>\n<pre lang=\"cpp\">\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\n#include <map>\r\nusing namespace std;   \r\nconst int ww = 7, _W = 16, ll = 127;\r\nconst int _P = 7777777; \r\n\r\nmap<int, int> H; int ST;\r\nint L[ll], h, w, n, up, l;\r\nint i, s, ans;\r\n\r\n\r\nstruct matrix{\r\n\tint d[ll][ll];\r\n\tmatrix(){\r\n\t\tmemset(d, 0, sizeof(d));\r\n\t}\r\n} A, C;\r\n\r\nmatrix operator *(const matrix& a, const matrix& b){\r\n\tmatrix c;\r\n\tfor (int i=1;i<l;i++)\r\n\t\tfor (int j=0;j<l;j++){\r\n\t\t\tlong long temp = 0;\r\n\t\t\tfor (int k=0;k<l;k++)\r\n\t\t\t\ttemp += (long long)(a.d[i][k]) * b.d[k][j];\r\n\t\t\tc.d[i][j] = temp % _P;\r\n\t\t}\r\n\treturn c;\r\n}\r\n\r\nmatrix pow(matrix a, int b){\r\n\tmatrix c;\r\n\tfor (int i = 0; i < l; i ++)\r\n\t\tc.d[i][i] = 1;\r\n\twhile (b!=0){\r\n\t\tif (b%2==1) c = c * a;\r\n\t\ta = a * a, b \/= 2;\r\n\t}\r\n\treturn c;\r\n}\r\n\r\n\r\n#define _Pl (s &#038; (1 << l))\r\n#define _Pr (s &#038; (1 << r))\r\n#define _Pi (s &#038; (1 << i))\r\n\/\/ Check Plug.\r\n\r\n#define _Ol (o &#038; (1 << l))\r\n#define _Or (o &#038; (1 << r))\r\n\/\/ Check Obstacle...\r\n\r\n#define _Tl (s &#038; (1 << l + _W))\r\n#define _Tr (s &#038; (1 << r + _W))\r\n#define _Ti (s &#038; (1 << i + _W))\r\n\/\/ Return Plug Type ..\r\n\r\n\r\n#define _Sl s ^= 1 << l\r\n#define _Sr s ^= 1 << r\r\n\/\/ Reset Plug ..\r\n\r\n#define _Cl s ^= 1 << (l + _W)\r\n#define _Cr s ^= 1 << (r + _W)\r\n#define _Ci s ^= 1 << (i + _W)\r\n\/\/ Change Brace Structure\r\n\r\n\r\n\/*\r\n \r\n void patch(int x){\r\n for (int i=0;i<w;i++){\r\n if (!(x&#038;(1<<i))) cout << \" \";\r\n else if (x &#038; (1 << i + _W)) cout << \")\" ;else cout << \"(\";\r\n }\r\n cout << endl;\r\n }\r\n *\/\r\n\r\ninline int countBits(int x){\r\n    x = (x &#038; 0x00005555) + ((x &#038; 0x0000aaaa) >> 1);\r\n    x = (x & 0x00003333) + ((x & 0x0000cccc) >> 2);\r\n    x = (x & 0x00000f0f) + ((x & 0x0000f0f0) >> 4);\r\n    x = (x & 0x000000ff) + ((x & 0x0000ff00) >> 8);\r\n    return x;\r\n}\r\n\r\nvoid eatLeft(int i){\r\n\tint An = 0;\r\n\tfor (i--;;i--){\r\n\t\tif (!_Pi) continue;\r\n\t\tif (_Ti) An++;\r\n\t\telse {if (An==0){_Ci; return;} An--;}\r\n\t}\r\n}\r\nvoid eatRight(int i){\r\n\tint An = 0;\r\n\tfor (i++;;i++){\r\n\t\tif (!_Pi) continue;\r\n\t\tif (!_Ti) An++;\r\n\t\telse {if (An==0){_Ci; return;} An--;}\r\n\t}\r\n}\r\n\r\n\r\n\r\nvoid dfs(int l){\r\n\tif (l == w){\r\n\t\tA.d[i][H[s]] = 1;\r\n\t}\r\n\telse {\r\n\t\tint r = l + 1;\r\n\t\tint c = s;\r\n\t\t\r\n\t\tif (_Pl){\r\n\t\t\t\/\/ 0: Stable ..\r\n\t\t\tdfs(r);\r\n\t\t\t\r\n\t\t\tif (_Tl){  \r\n\t\t\t\t\/\/ 2: Move_Right with ')' . ..\r\n\t\t\t\twhile (r < w &#038;&#038; !_Pr){ \r\n\t\t\t\t\t_Sl; _Cl; _Sr; _Cr; dfs(++r); s = c;\r\n\t\t\t\t}\r\n\t\t\t\t\r\n\t\t\t\t\/\/ 4: Merge with '))'\r\n\t\t\t\tif (r < w){\r\n\t\t\t\t\tif (_Tr){\r\n\t\t\t\t\t\teatLeft(l); _Sl; _Cl; _Sr; _Cr; dfs(r+1); s = c;\r\n\t\t\t\t\t}\r\n\t\t\t\t\t\/\/ 4: Merge with ')('\r\n\t\t\t\t\telse {\r\n\t\t\t\t\t\t_Sl; _Cl; _Sr; dfs(r+1); s = c;\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\telse {\r\n\t\t\t\t\/\/ 2: Move_Right with '(' . ..\r\n\t\t\t\twhile (r < w &#038;&#038; !_Pr){\r\n\t\t\t\t\t_Sl; _Sr; dfs(++r); s = c;\r\n\t\t\t\t}\r\n\t\t\t\t\r\n\t\t\t\t\/\/ 4: Merge with '(('\r\n\t\t\t\tif (r < w){\r\n\t\t\t\t\tif (!_Tr){\r\n\t\t\t\t\t\teatRight(r); _Sl; _Sr; dfs(r+1); s = c;\r\n\t\t\t\t\t}\r\n\t\t\t\t\t\/\/ 4 Merge with '()'\r\n\t\t\t\t\telse {\r\n\t\t\t\t\t\t\/\/!..#>..#>.f                         \r\n\t\t\t\t\t\tif (r + 1 == w &&  countBits(s)==2){\r\n\t\t\t\t\t\t\tA.d[i][0] = 1;\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\t\r\n\t\t}\r\n\t\telse {\r\n\t\t\t\/\/ 3: Bown a pair of new plug . ...\r\n\t\t\twhile (r < w &#038;&#038; !_Pr){\r\n\t\t\t\t_Sl; _Sr; _Cr; dfs(++r); s = c;\r\n\t\t\t}\r\n\t\t\t\r\n\t\t\t\/\/ 1 Move_Left\r\n\t\t\tif (r < w){\r\n\t\t\t\tif (_Tr) {_Sl; _Cl; _Sr; _Cr; dfs(r+1); s = c;}\r\n\t\t\t\telse {_Sl; _Sr; dfs(r+1); s = c;}\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n}\r\n\r\n\r\nvoid scan(int i, int ln, int rn){\r\n\twhile (!_Pi) i++;\r\n\t\r\n\tif (i==w) {\r\n\t\tH[s ^ up] = l;\r\n\t\tL[l++] = s ^ up;\r\n\t}\r\n\telse {\r\n\t\tif (ln < n) scan(i+1, ln+1, rn);\r\n\t\tif (rn < ln) {_Ci; scan(i+1, ln, rn+1); _Ci;}\r\n\t}\r\n}\r\n\r\nvoid init(){\r\n    memset(A.d, 0, sizeof(A.d));\r\n\tl = 0, up = 1 << w, H.clear();\r\n\t\r\n\tfor (i = 0; i < up; i ++){\r\n\t\tn = countBits(i);\r\n\t\tif ((n&#038;1)==0){s = i | up, n >>= 1, scan(0, 0, 0);}\r\n\t}\r\n\t\r\n\tST =  H[1 | 1 << (w - 1) | 1 << (_W + w - 1)]; \/\/\u521d\u59cb\u5339\u914d\r\n\tfor (i = 1; i < l; i ++)\r\n\t\ts = L[i], dfs(0);\t\r\n}\r\n\r\nvoid solve(){\r\n\tC = pow(A, h);\r\n\tans = C.d[ST][0];\r\n}\r\n\r\nint main(){        \r\n    \/\/freopen(\"in.txt\", \"r\", stdin);\r\n\twhile (scanf(\"%d%d\", &#038;w, &#038;h)==2){\r\n\t\tinit(); solve();\r\n\t\tif (ans == 0) cout << \"Impossible\" << endl;\r\n\t\telse cout << ans << endl;\r\n\t}\r\n}\r\n\r\n\/\/ 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 155126, \r\n\r\n\r\n<\/pre>\n<p><bk><bk><bk><bk><br \/>\n<bk><bk><bk><bk><\/p>\n<h3>Further discussion<\/h3>\n<p><a href=\"https:\/\/www.shuizilong.com\/house\/archives\/2172\">\u6bcd\u9898<\/a>\u91cc\u5199\u4e86\u4e24\u79cd\u65b9\u6cd5\uff0c\u8fd9\u9898\u5efa\u77e9\u9635\u7684\u65f6\u5019\u660e\u663e\u91c7\u53d6 DFS \u9010\u884c\u9012\u63a8\u66f4\u6e05\u695a\u3002<br \/>\n\u3002\u3002\uff08 TLE \u4e0d\u80fd\u81ea\u5df2 \u3002\u3002\u3002\u76f4\u5230 <a href=\"http:\/\/hi.baidu.com\/yali79\/blog\">hpfdf \u795e\u7287<\/a>\u7684\u5f3a\u52bf Debug \u4e0b\uff0c\u77e5\u9053\u77e9\u9635\u4e58\u6cd5\u7684\u65f6\u5019\uff0c\u8981\u7d2f\u79ef\u5230\u5e73\u65b9\u518d\u53d6\u6a21\u3002\u3002\u3002\u3002\u3002\u3002\u63a9\u9762\u3002 \u3002\uff1d =\u3002\u3002\uff09<\/p>\n<h3>External link :<\/h3>\n<p><a href=\"http:\/\/acm.zju.edu.cn\/onlinejudge\/showProblem.do?problemId=3540\">http:\/\/acm.zju.edu.cn\/onlinejudge\/showProblem.do?problemId=3540<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u8d77\u70b9\u7ec8\u70b9\u56fa\u5b9a\u7684\u201c\u4e00\u6761\u8def\u5f84\u201d\u95ee\u9898\u3002 \uff08.. H<\/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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[45],"class_list":["post-70","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-dp"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-18","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/70","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=70"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/70\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=70"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=70"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=70"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}