library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Shift of Sampling Points of Polynomial
(FPS/samplepointshift.hpp)

• View this file on GitHub
• Last update: 2024-10-22 03:59:04+09:00
• Include: #include "FPS/samplepointshift.hpp"

Depends on

• Combination (Math/comb.hpp)

Required by

• Factorial (Large) (FPS/factlarge.hpp)
• P-recursive (FPS/p-recursive.hpp)

Verified with

• Verify/LC_many_factorials.test.cpp
• Verify/LC_shift_of_sampling_points_of_polynomial.test.cpp

Code

#pragma once
#include "Math/comb.hpp"

template <typename T>
Poly<T> SamplePointsShift(vector<T> &ys, T c, int m = -1) {
    ll n = ys.size() - 1, C = c.v % T::get_mod();
    if (m == -1)
        m = n + 1;
    if (C <= n) {
        Poly<T> res;
        rep(i, C, n + 1) res.push_back(ys[i]);
        if (int(res.size()) >= m) {
            res.resize(m);
            return res;
        }
        auto add = SamplePointsShift<T>(ys, n + 1, m - res.size());
        for (int i = 0; int(res.size()) < m; i++) {
            res.push_back(add[i]);
        }
        return res;
    }
    if (C + m > T::get_mod()) {
        auto res = SamplePointsShift<T>(ys, c, T::get_mod() - c.v);
        auto add = SamplePointsShift<T>(ys, 0, m - res.size());
        rep(i, 0, add.size()) res.push_back(add[i]);
        return res;
    }

    Poly<T> A(n + 1), B(m + n);
    rep(i, 0, n + 1) {
        A[i] = ys[i] * Fact<T>(i, 1) * Fact<T>(n - i, 1);
        if ((n - i) & 1)
            A[i] = -A[i];
    }
    rep(i, 0, m + n) B[i] = Fp(1) / (c - n + i);
    auto AB = A * B;
    vector<T> res(m);
    Fp base = 1;
    rep(x, 0, n + 1) base *= (c - x);
    rep(i, 0, m) {
        res[i] = AB[n + i] * base;
        base *= (c + i + 1);
        base *= B[i];
    }
    return res;
}

/**
 * @brief Shift of Sampling Points of Polynomial
 */

#line 2 "Math/comb.hpp"

template <typename T> T Inv(ll n) {
    static int md;
    static vector<T> buf({0, 1});
    if (md != T::get_mod()) {
        md = T::get_mod();
        buf = vector<T>({0, 1});
    }
    assert(n > 0);
    n %= md;
    while (SZ(buf) <= n) {
        int k = SZ(buf), q = (md + k - 1) / k;
        buf.push_back(buf[k * q - md] * q);
    }
    return buf[n];
}

template <typename T> T Fact(ll n, bool inv = 0) {
    static int md;
    static vector<T> buf({1, 1}), ibuf({1, 1});
    if (md != T::get_mod()) {
        md = T::get_mod();
        buf = ibuf = vector<T>({1, 1});
    }
    assert(n >= 0 and n < md);
    while (SZ(buf) <= n) {
        buf.push_back(buf.back() * SZ(buf));
        ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));
    }
    return inv ? ibuf[n] : buf[n];
}

template <typename T> T nPr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nCr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);
}
// sum = n, r tuples
template <typename T> T nHr(int n, int r, bool inv = 0) {
    return nCr<T>(n + r - 1, r - 1, inv);
}
// sum = n, a nonzero tuples and b tuples
template <typename T> T choose(int n, int a, int b) {
    if (n == 0)
        return !a;
    return nCr<T>(n + b - 1, a + b - 1);
}

/**
 * @brief Combination
 */
#line 3 "FPS/samplepointshift.hpp"

template <typename T>
Poly<T> SamplePointsShift(vector<T> &ys, T c, int m = -1) {
    ll n = ys.size() - 1, C = c.v % T::get_mod();
    if (m == -1)
        m = n + 1;
    if (C <= n) {
        Poly<T> res;
        rep(i, C, n + 1) res.push_back(ys[i]);
        if (int(res.size()) >= m) {
            res.resize(m);
            return res;
        }
        auto add = SamplePointsShift<T>(ys, n + 1, m - res.size());
        for (int i = 0; int(res.size()) < m; i++) {
            res.push_back(add[i]);
        }
        return res;
    }
    if (C + m > T::get_mod()) {
        auto res = SamplePointsShift<T>(ys, c, T::get_mod() - c.v);
        auto add = SamplePointsShift<T>(ys, 0, m - res.size());
        rep(i, 0, add.size()) res.push_back(add[i]);
        return res;
    }

    Poly<T> A(n + 1), B(m + n);
    rep(i, 0, n + 1) {
        A[i] = ys[i] * Fact<T>(i, 1) * Fact<T>(n - i, 1);
        if ((n - i) & 1)
            A[i] = -A[i];
    }
    rep(i, 0, m + n) B[i] = Fp(1) / (c - n + i);
    auto AB = A * B;
    vector<T> res(m);
    Fp base = 1;
    rep(x, 0, n + 1) base *= (c - x);
    rep(i, 0, m) {
        res[i] = AB[n + i] * base;
        base *= (c + i + 1);
        base *= B[i];
    }
    return res;
}

/**
 * @brief Shift of Sampling Points of Polynomial
 */

Back to top page