< hamamuさんのAI生成コード置き場

ラグランジュ補間

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

//generated by GPT-5.6 Terra, modified by hamamu
template<class MINT>
struct LagrangeInterpolation{
  using ll = long long;

  // 補間に使う点の範囲と、その点での関数値を保存する。
  ll sx,ex;
  vector<MINT> ys;

  // cs[i] は i 番目のラグランジュ基底多項式に掛かる係数。
  vector<MINT> cs;

  // CMB は cmb.finv(i) で 1/i! を返せる型であればよい。
  template<class CMB>
  LagrangeInterpolation(ll sx,ll ex,const vector<MINT> &ys,CMB &cmb)
      :sx(sx),ex(ex),ys(ys)
  {
    // 補間点の範囲と、各点での値が矛盾しないことを確認する。
    assert(sx<=ex);
    assert((ll)ys.size()==ex-sx+1);

    // i 番目の基底多項式の分母を逆元化して係数へ取り込む。
    cs.resize(ex-sx+1);
    for(ll i=0;i<=ex-sx;++i){
      cs[i]=ys[i]*cmb.finv(i)*cmb.finv(ex-sx-i);
      if((ex-sx-i)&1) cs[i]=-cs[i];
    }
  }

  // 前後積を使い、各項から i 番目の因子だけを除いた積を O(1) で得る。
  // 全体として O(ex-sx+1) で補間多項式の値を返す。
  MINT get(ll x)const{
    // 補間に使った点は、そのまま保存値を返せる。
    if(sx<=x && x<=ex) return ys[x-sx];

    const ll pointCount=ex-sx+1;
    vector<MINT> lprod(pointCount+1,MINT(1));
    vector<MINT> rprod(pointCount+1,MINT(1));

    // lprod[i] = (x-sx)(x-(sx+1))...(x-(sx+i-1))。
    for(ll i=0;i<pointCount;++i){
      lprod[i+1]=lprod[i]*MINT(x-(sx+i));
    }

    // rprod[i] = (x-(sx+i))...(x-ex)。
    for(ll i=pointCount;i>0;--i){
      rprod[i-1]=rprod[i]*MINT(x-(sx+i-1));
    }

    // i 番目の因子を除いた積に、前計算済み係数を掛けて足し合わせる。
    MINT result=0;
    for(ll i=0;i<pointCount;++i){
      result+=cs[i]*lprod[i]*rprod[i+1];
    }
    return result;
  }
};
/*
- ---- ラグランジュ補間 ----
ll sx=0, ex=4;                         // 補間点は sx,sx+1,...,ex
vector<mll> ys={5,9,15,23,33};         // ys[i]=f(sx+i)
combination<mll> cmb(ex-sx);           // cmb.finv(i) のみ使われる
LagrangeInterpolation<mll> li(sx,ex,ys,cmb);

mll result=li.get(10);                 // f(10) を O(N:補間点数) で計算
*/