\u63cf\u8ff0<\/p>\n\n\n\n
\u6709N\u4e2a\u76f8\u540c\u7684\u5f00\u5173\uff0c\u6bcf\u4e2a\u5f00\u5173\u90fd\u4e0e\u67d0\u4e9b\u5f00\u5173\u6709\u7740\u8054\u7cfb\uff0c\u6bcf\u5f53\u4f60\u6253\u5f00\u6216\u8005\u5173\u95ed\u67d0\u4e2a\u5f00\u5173\u7684\u65f6\u5019\uff0c\u5176\u4ed6\u7684\u4e0e\u6b64\u5f00\u5173\u76f8\u5173\u8054\u7684\u5f00\u5173\u4e5f\u4f1a\u76f8\u5e94\u5730\u53d1\u751f\u53d8\u5316\uff0c\u5373\u8fd9\u4e9b\u76f8\u8054\u7cfb\u7684\u5f00\u5173\u7684\u72b6\u6001\u5982\u679c\u539f\u6765\u4e3a\u5f00\u5c31\u53d8\u4e3a\u5173\uff0c\u5982\u679c\u4e3a\u5173\u5c31\u53d8\u4e3a\u5f00\u3002\u4f60\u7684\u76ee\u6807\u662f\u7ecf\u8fc7\u82e5\u5e72\u6b21\u5f00\u5173\u64cd\u4f5c\u540e\u4f7f\u5f97\u6700\u540eN\u4e2a\u5f00\u5173\u8fbe\u5230\u4e00\u4e2a\u7279\u5b9a\u7684\u72b6\u6001\u3002\u5bf9\u4e8e\u4efb\u610f\u4e00\u4e2a\u5f00\u5173\uff0c\u6700\u591a\u53ea\u80fd\u8fdb\u884c\u4e00\u6b21\u5f00\u5173\u64cd\u4f5c\u3002\u4f60\u7684\u4efb\u52a1\u662f\uff0c\u8ba1\u7b97\u6709\u591a\u5c11\u79cd\u53ef\u4ee5\u8fbe\u5230\u6307\u5b9a\u72b6\u6001\u7684\u65b9\u6cd5\u3002\uff08\u4e0d\u8ba1\u5f00\u5173\u64cd\u4f5c\u7684\u987a\u5e8f\uff09<\/p>\n\n\n\n
\u8f93\u5165<\/p>\n\n\n\n
\u8f93\u5165\u7b2c\u4e00\u884c\u6709\u4e00\u4e2a\u6570K\uff0c\u8868\u793a\u4ee5\u4e0b\u6709K\u7ec4\u6d4b\u8bd5\u6570\u636e\u3002
\u6bcf\u7ec4\u6d4b\u8bd5\u6570\u636e\u7684\u683c\u5f0f\u5982\u4e0b\uff1a
\u7b2c\u4e00\u884c \u4e00\u4e2a\u6570N\uff080 < N < 29\uff09
\u7b2c\u4e8c\u884c N\u4e2a0\u6216\u80051\u7684\u6570\uff0c\u8868\u793a\u5f00\u59cb\u65f6N\u4e2a\u5f00\u5173\u72b6\u6001\u3002
\u7b2c\u4e09\u884c N\u4e2a0\u6216\u80051\u7684\u6570\uff0c\u8868\u793a\u64cd\u4f5c\u7ed3\u675f\u540eN\u4e2a\u5f00\u5173\u7684\u72b6\u6001\u3002
\u63a5\u4e0b\u6765 \u6bcf\u884c\u4e24\u4e2a\u6570I J\uff0c\u8868\u793a\u5982\u679c\u64cd\u4f5c\u7b2c I \u4e2a\u5f00\u5173\uff0c\u7b2cJ\u4e2a\u5f00\u5173\u7684\u72b6\u6001\u4e5f\u4f1a\u53d8\u5316\u3002\u6bcf\u7ec4\u6570\u636e\u4ee5 0 0 \u7ed3\u675f\u3002<\/p>\n\n\n\n
\u8f93\u51fa<\/p>\n\n\n\n
\u5982\u679c\u6709\u53ef\u884c\u65b9\u6cd5\uff0c\u8f93\u51fa\u603b\u6570\uff0c\u5426\u5219\u8f93\u51fa\u201cOh,it’s impossible~!!\u201d \u4e0d\u5305\u62ec\u5f15\u53f7\u6837\u4f8b\u8f93\u5165<\/p>\n\n\n\n
2\n3\n0 0 0\n1 1 1\n1 2\n1 3\n2 1\n2 3\n3 1\n3 2\n0 0\n3\n0 0 0\n1 0 1\n1 2\n2 1\n0 0<\/pre>\n\n\n\n\u6837\u4f8b\u8f93\u51fa<\/p>\n\n\n\n
4\nOh,it's impossible~!!\n<\/pre>\n\n\n\n\u63d0\u793a<\/p>\n\n\n\n
\u7b2c\u4e00\u7ec4\u6570\u636e\u7684\u8bf4\u660e\uff1a
\u4e00\u5171\u4ee5\u4e0b\u56db\u79cd\u65b9\u6cd5\uff1a
\u64cd\u4f5c\u5f00\u51731
\u64cd\u4f5c\u5f00\u51732
\u64cd\u4f5c\u5f00\u51733
\u64cd\u4f5c\u5f00\u51731\u30012\u30013 \uff08\u4e0d\u8bb0\u987a\u5e8f\uff09
\u6765\u6e90LIANGLIANG@POJ<\/p>\n\n\n\n<\/p>\n\n\n\n
\u554a\u597d\u4e45\u6ca1\u6709\u66f4\u535a\u5ba2\u4e86\uff0c\u770b\u5230\u4e00\u4e2a\u597d\u73a9\u7684\u9898\u6765\u66f4\u4e00\u66f4\uff08<\/p>\n\n\n\n
<\/p>\n\n\n\n
\u5199\u4e86\u597d\u4e45\u5404\u79cd\u6a21\u62df\u9898\u548c\u677f\u5b50\u9898\u90fd\u5feb\u5fd8\u4e86\u66fe\u7ecfoi\u7684\u5947\u6280\u6deb\u5de7\u4e86\uff08\u96fe
\u770b\u4e86\u4e0b\u8fd9\u9898\u7f51\u4e0a\u5927\u591a\u6570\u4eba\u7ed9\u7684\u9898\u89e3\u662f\u9ad8\u65af\u6d88\u5143\uff1f
\u4e0d\u8fc7\u8fd9\u4e48\u5f31\u7684\u6570\u636e\uff0c\u5f53\u7136\u662f\u66b4\u529b\u5927\u6cd5\u597d\u8fa3\uff08
\u679c\u7136\u7ee7\u627f\u4e86oi\u7684\u5148\u770b\u6570\u636e\u8303\u56f4\u7684\u597d\u4e60\u60efw<\/p>\n\n\n\n\u5f00\u5c40\u5c31\u60f3\u4f4d\u8fd0\u7b97bitset\uff1f\uff0c\u55ef\u5f88\u591a\u5947\u6280\u6deb\u5de7\uff08\u96fe
\u7efc\u5408\u4e00\u4e0b\u9898\u610f\u548c\u6570\u636e\u8303\u56f4\uff0c\u8fd8\u662f\u6bd4\u8f83\u88f8\u7684meet in the middle\uff08<\/p>\n\n\n\n\u6211\u4eec\u53ef\u4ee5\u5bf9\u534a\u5212\u5206\uff0c\u5148\u9884\u5904\u7406\u524d\u4e00\u534a\u5f00\u5173\u6240\u6709\u65b9\u6848\u7684\u7ed3\u679c\uff0c\u7136\u540e\u518d\u5728\u540e\u4e00\u534a\u679a\u4e3e\u65b9\u6848\uff0c\u8ba1\u7b97\u7ed3\u679c\uff0c\u5728map\u91cc\u67e5\u8be2ans\u5c31\u597d\u5566<\/p>\n\n\n\n
\u8fd9\u65f6\u5019\u6211\u4eec\u4e5f\u53d1\u73b0\u53ef\u4ee5\u7528meet in the middle\u7684\u539f\u56e0\u662f\u5f02\u6216\u64cd\u4f5c\u7684\u53ef\u4ea4\u6362\u6027\u548c\u9009\u62e9\u7684\u72ec\u7acb\u6027\uff0c\u8fd9\u6837\u6211\u4eec\u5c31\u53ef\u4ee5\u8086\u65e0\u5fcc\u60ee\u7684\u5212\u5206\u9884\u5904\u7406\u4e86\uff08\u53ef\u80fd\u8fd8\u6709\u5176\u4ed6\u6027\u8d28\uff1f\u53cd\u6b63\u5f02\u6216\u662f\u4e00\u4e2a\u975e\u5e38\u4f18\u7f8e\u7684\u8fd0\u7b97ww<\/p>\n\n\n\n
#include<map>\n#include<cmath>\n#include<queue>\n#include<cstdio>\n#include<string>\n#include<cstring>\n#include<iostream>\n#include<algorithm>\nusing namespace std;\n#define inf 1000000007\n#define ll long long\n#define N 200010\ninline int rd()\n{\n int x=0,f=1;char ch=getchar();\n while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}\n while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}\n return x*f;\n}\nint K,n,f[30],S,T,ans;\nint cg(int x){\n int tmp=0;\n for(int i=1;i<=n;++i){\n if(x&(1<<(i-1))) tmp^=f[i];\n }\n return tmp;\n}\nmap<int,int>st;\nint main()\n{\n K=rd();\n while(K--){\n n=rd();S=T=0;ans=0;\n for(int i=1;i<=n;++i) f[i]=1<<i;\n st.clear();\n for(int i=1;i<=n;++i) S|=rd()<<i;\n for(int i=1;i<=n;++i) T|=rd()<<i;\n int x,y;\n while(true){\n x=rd();y=rd();\n if(!x&&!y) break;\n f[x]|=1<<y;\n }\n int zz=1<<(n\/2);\n for(int i=0;i<zz;++i){\n ++st[S^cg(i)];\n }\n zz=1<<(n-(n\/2));\n for(int i=0;i<zz;++i){\n ans+=st[T^cg(i<<(n\/2))];\n }\n if(ans) printf(\"%d\\n\",ans);\n else puts(\"Oh,it's impossible~!!\");\n }\n return 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u63cf\u8ff0 \u6709N\u4e2a\u76f8\u540c\u7684\u5f00\u5173\uff0c\u6bcf\u4e2a\u5f00\u5173\u90fd\u4e0e\u67d0\u4e9b\u5f00\u5173\u6709\u7740\u8054\u7cfb\uff0c\u6bcf\u5f53\u4f60\u6253\u5f00\u6216\u8005\u5173\u95ed\u67d0\u4e2a\u5f00\u5173\u7684\u65f6\u5019\uff0c\u5176\u4ed6\u7684\u4e0e\u6b64\u5f00\u5173\u76f8\u5173\u8054\u7684 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[83],"class_list":["post-774","post","type-post","status-publish","format-standard","hentry","category-poj","tag-meet-in-the-middle"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/774","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=774"}],"version-history":[{"count":1,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/774\/revisions"}],"predecessor-version":[{"id":775,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/774\/revisions\/775"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=774"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=774"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=774"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}