\u521d\u59cb\u957f\u5ea6$2^n$\u768401\u5e8f\u5217\uff0c\u8981\u4ece^&|\u4e2d\u9009\u62e9n\u4e2a\u8fd0\u7b97\u7b26\u3002
\n\u2022 \u5e8f\u5217\u957f\u5ea6:$(2^n)\\to (2^{n-1})\\to … \\to 16\\to 8\\to 4\\to 2\\to 1$\u3002
\n\u2022 \u95ee\u6709\u591a\u5c11\u4e2a\u53ef\u80fd\uff0c\u4f7f\u5f97\u8fd0\u7b97\u540e\u5269\u4e0b\u7684\u4e00\u4e2a\u5b57\u7b26\u4e3a1\u3002<\/p>\n
\u4e8b\u5b9e\u4e0a\u8fd9\u9053\u9898\u66b4\u529b\u5c31\u662f\u6807\u51c6\u505a\u6cd5\uff0c\u4f46\u662fdfs\u7684\u8fc7\u7a0b\u4e00\u5b9a\u662f$3^n$\u7684\uff0c\u4f1a\u8d85\u51fa\u9898\u76ee\u8981\u6c42\u65f6\u95f4\u3002\u6211\u4eec\u5fc5\u987b\u8003\u8651\u526a\u679d\u6216\u8005\u5bf9\u5c0f\u8303\u56f4\u6570\u636e\u8fdb\u884c\u4f18\u5316\u3002<\/p>\n
\u2022 \u66b4\u529b\u7684\u590d\u6742\u5ea6\u662f$3^n$\u7684\uff0c\u53ea\u9700\u8981\u518d\u4f18\u5316\u4e00\u70b9\u70b9!
\n\u2022 \u5982\u679c\u5269\u4e0b\u4e86$16$\u4e2a\u53d8\u91cf\uff0c\u53ef\u80fd\u6027\u53ea\u6709$65536$\u4e2a\u3002
\n\u2022 \u9884\u5904\u7406\u4ed6\u4eec\uff0c\u5f97\u5230\u4e00\u4e2a$3^{n-4}$\u7684\u505a\u6cd5(\u4e8b\u5b9e\u4e0a\u5b98\u65b9\u5728\u8fd9\u91cc\u5f04\u9519\u4e86\uff0c\u662f$3^{n-4} * 2^{n-4}$)\u3002
\n\u2022 \u4e8b\u5b9e\u4e0a\uff0c\u76f4\u63a5\u66b4\u529b\uff0c\u5e38\u6570\u4f18\u5316\u5373\u53ef\u3002<\/p>\n
#include <bits\/stdc++.h>\n#include <ext\/pb_ds\/assoc_container.hpp>\n#include <ext\/pb_ds\/tree_policy.hpp>\n\nusing namespace std;\nusing namespace __gnu_pbds;\n\n#define fi first\n#define se second\n#define mp make_pair\n#define pb push_back\n#define fbo find_by_order\n#define ook order_of_key\n\ntypedef long long ll;\ntypedef pair<ll,ll> ii;\ntypedef vector<int> vi;\ntypedef long double ld; \ntypedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;\ntypedef set<ll>::iterator sit;\ntypedef map<ll,ll>::iterator mit;\n\nbool B[22][(1<<20)+5];\nint ans = 0;\nint dp[5][(1<<16)+15];\n\nvoid gen(int n)\n{\n int pow3=1;\n for(int i=0;i<n;i++) pow3*=3;\n for(int i=0;i<(1<<(1<<n));i++)\n {\n for(int k=0;k<(1<<n);k++)\n {\n if(i&(1<<k)) B[n][k] = 1;\n else B[n][k] = 0;\n }\n for(int j=0;j<pow3;j++)\n {\n int cur = j;\n for(int k=n-1;k>=0;k--)\n {\n int z=cur%3;\n for(int l=0;l<(1<<k);l++)\n {\n if(z==0) B[k][l]=B[k+1][2*l]&B[k+1][2*l+1];\n else if(z==1) B[k][l]=B[k+1][2*l]^B[k+1][2*l+1];\n else B[k][l]=B[k+1][2*l]|B[k+1][2*l+1];\n }\n cur\/=3;\n }\n dp[n][i] += B[0][0];\n }\n }\n}\n\nvoid solve(int n)\n{\n if(n<=4)\n {\n int bit = 0;\n for(int i=0;i<(1<<n);i++)\n {\n if(B[n][i]) bit^=(1<<i);\n }\n ans += dp[n][bit];\n return ;\n }\n for(int i = 0; i < 3; i++)\n {\n for(int j = 0; j < (1<<(n-1)); j++)\n {\n if(i==0) B[n-1][j] = B[n][2*j]&B[n][2*j+1];\n else if(i==1) B[n-1][j] = B[n][2*j]^B[n][2*j+1];\n else B[n-1][j] = B[n][2*j]|B[n][2*j+1];\n }\n solve(n-1);\n }\n}\n\nint main()\n{\n ios_base::sync_with_stdio(0); cin.tie(0);\n int n; cin>>n; string z; cin>>z;\n for(int i=0;i<=4;i++) gen(i);\n for(int i=0;i<(1<<n);i++)\n {\n B[n][i] = z[i] - '0';\n }\n solve(n);\n cout<<ans<<'\\n';\n}\n<\/code><\/pre>\n\u5176\u4ed6\u65b9\u6cd5<\/h3>\n
\u4e8b\u5b9e\u4e0a\u53ef\u4ee5\u8003\u8651\u526a\u679d
\ndfs\u5bf9\u6bcf\u4e2a\u64cd\u4f5c\u7684\u6240\u6709\u53ef\u80fd\u8ba1\u6570\uff0c\u5982\u679c\u64cd\u4f5c\u7ed3\u679c\u7b49\u4e8e1\uff0c\u5219$cnt+=1$
\n\u5f53$cnt == 2^i$\u4e5f\u5c31\u662f\u7b49\u4e8e\u4e0b\u4e00\u5c42\u7684\u957f\u5ea6\uff0c\u4e5f\u5c31\u662f\u4e0b\u4e00\u5c42\u5747\u4e3a1\uff0c\u7b54\u6848+=cnt,\u5426\u5219\u624d\u7ee7\u7eed\u5f80\u4e0bdfs<\/p>\n
\u8fd9\u6837\u8ba1\u7b97\u7684\u6700\u574f\u60c5\u51b5\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a$3^n * (2^{17} + 2^{16} + … + 2) = 3^n * 2^{18} – 3$\uff0c\u4e3a$\\mathcal O(3^{n} * 2^{n})$<\/p>\n
AC\u4ee3\u7801<\/h2>\n#include <iostream>\n\nusing namespace std;\nconst int maxn = (1 << 18) + 5;\nchar ch[20][maxn];\nint ans;\n\ninline char op(char x, char y, int ope) {\n switch (ope) {\n case 1:\n return x ^ y;\n case 2:\n return x & y;\n case 3:\n return x | y;\n default:\n return 0;\n }\n}\n\nvoid dfs(char *s, int n) {\n for (int ope = 1; ope <= 3; ope++) {\n int cnt = 0;\n for (int i = 0; i < (1 << n); i += 2) {\n ch[n - 1][i >> 1] = op(s[i], s[i + 1], ope);\n if (ch[n - 1][i >> 1])\n cnt++;\n }\n if (cnt == (1 << (n - 1))) {\n ans += cnt;\n } else if (cnt) {\n dfs(ch[n - 1], n - 1);\n }\n }\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(0);\n cout.tie(0);\n int n;\n string s;\n cin >> n;\n cin >> ch[n];\n for (int i = 0; ch[n][i]; ++i) {\n ch[n][i] -= '0';\n }\n dfs(ch[n], n);\n cout << ans << '\\n';\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u9898\u610f \u521d\u59cb\u957f\u5ea6$2^n$\u768401\u5e8f\u5217\uff0c\u8981\u4ece^&|\u4e2d\u9009\u62e9n\u4e2a\u8fd0\u7b97\u7b26\u3002 \u2022 \u5e8f\u5217\u957f\u5ea6:$(2^n)\\to ( […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[39,49,22],"tags":[],"class_list":["post-424","post","type-post","status-publish","format-standard","hentry","category-c","category-49","category-22"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-6Q","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/424","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=424"}],"version-history":[{"count":1,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/424\/revisions"}],"predecessor-version":[{"id":429,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/424\/revisions\/429"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=424"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=424"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=424"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}