BM算法【实数模板】

BM递推杜教版是在整数取模的情况下的，

这个可以求解实数系数，但是可能有精度误差。

若一个问题的结论是通过推线性递推式来解，考虑到实际的情况，可以用BM算法的模板，先输入项数再依次输入项，项越多越准确（按道理，前k项的递推，只需要2*k 个初始项就能确定）

#include <bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i=int(a);i<int(b);++i)

#define mem(a,p) memset(a,p,sizeof(a))

#define MAXN 1005

struct BM

{

    int n{};

    vector<double> ps[MAXN];

    int pn{},fail[MAXN]{};

    double delta[MAXN]{};

    void Solve(const double *x,int n)

    {

        pn=;

        mem(fail,);

        mem(delta,);

        ps[].clear();

        rep(i,,n+)

        {

            double dt=-x[i];

            rep(j,,ps[pn].size())

                dt+=x[i-j-]*ps[pn][j];

            delta[i]=dt;

            if(fabs(dt)<=1e-)continue;

            fail[pn]=i;

            if(!pn)

            {

                ps[++pn].resize();

                continue;

            }

            vector<double> &ls=ps[pn-];

            double k=-dt/delta[fail[pn-]];

            vector<double> cur;

            cur.resize(i-fail[pn-]-);

            cur.push_back(-k);

            rep(j,,ls.size())cur.push_back(ls[j]*k);

            if(cur.size()<ps[pn].size())cur.resize(ps[pn].size());

            rep(j,,ps[pn].size())cur[j]+=ps[pn][j];

            ps[++pn]=cur;

        }

    }

    void print()

    {

        cout<<setiosflags(ios::fixed)<<setprecision();

        for(int i = ;i<ps[pn].size();++i)

        {

            cout<<ps[pn][i]<<" ";

        }

        cout<<endl;

    }

}B;

double x[MAXN];

int main()

{

    int n;

    while(cin>>n)

    {

        for(int i = ;i<=n;++i)

        {

            cin>>x[i];

        }

        B.Solve(x,n);

        B.print();

    }

}

Code From:

https://www.haoyuan.info/?p=300