拉格朗日插值(多项式快速插值)(多项式全家桶)

最近在学多项式,想起来一个月前写的一道拉格朗日,特来水贴

板子

实现方法_oiwiki
感觉写了个野路子,也可能是我太菜了
先orz jiangly
jiangly sama的多项式板子

using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
   
    T res = 1;
    for (; b; b /= 2, a *= a) {
   
        if (b % 2) {
   
            res *= a;
        }
    }
    return res;
}
 
template<int P>
struct MInt {
   
    int x;
    constexpr MInt() : x{
   } {
   }
    constexpr MInt(i64 x) : x{
   norm(x % getMod())} {
   }
    
    static int Mod;
    constexpr static int getMod() {
   
        if (P > 0) {
   
            return P;
        } else {
   
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
   
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
   
        if (x < 0) {
   
            x += getMod();
        }
        if (x >= getMod()) {
   
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
   
        return x;
    }
    explicit constexpr operator int() const {
   
        return x;
    }
    constexpr MInt operator-() const {
   
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
   
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
   
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
   
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
   
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
   
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
   
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
   
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
   
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
   
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
   
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
   
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
   
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
   
        return lhs.val() != rhs.val();
    }
};
 
template<>
int MInt<0>::Mod = 1;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1e6 + 3;
using Z = MInt<P>;

std::vector<int> rev;
template<int P>
std::vector<MInt<P>> roots{
   0, 1};

template<int P>
constexpr MInt<P> findPrimitiveRoot() {
   
    MInt<P> i = 2;
    int k = __builtin_ctz(P - 1);
    while (true) {
   
        if (power(i, (P - 1) / 2) != 1) {
   
            break;
        }
        i += 1;
    }
    return power(i, (P - 1) >> k);
}
 
template<int P>
constexpr MInt<P> primitiveRoot = findPrimitiveRoot<P>();
 
template<>
constexpr MInt<998244353> primitiveRoot<998244353> {
   31};
 
template<int P>
constexpr void dft(std::vector<MInt<P>> &a) {
   
    int n = a.size();
    
    if (int(rev.size()) != n) {
   
        int k = __builtin_ctz(n) - 1;
        rev.resize(n);
        for (int i = 0; i < n; i++) {
   
            rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
        }
    }
    
    for (int i = 0; i < n; i++) {
   
        if (rev[i] < i) {
   
            std::swap(a[i], a[rev[i]]);
        }
    }
    if (roots<P>.size() < n) {