{"id":626,"date":"2019-02-18T00:06:02","date_gmt":"2019-02-17T16:06:02","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=626"},"modified":"2019-02-18T00:08:35","modified_gmt":"2019-02-17T16:08:35","slug":"lp3803-%e3%80%90%e6%a8%a1%e6%9d%bf%e3%80%91%e5%a4%9a%e9%a1%b9%e5%bc%8f%e4%b9%98%e6%b3%95%ef%bc%88fft%ef%bc%89%ef%bc%88%e9%9d%9e%e9%80%92%e5%bd%92%e7%89%88%e6%9c%ac%ef%bc%89","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/02\/18\/lp3803-%e3%80%90%e6%a8%a1%e6%9d%bf%e3%80%91%e5%a4%9a%e9%a1%b9%e5%bc%8f%e4%b9%98%e6%b3%95%ef%bc%88fft%ef%bc%89%ef%bc%88%e9%9d%9e%e9%80%92%e5%bd%92%e7%89%88%e6%9c%ac%ef%bc%89\/","title":{"rendered":"lp3803 \u3010\u6a21\u677f\u3011\u591a\u9879\u5f0f\u4e58\u6cd5\uff08FFT\uff09\uff08\u975e\u9012\u5f52\u7248\u672c\uff09"},"content":{"rendered":"\n

\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362\uff08FFT\uff09\u7684\u4e00\u79cd\u8f83\u9ad8\u6548\u7684\u5b9e\u73b0<\/p>\n\n\n\n

*\u7531\u4e8e\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362\uff08FFT\uff09\u5e38\u5e38\u88ab\u7528\u5728\u901a\u4fe1\u9886\u57df\uff0c\u6545\u800cFFT\u7684\u5b9e\u73b0\u6548\u7387\u6210\u4e3a\u4e86\u4e00\u4e2a\u9700\u8981\u88ab\u8003\u5bdf\u7684\u5bf9\u8c61\u3002 <\/p>\n\n\n\n

\u4e8b\u5b9e\u4e0a\uff0c\u89c2\u5bdfFFT\u7684\u5b9e\u73b0\u8fc7\u7a0b\uff0c\u6211\u4eec\u53d1\u73b0\u5b83\u6ca1\u6709\u975e\u9012\u5f52\u4e0d\u53ef\u7684\u7406\u7531\u3002<\/p>\n\n\n\n

\u5177\u4f53\u6765\u8bf4\uff0c\u6211\u4eec\u53d1\u73b0\uff0c\u5982\u679c\u6211\u4eec\u60f3\u8981\u628aFFT\u6539\u9020\u4e3a\u9012\u63a8\u6a21\u5f0f\uff0c\u6700\u5927\u7684\u969c\u788d\u5c31\u662f\u6bcf\u4e00\u6b21\u5408\u5e76\u64cd\u4f5c\u3002
\n\u5728\u5feb\u901f\u79bb\u6563\u5085\u91cc\u53f6\u53d8\u6362\u4e2d\uff0c\u6bcf\u4e00\u6b21\u5408\u5e76\u64cd\u4f5c\u90fd\u4f1a\u5bfc\u81f4\u4e24\u4e2a\u8ddd\u79bb\u4e3a\\(\\frac{n}{2}\\)\u7684\u70b9\u7684\u503c\u5408\u5e76\u5728\u4e00\u8d77\u3002\u56e0\u6b64\uff0c\u5982\u679c\u5c06\u539f\u5e8f\u5217\u4f20\u5165\uff0c\u90a3\u4e48\u5f97\u5230\u7684\u5c31\u662f\u4e00\u4e2a\u4e71\u5e8f\u7684\u961f\u5217\u3002
\n\u6211\u4eec\u8003\u8651\u5c06\u5e8f\u5217\u4ee5\u4ec0\u4e48\u987a\u5e8f\u4f20\u5165\u3002
\n\u6211\u4eec\u53d1\u73b0\uff0c\u6bcf\u4e00\u6b21\u8fd9\u6837\u7684\u5408\u5e76\u64cd\u4f5c\u672c\u8d28\u4e0a\u90fd\u662f\u5c06\u4e24\u4e2a\u90e8\u5206\u300c\u7ffb\u8f6c\u300d\u4e86\u3002
\n\u4ee50~7\u4e3a\u4f8b\uff1a
\n0 1 2 3 4 5 6 7
\n0 4 2 6 1 5 3 7
\n\u5c06\u5b83\u4eec\u5199\u6210\u4e8c\u8fdb\u5236\uff1a
\n000 001 010 011 100 101 110 111
\n000 100 010 110 001 101 011 111
\n\u53d1\u73b0\u53d8\u6362\u4e4b\u540e\u6bcf\u4e2a\u6570\u7684\u4e8c\u8fdb\u5236\u4f4d\u90fd\u5012\u8f6c\u4e86\u3002
\n\u6545\u800c\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u5012\u8f6c\u4e8c\u8fdb\u5236\u4f4d\u7684\u65b9\u5f0f\u6765\u9884\u5904\u7406\u539f\u5e8f\u5217\uff0c\u4f7f\u5f97FFT\u4e4b\u540e\u7684\u5e8f\u5217\u987a\u5e8f\u662f\u6b63\u5e38\u7684\u3002
\n\u4f46\u662f\u4e0d\u77e5\u9053\u662f\u4ec0\u4e48\u539f\u56e0\uff0c\u8fd9\u4e2a\u4ee3\u7801\u8dd1\u51fa\u6765\u7684\u901f\u5ea6\u7adf\u7136\u4e5f\u662f4500ms\u2026\u8fd9\u5c31\u5f88\u8ba9\u4eba\u6320\u5934\u4e86\u3002
\n\u4e8e\u662f\u5411PinkRabbit\u5de8\u795e\u8bf7\u6559\u4e86\u51e0\u4e2a\u7ecf\u9a8c\uff1a
\n1.\u4e0d\u7528\u4e2d\u95f4\u6570\u7ec4\uff0c\u76f4\u63a5\u5728\u539f\u6570\u7ec4\u4e0a\u64cd\u4f5c\u3002
\n2.\u8c03\u6574\u8d4b\u503c\u64cd\u4f5c\uff0c\u4f7f\u5f97\u4fee\u6539\u5c3d\u91cf\u5c11\u3002
\n3.\u5c06\u8774\u8776\u53d8\u6362\u9884\u5904\u7406\u4e3a\u4e00\u4e2a\u6570\u7ec4\u3002
\n\u7efc\u5408\u51e0\u70b9\uff0c\u5c31\u6210\u529f\u5730\u5361\u5230\u4e862500ms
\n\u5f53\u7136\u8fd8\u662f\u6709\u5f85\u5361\u5e38\uff0c\u6bd5\u7adf\u8fd9\u8fd8\u662f\u4e00\u4e2a\u6bd4\u8f83\u5371\u9669\u7684\u65f6\u95f4\u3002<\/p>\n\n\n\n

#include<iostream>\n#include<cstdio>\n#include<cmath>\n#define PI 3.141592653589793238462\n\nstruct Complex{\n\tdouble r;\n\tdouble i;\n\tComplex(double ri=0.0,double ii=0.0):r(ri),i(ii){}\n\tinline Complex operator+(const Complex &B)const{\n\t\treturn (Complex){r+B.r,i+B.i}; \n\t}\n\tinline Complex operator-(const Complex &B)const{\n\t\treturn (Complex){r-B.r,i-B.i};\n\t}\n\tinline Complex operator*(const Complex &B)const{\n\t\treturn (Complex){r*B.r-i*B.i,r*B.i+i*B.r};\n\t}\n}a[1<<21|1],b[1<<21|1],s[1<<21|1];\nint r[1<<21|1];\ninline void FFT(Complex *A,int N,int typ){\n\t\/\/ButterflyTransform\n\tfor(int i=0;i<N;++i){\n\t\t(r[i]>i)?std::swap(A[i],A[r[i]]),0:0;\n\t}\n\tComplex bs,nw,x,y;\n\tfor(int i=2,mid;i<=N;i<<=1){\n\t\tbs=Complex(cos(2.0*PI\/i),typ*sin(2.0*PI\/i));\n\t\tmid=i>>1;\n\t\tfor(int j=0;j<N;j+=i){\n\t\t\tnw=Complex(1.0,0.0);\n\t\t\tfor(int k=0;k<mid;++k,nw=nw*bs){\n\t\t\t\tx=A[j+k],y=(A[mid+j+k]*nw);\n\t\t\t\tA[j+k]=x+y;\n\t\t\t\tA[mid+j+k]=x-y;\n\t\t\t}\n\t\t}\n\t}\n}\nint n,m,cnt=1,byt=0;;\nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\tfor(int i=0;i<=n;++i){\n\t\tscanf(\"%lf\",&a[i].r);\n\t}\n\tfor(int i=0;i<=m;++i){\n\t\tscanf(\"%lf\",&b[i].r);\n\t}\n\twhile(cnt<=n+m){\n\t\tcnt<<=1;\n\t\t++byt;\n\t}\n\tfor(int i=0;i<cnt;++i){\n\t\tr[i]=(r[i>>1]>>1)|((i&1)<<(byt-1));\n\t}\n\tFFT(a,cnt,1);\n\tFFT(b,cnt,1);\n\tfor(int i=0;i<cnt;++i){\n\t\ta[i]=a[i]*b[i];\n\t}\n\tFFT(a,cnt,-1);\n\t\/\/\u6ce8\u610f\u8fd9\u91cctyp\u5e94\u8be5\u662f-1 \n\tfor(int i=0;i<=n+m;++i){\n\t\tprintf(\"%d \",(int)(a[i].r\/cnt+0.5));\n\t\t\/\/\u6ce8\u610f\u8f93\u51fa\u5e94\u8be5\u5f3a\u8f6c\u683c\u5f0f\u3002 \n\t}\n\tputs(\"\");\n}\n\nint main(){\n\tinit();\n\treturn 0; \n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362\uff08FFT\uff09\u7684\u4e00\u79cd\u8f83\u9ad8\u6548\u7684\u5b9e\u73b0 *\u7531\u4e8e\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362\uff08FFT\uff09\u5e38\u5e38\u88ab\u7528\u5728\u901a\u4fe1\u9886\u57df\uff0c\u6545\u800cFFT\u7684\u5b9e\u73b0 … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201clp3803 \u3010\u6a21\u677f\u3011\u591a\u9879\u5f0f\u4e58\u6cd5\uff08FFT\uff09\uff08\u975e\u9012\u5f52\u7248\u672c\uff09\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[84,85,8,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/626"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=626"}],"version-history":[{"count":2,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/626\/revisions"}],"predecessor-version":[{"id":628,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/626\/revisions\/628"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=626"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=626"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=626"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}