{"id":300,"date":"2018-06-08T16:58:24","date_gmt":"2018-06-08T16:58:24","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=300"},"modified":"2018-06-08T16:58:24","modified_gmt":"2018-06-08T16:58:24","slug":"bm%e7%ae%97%e6%b3%95%e6%b1%82%e7%ba%bf%e6%80%a7%e9%80%92%e6%8e%a8%e5%bc%8f%e6%a8%a1%e6%9d%bf","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=300","title":{"rendered":"BM\u7b97\u6cd5\u6c42\u7ebf\u6027\u9012\u63a8\u5f0f\u6a21\u677f"},"content":{"rendered":"<p>\u82e5\u4e00\u4e2a\u95ee\u9898\u7684\u7ed3\u8bba\u662f\u901a\u8fc7\u63a8\u7ebf\u6027\u9012\u63a8\u5f0f\u6765\u89e3\uff0c\u8003\u8651\u5230\u5b9e\u9645\u7684\u60c5\u51b5\uff0c\u53ef\u4ee5\u7528BM\u7b97\u6cd5\u7684\u6a21\u677f\uff0c\u5148\u8f93\u5165\u9879\u6570\u518d\u4f9d\u6b21\u8f93\u5165\u9879\uff0c\u9879\u8d8a\u591a\u8d8a\u51c6\u786e<\/p>\n<pre><code>#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\n\n#define rep(i,a,b) for(int i=int(a);i&lt;int(b);++i)\n\n#define mem(a,p) memset(a,p,sizeof(a))\n\n#define MAXN 1005\n\nstruct BM\n{\n    int n{};\n\n    vector&lt;double&gt; ps[MAXN];\n    int pn{},fail[MAXN]{};\n    double delta[MAXN]{};\n\n    void Solve(const double *x,int n)\n    {\n        pn=0;\n        mem(fail,0);\n        mem(delta,0);\n        ps[0].clear();\n        rep(i,1,n+1)\n        {\n            double dt=-x[i];\n            rep(j,0,ps[pn].size())\n                dt+=x[i-j-1]*ps[pn][j];\n            delta[i]=dt;\n            if(fabs(dt)&lt;=1e-8)continue;\n            fail[pn]=i;\n            if(!pn)\n            {\n                ps[++pn].resize(1);\n                continue;\n            }\n            vector&lt;double&gt; &amp;ls=ps[pn-1];\n            double k=-dt\/delta[fail[pn-1]];\n            vector&lt;double&gt; cur;\n            cur.resize(i-fail[pn-1]-1);\n            cur.push_back(-k);\n            rep(j,0,ls.size())cur.push_back(ls[j]*k);\n            if(cur.size()&lt;ps[pn].size())cur.resize(ps[pn].size());\n            rep(j,0,ps[pn].size())cur[j]+=ps[pn][j];\n            ps[++pn]=cur;\n        }\n    }\n\n    void print()\n    {\n        cout&lt;&lt;setiosflags(ios::fixed)&lt;&lt;setprecision(10);\n        for(int i = 0;i&lt;ps[pn].size();++i)\n        {\n            cout&lt;&lt;ps[pn][i]&lt;&lt;\" \";\n        }\n        cout&lt;&lt;endl;\n    }\n}B;\n\ndouble x[MAXN];\n\nint main()\n{\n    int n;\n    while(cin&gt;&gt;n)\n    {\n        for(int i = 1;i&lt;=n;++i)\n        {\n            cin&gt;&gt;x[i];\n        }\n        B.Solve(x,n);\n        B.print();\n    }\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u82e5\u4e00\u4e2a\u95ee\u9898\u7684\u7ed3\u8bba\u662f\u901a\u8fc7\u63a8\u7ebf\u6027\u9012\u63a8\u5f0f\u6765\u89e3\uff0c\u8003\u8651\u5230\u5b9e\u9645\u7684\u60c5\u51b5\uff0c\u53ef\u4ee5\u7528BM\u7b97\u6cd5\u7684\u6a21\u677f\uff0c\u5148\u8f93\u5165\u9879\u6570\u518d\u4f9d\u6b21\u8f93\u5165\u9879\uff0c\u9879\u8d8a\u591a [&hellip;]<\/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":[22],"tags":[],"class_list":["post-300","post","type-post","status-publish","format-standard","hentry","category-22"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-4Q","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/300","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=300"}],"version-history":[{"count":1,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/300\/revisions"}],"predecessor-version":[{"id":301,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/300\/revisions\/301"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=300"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=300"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=300"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}