2018-team4-modules/BM

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define SZ 10010
int n;
typedef double ld;
typedef vector<ld> vld;
vld ps[2333];
int pn = 0, fail[SZ];
ld x[SZ], delta[SZ];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf", x + i);
    for (int i = 1; i <= n; i++)
    {
        ld dt = -x[i];
        for (int j = 0; j < ps[pn].size(); j++)
            dt += x[i - j - 1] * ps[pn][j];
        delta[i] = dt;
        if (fabs(dt) <= 1e-7)
            continue;
        fail[pn] = i;
        if (!pn)
        {
            ps[++pn].resize(i);
            continue;
        } 
        vld &ls = ps[pn - 1];
        ld k = -dt / delta[fail[pn - 1]];
        vld cur;
        cur.resize(i - fail[pn - 1] - 1); //trailing 0
        cur.pb(-k);
        for (int j = 0; j < ls.size(); j++)
            cur.pb(ls[j] * k);
        if (cur.size() < ps[pn].size())
            cur.resize(ps[pn].size());
        for (int j = 0; j < ps[pn].size(); j++)
            cur[j] += ps[pn][j];
        ps[++pn] = cur;
    }
    for (unsigned g = 0; g < ps[pn].size(); g++)
        cout << ps[pn][g] << " ";
    puts("");
}
}}}

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define SZ 10010
int n;
typedef double ld;
typedef vector<ld> vld;
vld ps[2333];
int pn = 0, fail[SZ];
ld x[SZ], delta[SZ];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf", x + i);
    for (int i = 1; i <= n; i++)
    {
        ld dt = -x[i];
        for (int j = 0; j < ps[pn].size(); j++)
            dt += x[i - j - 1] * ps[pn][j];
        delta[i] = dt;
        if (fabs(dt) <= 1e-7)
            continue;
        fail[pn] = i;
        if (!pn)
        {
            ps[++pn].resize(i);
            continue;
        } 
        vld &ls = ps[pn - 1];
        ld k = -dt / delta[fail[pn - 1]];
        vld cur;
        cur.resize(i - fail[pn - 1] - 1); //trailing 0
        cur.pb(-k);
        for (int j = 0; j < ls.size(); j++)
            cur.pb(ls[j] * k);
        if (cur.size() < ps[pn].size())
            cur.resize(ps[pn].size());
        for (int j = 0; j < ps[pn].size(); j++)
            cur[j] += ps[pn][j];
        ps[++pn] = cur;
    }
    for (unsigned g = 0; g < ps[pn].size(); g++)
        cout << ps[pn][g] << " ";
    puts("");
}