{"id":639,"date":"2019-02-26T21:19:55","date_gmt":"2019-02-26T13:19:55","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=639"},"modified":"2019-02-26T21:19:55","modified_gmt":"2019-02-26T13:19:55","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%88ntt%e5%ae%9e%e7%8e%b0%ef%bc%89","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/02\/26\/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%88ntt%e5%ae%9e%e7%8e%b0%ef%bc%89\/","title":{"rendered":"lp3803 \u3010\u6a21\u677f\u3011\u591a\u9879\u5f0f\u4e58\u6cd5\uff08FFT\uff09\uff08NTT\u5b9e\u73b0\uff09"},"content":{"rendered":"\n
\"\"
\u7a0b\u5e8f\u8fd0\u884c\u6548\u7387\u3002\uff08\u8bc4\u6d4b\u7cfb\u7edf\u4e3aduck.ac\uff09<\/figcaption><\/figure>\n\n\n\n

\u6211\u4eec\u73b0\u5728\u5df2\u7ecf\u6709\u4e00\u79cd\u5feb\u901f\u5b8c\u6210\u591a\u9879\u5f0f\u5377\u79ef\u7684\u65b9\u6848\u4e86\u3002\u7136\u800c\u8fd9\u79cd\u65b9\u6848\u8fd8\u5b58\u5728\u4e24\u4e2a\u7f3a\u9677\u3002
\n\u9996\u5148\uff0c\u662f\u6d6e\u70b9\u578b\u8fd0\u7b97\u5e26\u6765\u7684\u7cbe\u5ea6\u8bef\u5dee\u3002\u8fd9\u5728\u591a\u6b21\u4e58\u79ef\u4e4b\u540e\u4f1a\u4e0d\u65ad\u6269\u5927\uff0c\u6700\u7ec8\u5230\u4e00\u4e2a\u65e0\u6cd5\u89e3\u51b3\u7684\u5730\u6b65\u3002
\n\u7b2c\u4e8c\uff0c\u5c31\u662f\u7ed3\u6784\u4f53\u8fd0\u7b97\u5e26\u6765\u7684\u5927\u5e38\u6570\u3002\u8fd9\u4e5f\u4f7f\u5f97\u8fd9\u9053\u9898\u7684\u65f6\u95f4\u9650\u5236\u53d8\u5f97\u6bd4\u8f83\u7d27\u5f20\u3002
\n\u4e8e\u662f\uff0c\u6211\u4eec\u8003\u8651\u53e6\u8f9f\u8e4a\u5f84\uff0c\u4f7f\u7528\u67d0\u4e00\u79cd\u5927\u6a21\u6570\u6765\u5b8c\u6210\u6574\u6570\u591a\u9879\u5f0f\u5377\u79ef\u3002
\n\u5feb\u901f\u6570\u8bba\u53d8\u6362\uff08Fast Number Transform\uff09\u5c31\u662f\u4e00\u79cd\u8fd9\u6837\u7684\u7b97\u6cd5\u3002<\/p>\n\n\n\n

\u56de\u5230FFT\u7684\u672c\u8d28\uff0cFFT\u662f\u4e00\u79cd\u7cbe\u786e\u9009\u53d6\u53d6\u503c\u4ee5\u540e\u4ee3\u503c\u4f18\u5316\u7cfb\u6570\u8868\u8fbe\u548c\u70b9\u503c\u8868\u8fbe\u76f8\u4e92\u8f6c\u5316\u7684\u65b9\u6848\u3002\u6211\u4eec\u5c1d\u8bd5\u5728\u6a21\u610f\u4e49\u4e0b\u627e\u5230\u4e00\u4e9b\u6ee1\u8db3\u4e0e\u5355\u4f4d\u590d\u6839\u6027\u8d28\u7c7b\u4f3c\u7684\u6570\u3002
\n\u4e00\u79cd\u5728\u6570\u8bba\u4e0a\u88ab\u79f0\u4e3a\u539f\u6839\u7684\u6570\u53ef\u4ee5\u6ee1\u8db3\u8fd9\u4e00\u65cf\u6027\u8d28\u3002
\n\u9996\u5148\u6211\u4eec\u6709\u539f\u6839\u7684\u5b9a\u4e49\u3002
\n\u5f62\u5f0f\u5316\u7684\u8bf4\uff0c\u82e5\\(g\\)\u6a21\\(p\\)\u7684\u9636\u7b49\u4e8e\\(\\phi(p)\\)\uff0c\u5219\u79f0\\(g\\)\u4e3a\\(p\\)\u7684\u4e00\u4e2a\u539f\u6839\u3002
\n\u5177\u4f53\u6765\u8bf4\uff0c\u6211\u4eec\u8ba4\u4e3a\uff0c\u82e5\\(g^x \\equiv 1\\ (mod\\ p) \\)\u603b\u662f\u6709\u89e3\uff0c\u90a3\u4e48\u6211\u4eec\u79f0\\(g\\)\u662f\u8d28\u6570\\(p\\)\u7684\u4e00\u4e2a\u539f\u6839\u3002
\n\u5bf9\u4e8e\\(\\forall g\\in Z,p\\in P\\)\uff0c\u603b\u662f\u6709\\(g^{p-1}\\equiv 1\\ (mod\\ p) \\)
\n\u90a3\u4e48\uff0c\u5bf9\u4e8e\u4e00\u4e2a\\(p=t2^{k}+1\\)\u6211\u4eec\u6709\uff0c\\(g^{\\frac{p-1}{2^i}}\\ (0\\le i\\le k)\\)\u5728\u6a21$latexp$\u610f\u4e49\u4e0b\u59cb\u7ec8\u6709\u6b63\u6574\u6570\u89e3\u3002\u8fd9\u4e00\u70b9\u548c\u5355\u4f4d\u590d\u6839\u7c7b\u4f3c\u3002
\n\u901a\u8fc7\u9009\u53d6\u6ee1\u8db3\u4e0a\u8ff0\u6761\u4ef6\u7684\u8d28\u6570\uff0c\u5373\\(p=t2^{k}+1\\)\uff0c\u6211\u4eec\u8fd8\u6709\u8fd9\u6837\u7684\u6027\u8d28\uff1a
\n\u6d88\u53bb\u5f15\u7406\uff1a
\n$$g^{\\frac{dk(p-1)}{dn}}\\equiv g^{\\frac{k(p-1)}{n}}$$
\n\u6298\u534a\u5f15\u7406\uff1a
\n$$(g^{\\frac{(k+\\frac{n}{2})(p-1)}{n}})^2\\equiv (g^{\\frac{k(p-1)}{n}}g^{\\frac{p-1}{2}})^2\\equiv (g^{\\frac{k(p-1)}{n}}(p-1))^2\\equiv (g^{\\frac{k(p-1)}{n}})^2$$
\n\u6c42\u548c\u5f15\u7406\uff1a
\n$$\\sum_{j=0}^{n-1}(g^{\\frac{k(p-1)}{n}})^j\\equiv \\frac{(g^{\\frac{k(p-1)}{n}})^n-1}{g^{\\frac{k(p-1)}{n}}-1}\\equiv \\frac{g^{k(p-1)}-1}{g^{\\frac{k(p-1)}{n}}-1}\\equiv \\frac{1^k-1}{g^{\\frac{k(p-1)}{n}}}\\equiv 0$$
\n\u6298\u534a\u5f15\u7406\u7684\u4e00\u4e2a\u63a8\u8bba\uff1a
\n$$\\sum_{i=0}^{n-1}g^{\\frac{i(p-1)}{n}}\\equiv 0$$
\n\u6211\u4eec\u60ca\u8bb6\u5730\u53d1\u73b0\u539f\u6839\u5177\u6709\u5355\u4f4d\u590d\u6839\u5177\u6709\u7684\u4e09\u4e2a\u5b9a\u7406\u548c\u4e00\u4e2a\u63a8\u8bba\u3002\u8fd9\u8bf4\u660e\uff0c\u6211\u4eec\u53ef\u4ee5\u5c06\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362\u7684\u64cd\u4f5c\u4ee5\u539f\u6839\u7684\u5f62\u5f0f\u62d3\u5c55\u5230\u6a21\u610f\u4e49\u4e0b\u3002
\n\u6211\u4eec\u4ee4\uff1a
\n$$\\omega_{n}^{k}=g^{\\frac{k(p-1)}{n}}$$
\n\u90a3\u4e48\u6211\u4eec\u5c31\u53ef\u4ee5\u7b80\u5355\u5730\u5c06\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362\u4e2d\u7684\u5355\u4f4d\u590d\u6839\u5168\u90e8\u66ff\u6362\u4e3a\u539f\u6839\uff0c\u8fd9\u6837\u5c31\u5b9e\u73b0\u4e86\u5feb\u901f\u6570\u8bba\u53d8\u6362\u3002
\n\u5bf9\u4e8e\u8fd9\u91cc\u7684\u6a21\u6570\\(p\\)\uff0c\u6211\u4eec\u53ef\u4ee5\u9009\u53d6998244353\uff0c\u5b83\u662f\\(2^{23}*119+1\\)\u3002 <\/p>\n\n\n\n

#include<iostream>\n#include<cstdio>\n#define Swap(A,B) (A^=B^=A^=B)\nconst long long P=998244353;\nconst long long g0=3,gi=332748118;\n\/\/*****\u975e\u5e38\u91cd\u8981\uff1agi\u662f332748118!!!!!!! \nint L=1,R[1<<21|1];\nlong long invL;\ninline int pw(int A,int X){\n\tlong long BS=A,RT=1;\n\twhile(X){\n\t\tif(X&1){\n\t\t\tRT=RT*BS%P;\n\t\t}\n\t\tBS=BS*BS%P;\n\t\tX>>=1;\n\t}\n\treturn RT;\n}\ninline void prpr(int LEN){\n\tint B=0;\n\twhile(L<=LEN){\n\t\tL<<=1;\n\t\t++B;\n\t}\n\tinvL=P-(P-1)\/L;\n\tfor(int i=0;i<L;++i){\n\t\tR[i]=R[i>>1]>>1|(i&1)<<(B-1);\n\t}\n}\ninline void FNTT(int *A,int typ){\n\tfor(int i=0;i<L;++i){\n\t\tif(R[i]<i){\n\t\t\tSwap(A[R[i]],A[i]);\n\t\t}\n\t}\n\tint gn,g,X,Y,M;\n\tfor(int i=2;i<=L;i<<=1){\n\t\tM=i>>1;\n\t\tgn=pw(~typ?g0:gi,(P-1)\/i);\n\t\tfor(int j=0;j<L;j+=i){\n\t\t\tg=1;\n\t\t\tfor(int k=0;k<M;++k,g=1ll*g*gn%P){\n\t\t\t\tX=A[j+k],Y=1ll*g*A[M+j+k]%P;\n\t\t\t\tA[j+k]=(X+Y)%P,A[M+j+k]=(X-Y)%P;\n\t\t\t}\n\t\t}\n\t}\n}\nint n,m,a[1<<21|1],b[1<<21|1];\nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\tfor(int i=0;i<=n;++i){\n\t\tscanf(\"%d\",a+i);\n\t}\n\tfor(int i=0;i<=m;++i){\n\t\tscanf(\"%d\",b+i);\n\t}\n\tprpr(n+m);\n\tFNTT(a,1);\n\tFNTT(b,1);\n\tfor(int i=0;i<L;++i){\n\t\ta[i]=1ll*a[i]*b[i]%P;\n\t}\n\tFNTT(a,-1);\n\tfor(int i=0;i<=n+m;++i){\n\t\tprintf(\"%d \",1ll*(a[i]+P)*invL%P);\n\t}\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u6211\u4eec\u73b0\u5728\u5df2\u7ecf\u6709\u4e00\u79cd\u5feb\u901f\u5b8c\u6210\u591a\u9879\u5f0f\u5377\u79ef\u7684\u65b9\u6848\u4e86\u3002\u7136\u800c\u8fd9\u79cd\u65b9\u6848\u8fd8\u5b58\u5728\u4e24\u4e2a\u7f3a\u9677\u3002 \u9996\u5148\uff0c\u662f\u6d6e\u70b9\u578b\u8fd0\u7b97\u5e26\u6765\u7684\u7cbe\u5ea6\u8bef\u5dee\u3002 … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201clp3803 \u3010\u6a21\u677f\u3011\u591a\u9879\u5f0f\u4e58\u6cd5\uff08FFT\uff09\uff08NTT\u5b9e\u73b0\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,91,8,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/639"}],"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=639"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/639\/revisions"}],"predecessor-version":[{"id":642,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/639\/revisions\/642"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=639"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=639"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=639"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}