\u5feb\u901f\u6c83\u5c14\u4ec0\u53d8\u6362\u662f\u4e00\u79cd\u7c7b\u4f3c\u4e8e\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362\u7684\u64cd\u4f5c\u3002\u5b83\u662f\u7528\u6765\u5904\u7406\u5b50\u96c6\u5377\u79ef\u7684\u6709\u6548\u5de5\u5177\u3002
\n\u6211\u4eec\u4f9d\u6b21\u8003\u8651\u64cd\u4f5c\u7b26\u4e3aand or\u6216\u8005xor\u65f6\u7684\u60c5\u51b5\u3002
\n\u6211\u4eec\u5982\u662f\u8003\u8651\uff1a\u5c06\u4e00\u4e2a\u957f\u5ea6\u4e3a\\(2^n\\)\u7684\u6570\u5217\\(A_{0}\\)\u548c\\(A_{1}\\)\u5207\u5272\u6210\u4e24\u4e2a\u957f\u5ea6\u4e3a\\(2^{n-1}\\)\u7684\u90e8\u5206\uff0c\\(A_{0}\\)\u8868\u793a\u4e0b\u6807\u6700\u9ad8\u4f4d\u4e3a0\u7684\u6570\u5217\uff0c\u800c\\(A_{1}\\)\u8868\u793a\u4e0b\u6807\u6700\u9ad8\u4f4d1\u7684\u6570\u5217\u3002
\n\u90a3\u4e48\uff0c\u6211\u4eec\u6709\u5f88\u663e\u7136\u7684and\u7684\u5f0f\u5b50\uff1a
\n$$ C_{0}=A_{0} * B_{0}$$ $$ C_{1}=A_{0} * B_{1} + A_{1} * B_{0} + A_{1} * B_{1}=(A_{0} + A_{1})*(B_{0} + B_{1}) – C_{0}$$
\n\u540c\u7406\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u5230or\u7684\u5f0f\u5b50\u3002
\n$$C_{0}=A_{0} * B_{0} + A_{1} * B_{0} + A_{0} * B_{1} = (A_{0} + A_{1}) * (B_{0} + B_{1}) -C_{1}$$ $$C_{1}=A_{1} * B_{1}$$
\n\u4ee5\u53caxor\u7684\u5f0f\u5b50\uff1a
\n$$C_{0} = A_{0} * B_{0} + A_{1} * B_{1}$$ $$C_{1} = A_{0} * B_{1} + A_{1} * B_{0}$$
\n\u6211\u4eec\u53d1\u73b0\uff0c\u9664\u4e86xor\u4ee5\u5916\u7684\u5f0f\u5b50\uff0c\u90fd\u662f\u300c\u7b80\u6d01\u300d\u7684\u3002
\n\u6362\u800c\u8a00\u4e4b\uff0c\u6211\u4eec\u53ef\u4ee5\u76f4\u63a5\u4ee5\\(nlog_n\\)\u7684\u590d\u6742\u5ea6\u6c42\u5f97\u5b83\u4eec\u7684\u7b54\u6848\u3002
\n\u73b0\u5728\u8003\u8651xor\u8fd9\u4e2a\u7384\u5999\u7684\u5f0f\u5b50\u3002
\n\u6211\u4eec\u53d1\u73b0\u6709\u5982\u4e0b\u6027\u8d28\uff1a
\n$$C_{0} + C_{1} = (A_{0} + A_{1}) * (B_{0} + B_{1})$$ $$C_{0} – C_{1} = (A_{0} – A_{1}) * (B_{0} – B_{1})$$
\n\u6211\u4eec\u4e0d\u59a8\u4ee4\uff1a
\n$$X = (A_{0} + A_{1}) * (B_{0} + B_{1})$$ $$Y = (A_{0} – A_{1}) * (B_{0} – B_{1})$$
\n\u90a3\u4e48
\n$$ C_{0} = \\frac{X + Y}{2}$$ $$ C_{1} = \\frac{X – Y}{2}$$
\n\u4e8e\u662f\u5c31\u505a\u5b8c\u4e86\u3002<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\n\ntypedef long long ll;\nconst ll MOD=998244353;\nconst ll inv2=(MOD+1)>>1;\ninline void fwtor(int *A,int *B,int *C,int N){\n\tif(N==1){\n\t\tC[0]=1ll*A[0]*B[0]%MOD;return;\n\t}\n\tint M=N>>1;\n\tfor(int i=0;i<M;++i){\n\t\tA[i+M]+=A[i];A[i+M]%=MOD;\n\t\tB[i+M]+=B[i];B[i+M]%=MOD;\n\t}\n\tfwtor(A,B,C,M);fwtor(A+M,B+M,C+M,M);\n\tfor(int i=0;i<M;++i){\n\t\tC[i+M]-=C[i]-MOD;C[i+M]%=MOD;\n\t}\n}\ninline void fwtand(int *A,int *B,int *C,int N){\n\tif(N==1){\n\t\tC[0]=1ll*A[0]*B[0]%MOD;return;\n\t}\n\tint M=N>>1;\n\tfor(int i=0;i<M;++i){\n\t\tA[i]+=A[i+M];A[i]%=MOD;\n\t\tB[i]+=B[i+M];B[i]%=MOD;\n\t}\n\tfwtand(A,B,C,M);fwtand(A+M,B+M,C+M,M);\n\tfor(int i=0;i<M;++i){\n\t\tC[i]-=C[i+M]-MOD;C[i]%=MOD;\n\t}\n}\ninline void fwtxor(int *A,int *B,int *C,int N){\n\tif(N==1){\n\t\tC[0]=1ll*A[0]*B[0]%MOD;return;\n\t}\n\tint M=N>>1,XA,YA,XB,YB;\n\tfor(int i=0;i<M;++i){\n\t\tXA=(A[i]+A[i+M])%MOD,YA=(A[i]-A[i+M]+MOD)%MOD;\n\t\tXB=(B[i]+B[i+M])%MOD,YB=(B[i]-B[i+M]+MOD)%MOD;\n\t\tA[i]=XA,A[i+M]=YA,B[i]=XB,B[i+M]=YB;\n\t}\n\tfwtxor(A,B,C,M),fwtxor(A+M,B+M,C+M,M);\n\tfor(int i=0;i<M;++i){\n\t\tXA=(C[i]+C[i+M])%MOD,YA=(C[i]-C[i+M]+MOD)%MOD;\n\t\tC[i]=XA*inv2%MOD,C[i+M]=YA*inv2%MOD;\n\t}\n}\nint n;\nint a[1<<17],b[1<<17],c[1<<17],aa[1<<17],bb[1<<17];\nvoid init(){\n\tscanf(\"%d\",&n);\n\tn=1<<n;\n\tfor(int i=0;i<n;++i)scanf(\"%d\",a+i);\n\tfor(int i=0;i<n;++i)scanf(\"%d\",b+i);\n\tfor(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;\n\tfwtor(aa,bb,c,n);\n\tfor(int i=0;i<n;++i)printf(\"%d \",c[i]);puts(\"\");\n\tfor(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;\n\tfwtand(aa,bb,c,n);\n\tfor(int i=0;i<n;++i)printf(\"%d \",c[i]);puts(\"\");\n\tfor(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;\n\tfwtxor(aa,bb,c,n);\n\tfor(int i=0;i<n;++i)printf(\"%d \",c[i]);puts(\"\");\n}\nint main(){\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u5feb\u901f\u6c83\u5c14\u4ec0\u53d8\u6362\u662f\u4e00\u79cd\u7c7b\u4f3c\u4e8e\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362\u7684\u64cd\u4f5c\u3002\u5b83\u662f\u7528\u6765\u5904\u7406\u5b50\u96c6\u5377\u79ef\u7684\u6709\u6548\u5de5\u5177\u3002 \u6211\u4eec\u4f9d\u6b21\u8003\u8651\u64cd\u4f5c\u7b26\u4e3aand … <\/p>\n