{"id":486,"date":"2018-01-07T18:54:11","date_gmt":"2018-01-07T10:54:11","guid":{"rendered":"http:\/\/kylelv.com\/?p=486"},"modified":"2018-01-16T21:26:37","modified_gmt":"2018-01-16T13:26:37","slug":"loj-6059-%e3%80%8c2017-%e5%b1%b1%e4%b8%9c%e4%b8%80%e8%bd%ae%e9%9b%86%e8%ae%ad-day1%e3%80%8dsum-%e5%80%8d%e5%a2%9entt","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=486","title":{"rendered":"loj #6059. \u300c2017 \u5c71\u4e1c\u4e00\u8f6e\u96c6\u8bad Day1\u300dSum  &#8212; \u500d\u589e+NTT"},"content":{"rendered":"<div class=\"ui center aligned grid\">\n<div class=\"row\">\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_73 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69fdeefeb5b66\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69fdeefeb5b66\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blog.kylelv.com\/?p=486\/#6059_%E3%80%8C2017_%E5%B1%B1%E4%B8%9C%E4%B8%80%E8%BD%AE%E9%9B%86%E8%AE%AD_Day1%E3%80%8DSum\" title=\"#6059. \u300c2017 \u5c71\u4e1c\u4e00\u8f6e\u96c6\u8bad Day1\u300dSum\">#6059. \u300c2017 \u5c71\u4e1c\u4e00\u8f6e\u96c6\u8bad Day1\u300dSum<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blog.kylelv.com\/?p=486\/#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0\" title=\"\u9898\u76ee\u63cf\u8ff0\">\u9898\u76ee\u63cf\u8ff0<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blog.kylelv.com\/?p=486\/#%E8%BE%93%E5%85%A5%E6%A0%BC%E5%BC%8F\" title=\"\u8f93\u5165\u683c\u5f0f\">\u8f93\u5165\u683c\u5f0f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blog.kylelv.com\/?p=486\/#%E8%BE%93%E5%87%BA%E6%A0%BC%E5%BC%8F\" title=\"\u8f93\u51fa\u683c\u5f0f\">\u8f93\u51fa\u683c\u5f0f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blog.kylelv.com\/?p=486\/#%E6%A0%B7%E4%BE%8B\" title=\"\u6837\u4f8b\">\u6837\u4f8b<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blog.kylelv.com\/?p=486\/#%E6%A0%B7%E4%BE%8B%E8%BE%93%E5%85%A5\" title=\"\u6837\u4f8b\u8f93\u5165\">\u6837\u4f8b\u8f93\u5165<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blog.kylelv.com\/?p=486\/#%E6%A0%B7%E4%BE%8B%E8%BE%93%E5%87%BA\" title=\"\u6837\u4f8b\u8f93\u51fa\">\u6837\u4f8b\u8f93\u51fa<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blog.kylelv.com\/?p=486\/#%E6%95%B0%E6%8D%AE%E8%8C%83%E5%9B%B4%E4%B8%8E%E6%8F%90%E7%A4%BA\" title=\"\u6570\u636e\u8303\u56f4\u4e0e\u63d0\u793a\">\u6570\u636e\u8303\u56f4\u4e0e\u63d0\u793a<\/a><\/li><\/ul><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h2 class=\"ui header\" style=\"text-align: center;\"><span class=\"ez-toc-section\" id=\"6059_%E3%80%8C2017_%E5%B1%B1%E4%B8%9C%E4%B8%80%E8%BD%AE%E9%9B%86%E8%AE%AD_Day1%E3%80%8DSum\"><\/span>#6059. \u300c2017 \u5c71\u4e1c\u4e00\u8f6e\u96c6\u8bad Day1\u300dSum<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<\/div>\n<div class=\"row\" style=\"text-align: center;\"><span class=\"ui label\">\u5185\u5b58\u9650\u5236\uff1a256 MiB\u00a0<\/span><span class=\"ui label\">\u65f6\u95f4\u9650\u5236\uff1a1500 ms<\/span><\/div>\n<\/div>\n<div class=\"ui grid\">\n<div class=\"row\">\n<div class=\"column\">\n<div class=\"ui buttons right floated\"><\/div>\n<\/div>\n<\/div>\n<div class=\"row\">\n<div class=\"column\">\n<h4 class=\"ui top attached block header\"><span class=\"ez-toc-section\" id=\"%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0\"><\/span>\u9898\u76ee\u63cf\u8ff0<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<div class=\"ui bottom attached segment font-content\">\n<div>\n<p>\u6c42\u6709\u591a\u5c11\u00a0<span class=\"katex\"><span class=\"katex-mathml\">n <\/span><\/span>\u4f4d\u5341\u8fdb\u5236\u6570\u662f\u00a0<span class=\"katex\"><span class=\"katex-mathml\">p p<\/span><span class=\"katex-html\"><span class=\"base textstyle uncramped\"><span class=\"mord mathit\">p<\/span><\/span><\/span><\/span>\u00a0\u7684\u500d\u6570\u4e14\u6bcf\u4f4d\u4e4b\u548c\u5c0f\u4e8e\u7b49\u4e8e\u00a0<span class=\"katex\"><span class=\"katex-mathml\">mi(mi=0,1,2,\u2026,m\u22121,m) <\/span><\/span>\uff0c\u5141\u8bb8\u524d\u5bfc\u00a0<span class=\"katex\"><span class=\"katex-mathml\">0<\/span><\/span>\uff0c\u7b54\u6848\u5bf9\u00a0<span class=\"katex\"><span class=\"katex-mathml\">998244353 <\/span><\/span>\u53d6\u6a21\u3002<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"row\">\n<div class=\"column\">\n<h4 class=\"ui top attached block header\"><span class=\"ez-toc-section\" id=\"%E8%BE%93%E5%85%A5%E6%A0%BC%E5%BC%8F\"><\/span>\u8f93\u5165\u683c\u5f0f<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<div class=\"ui bottom attached segment font-content\">\n<div>\n<p>\u4e00\u884c\u4e09\u4e2a\u6574\u6570\u00a0<span class=\"katex\"><span class=\"katex-mathml\">n,p,m<\/span><\/span>\u3002<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"row\">\n<div class=\"column\">\n<h4 class=\"ui top attached block header\"><span class=\"ez-toc-section\" id=\"%E8%BE%93%E5%87%BA%E6%A0%BC%E5%BC%8F\"><\/span>\u8f93\u51fa\u683c\u5f0f<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<div class=\"ui bottom attached segment font-content\">\n<div>\n<p>\u8f93\u51fa\u4e00\u884c\u00a0<span class=\"katex\"><span class=\"katex-mathml\">m+1<\/span><\/span>\u4e2a\u6b63\u6574\u6570\uff0c\u5206\u522b\u8868\u793a\u00a0<span class=\"katex\"><span class=\"katex-mathml\">mi=0,1,2,\u2026,m\u22121,m\u00a0<\/span><\/span>\u65f6\u7684\u7b54\u6848\u3002<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"row\">\n<div class=\"column\">\n<h4 class=\"ui top attached block header\"><span class=\"ez-toc-section\" id=\"%E6%A0%B7%E4%BE%8B\"><\/span>\u6837\u4f8b<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<div class=\"ui bottom attached segment font-content\">\n<div>\n<h4><span class=\"ez-toc-section\" id=\"%E6%A0%B7%E4%BE%8B%E8%BE%93%E5%85%A5\"><\/span>\u6837\u4f8b\u8f93\u5165<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<div class=\"ui existing segment\">\n<pre><code class=\"lang-plain\">2 3 3<\/code><\/pre>\n<\/div>\n<h4><span class=\"ez-toc-section\" id=\"%E6%A0%B7%E4%BE%8B%E8%BE%93%E5%87%BA\"><\/span>\u6837\u4f8b\u8f93\u51fa<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<div class=\"ui existing segment\">\n<pre><code class=\"lang-plain\">1 1 1 5<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"row\">\n<div class=\"column\">\n<h4 class=\"ui top attached block header\"><span class=\"ez-toc-section\" id=\"%E6%95%B0%E6%8D%AE%E8%8C%83%E5%9B%B4%E4%B8%8E%E6%8F%90%E7%A4%BA\"><\/span>\u6570\u636e\u8303\u56f4\u4e0e\u63d0\u793a<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<h4 class=\"ui top attached block header\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-487\" src=\"http:\/\/kylelv.com\/wp-content\/uploads\/2018\/01\/QQ\u622a\u56fe20180116212221.jpg\" alt=\"\" width=\"466\" height=\"86\" srcset=\"https:\/\/blog.kylelv.com\/wp-content\/uploads\/2018\/01\/QQ\u622a\u56fe20180116212221.jpg 466w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2018\/01\/QQ\u622a\u56fe20180116212221-300x55.jpg 300w\" sizes=\"auto, (max-width: 466px) 100vw, 466px\" \/><\/h4>\n<p>&nbsp;<\/p>\n<p>\u9996\u5148\u88f8dp\u6bd4\u8f83\u597d\u63a8\uff0cf[i][j][k]\u8868\u793a\u7b2ci\u4f4d\uff0c\u6a21p\u4e3aj\uff0c\u6570\u5b57\u548c\u4e3ak\u7684\u65b9\u6848\u6570<\/p>\n<p>\u7531\u4e8en\u5f88\u5927\uff0c\u6211\u4eec\u53ef\u4ee5\u8003\u8651\u4e8c\u8fdb\u5236\u62c6\u5206<\/p>\n<p>\u500d\u589e\u6c42\u51faf[2^i][][]\uff0c\u7136\u540e\u5c06n\u7684\u4e8c\u8fdb\u5236\u4f4d\u662f1\u7684\u5408\u5e76\u8d77\u6765\u5c31\u597d\u4e86<\/p>\n<p>\u7136\u540e\u5c31\u662f\u8003\u8651\u5982\u4f55\u5408\u5e76\u4e24\u4e2a\u6570\u7ec4<\/p>\n<p>\u53ef\u4ee5\u5148\u679a\u4e3ek\uff0ck=k1+k2,\u7136\u540ep^2\u7684\u679a\u4e3e\u6bcf\u4e00\u4e2a\u4f59\u6570\u5c31\u597d<\/p>\n<p>\u6211\u4eec\u4e0d\u96be\u53d1\u73b0\u8fd9\u5c31\u662f\u4e00\u4e2a\u5377\u79ef<\/p>\n<p>\u7528NTT\u52a0\u901f\u5373\u53ef<\/p>\n<p>\u8fd9\u91cc\u590d\u6742\u5ea6\u662f\uff08p*mlogm+p^2 m\uff09\u7684\uff0c\u56e0\u4e3a\u6211\u4eec\u53ea\u9700\u8981\u4e00\u6b21\u6b63\u53d8\u6362\uff0c\u7136\u540e\u4e58\u5b8c\u4e4b\u540e\u518d\u53d8\u6362\u56de\u6765\u5373\u53ef<\/p>\n<p>\u6240\u4ee5\u603b\u590d\u6742\u5ea6\uff08p*mlogm+p^2 m\uff09logn<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:c++ decode:true\">#include&lt;map&gt;\r\n#include&lt;cmath&gt;\r\n#include&lt;queue&gt;\r\n#include&lt;cstdio&gt;\r\n#include&lt;cstring&gt;\r\n#include&lt;iostream&gt;\r\n#include&lt;algorithm&gt;\r\nusing namespace std;\r\n#define inf 1000000007\r\n#define mod 998244353\r\n#define ll long long\r\n#define N 4010\r\nint r[N],L=-1,G=3,nn;\r\nll inv;\r\nll ksm(ll a,int b)\r\n{\r\n\tll sum=1;\r\n\twhile(b)\r\n\t{\r\n\t\tif(b&amp;1) sum=sum*a%mod;\r\n\t\ta=a*a%mod;b&gt;&gt;=1;\r\n\t}\r\n\treturn sum;\r\n}\r\nll t,f[55][N],g[55][N],h[55][N];\r\nvoid NTT(ll *x,int f)\r\n{\r\n\tint i,j,k;\r\n\tll wn,w,X,Y;\r\n\tfor(i=0;i&lt;nn;i++) if(i&lt;r[i]) swap(x[i],x[r[i]]);\r\n\tfor(i=1;i&lt;nn;i&lt;&lt;=1)\r\n\t{\r\n\t\twn=ksm(G,(mod-1)\/(i&lt;&lt;1));\r\n\t\tfor(j=0;j&lt;nn;j+=(i&lt;&lt;1))\r\n\t\t{\r\n\t\t\tfor(k=0,w=1;k&lt;i;k++,w=w*wn%mod)\r\n\t\t\t{\r\n\t\t\t\tX=x[j+k];Y=w*x[j+k+i]%mod;\r\n\t\t\t\tx[j+k]=(X+Y)%mod;x[j+k+i]=(X-Y+mod)%mod;\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\tif(f==-1)\r\n\t{\r\n\t\treverse(x+1,x+nn);\r\n\t\tfor(i=0;i&lt;nn;i++) x[i]=x[i]*inv%mod;\r\n\t}\r\n}\r\nint n,m,p;\r\nvoid sol1()\r\n{\r\n\tregister int i,j,k;\r\n\tfor(i=0;i&lt;p;i++) NTT(f[i],1),NTT(g[i],1);\r\n\tmemset(h,0,sizeof(h));\r\n\tfor(i=0;i&lt;p;i++)\r\n\t\tfor(j=0;j&lt;p;j++)\r\n\t\t\tfor(k=0;k&lt;nn;k++) (h[(t*i+j)%p][k]+=f[i][k]*g[j][k])%=mod;\r\n\tfor(i=0;i&lt;p;i++)\r\n\t{\r\n\t\tNTT(h[i],-1),NTT(g[i],-1);\r\n\t\tfor(j=0;j&lt;=m;j++) f[i][j]=h[i][j];\r\n\t\tfor(j=m+1;j&lt;nn;j++) f[i][j]=0;\r\n\t}\r\n}\r\nvoid sol2()\r\n{\r\n\tregister int i,j,k;\r\n\tfor(i=0;i&lt;p;i++) NTT(g[i],1);\r\n\tmemset(h,0,sizeof(h));\r\n\tfor(i=0;i&lt;p;i++)\r\n\t\tfor(j=0;j&lt;p;j++)\r\n\t\t\tfor(k=0;k&lt;nn;k++) (h[(t*i+j)%p][k]+=g[i][k]*g[j][k])%=mod;\r\n\tfor(i=0;i&lt;p;i++)\r\n\t{\r\n\t\tNTT(h[i],-1);\r\n\t\tfor(j=0;j&lt;=m;j++) g[i][j]=h[i][j];\r\n\t\tfor(j=m+1;j&lt;nn;j++) g[i][j]=0;\r\n\t}\r\n}\r\nint main()\r\n{\r\n\tscanf(\"%d%d%d\",&amp;n,&amp;p,&amp;m);\r\n\tfor(nn=1;nn&lt;=m*2;nn&lt;&lt;=1) L++; inv=ksm(nn,mod-2);\r\n\tfor(int i=0;i&lt;nn;i++) r[i]=(r[i&gt;&gt;1]&gt;&gt;1)|((i&amp;1)&lt;&lt;L);\r\n\tt=10;f[0][0]=1;\r\n\tfor(int i=0;i&lt;=9&amp;&amp;i&lt;=m;i++) g[i%p][i]++;\r\n\twhile(n)\r\n\t{\r\n\t\tif(n&amp;1) sol1();\r\n\t\tsol2();n&gt;&gt;=1;t=t*t%p;\r\n\t}\r\n\tfor(int i=1;i&lt;=m;i++) (f[0][i]+=f[0][i-1])%=mod;\r\n\tfor(int i=0;i&lt;=m;i++) printf(\"%lld%c\",f[0][i],\" \\n\"[i==m]);\r\n\treturn 0;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<h4 class=\"ui top attached block header\"><\/h4>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>#6059. \u300c2017 \u5c71\u4e1c\u4e00\u8f6e\u96c6\u8bad Day1\u300dSum \u5185\u5b58\u9650\u5236\uff1a256 MiB\u00a0\u65f6\u95f4\u9650\u5236\uff1a1500 ms  [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[50],"tags":[38,51],"class_list":["post-486","post","type-post","status-publish","format-standard","hentry","category-loj","tag-fft","tag-51"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/486","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=486"}],"version-history":[{"count":1,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/486\/revisions"}],"predecessor-version":[{"id":488,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/486\/revisions\/488"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=486"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=486"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=486"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}