cp-library-cpp

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

View the Project on GitHub NotLeonian/cp-library-cpp

:heavy_check_mark: test/src/polynomial/lagrange_interpolation/cumulative_sum.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc208/tasks/abc208_f"

#include <iostream>
#include <atcoder/modint>

#include "library/polynomial/lagrange_interpolation.hpp"
#include "library/sequence/powers.hpp"

using mint = atcoder::modint1000000007;

int main() {
    long long n;
    int m, k;
    std::cin >> n >> m >> k;

    std::vector<mint> f = suisen::powers<mint>(k + m, k);
    for (int loop = 0; loop < m; ++loop) {
        for (int i = 1; i <= k + m; ++i) f[i] += f[i - 1];
    }

    std::cout << suisen::lagrange_interpolation_arithmetic_progression<mint>(f, n).val() << '\n';

    return 0;
}
#line 1 "test/src/polynomial/lagrange_interpolation/cumulative_sum.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc208/tasks/abc208_f"

#include <iostream>
#include <atcoder/modint>

#line 1 "library/polynomial/lagrange_interpolation.hpp"



#line 1 "library/math/product_of_differences.hpp"



#include <deque>
#line 1 "library/polynomial/multi_point_eval.hpp"



#include <vector>

namespace suisen {
    template <typename FPSType, typename T>
    std::vector<typename FPSType::value_type> multi_point_eval(const FPSType& f, const std::vector<T>& xs) {
        int n = xs.size();
        if (n == 0) return {};
        std::vector<FPSType> seg(2 * n);
        for (int i = 0; i < n; ++i) seg[n + i] = FPSType{ -xs[i], 1 };
        for (int i = n - 1; i > 0; --i) seg[i] = seg[i * 2] * seg[i * 2 + 1];
        seg[1] = f % seg[1];
        for (int i = 2; i < 2 * n; ++i) seg[i] = seg[i / 2] % seg[i];
        std::vector<typename FPSType::value_type> ys(n);
        for (int i = 0; i < n; ++i) ys[i] = seg[n + i].size() ? seg[n + i][0] : 0;
        return ys;
    }
} // namespace suisen


#line 6 "library/math/product_of_differences.hpp"

namespace suisen {
    /**
     * O(N(logN)^2)
     * return the vector p of length xs.size() s.t. p[i]=Π[j!=i](x[i]-x[j])
     */
    template <typename FPSType, typename T>
    std::vector<typename FPSType::value_type> product_of_differences(const std::vector<T>& xs) {
        // f(x):=Π_i(x-x[i])
        // => f'(x)=Σ_i Π[j!=i](x-x[j])
        // => f'(x[i])=Π[j!=i](x[i]-x[j])
        const int n = xs.size();
        std::deque<FPSType> dq;
        for (int i = 0; i < n; ++i) dq.push_back(FPSType{ -xs[i], 1 });
        while (dq.size() >= 2) {
            auto f = std::move(dq.front());
            dq.pop_front();
            auto g = std::move(dq.front());
            dq.pop_front();
            dq.push_back(f * g);
        }
        auto f = std::move(dq.front());
        f.diff_inplace();
        return multi_point_eval<FPSType, T>(f, xs);
    }
} // namespace suisen



#line 5 "library/polynomial/lagrange_interpolation.hpp"

namespace suisen {
    // O(N^2+NlogP)
    template <typename T>
    T lagrange_interpolation_naive(const std::vector<T>& xs, const std::vector<T>& ys, const T t) {
        const int n = xs.size();
        assert(int(ys.size()) == n);

        T p{ 1 };
        for (int i = 0; i < n; ++i) p *= t - xs[i];

        T res{ 0 };
        for (int i = 0; i < n; ++i) {
            T w = 1;
            for (int j = 0; j < n; ++j) if (j != i) w *= xs[i] - xs[j];
            res += ys[i] * (t == xs[i] ? 1 : p / (w * (t - xs[i])));
        }
        return res;
    }

    // O(N(logN)^2+NlogP)
    template <typename FPSType, typename T>
    typename FPSType::value_type lagrange_interpolation(const std::vector<T>& xs, const std::vector<T>& ys, const T t) {
        const int n = xs.size();
        assert(int(ys.size()) == n);

        std::vector<FPSType> seg(2 * n);
        for (int i = 0; i < n; ++i) seg[n + i] = FPSType {-xs[i], 1};
        for (int i = n - 1; i > 0; --i) seg[i] = seg[i * 2] * seg[i * 2 + 1];
        seg[1] = seg[1].diff() % seg[1];
        for (int i = 2; i < 2 * n; ++i) seg[i] = seg[i / 2] % seg[i];

        using mint = typename FPSType::value_type;
        mint p{ 1 };
        for (int i = 0; i < n; ++i) p *= t - xs[i];

        mint res{ 0 };
        for (int i = 0; i < n; ++i) {
            mint w = seg[n + i][0];
            res += ys[i] * (t == xs[i] ? 1 : p / (w * (t - xs[i])));
        }
        return res;
    }

    // xs[i] = ai + b
    // requirement: for all 0≤i<j<n, ai+b ≢ aj+b mod p
    template <typename T>
    T lagrange_interpolation_arithmetic_progression(T a, T b, const std::vector<T>& ys, const T t) {
        const int n = ys.size();
        T fac = 1;
        for (int i = 1; i < n; ++i) fac *= i;
        std::vector<T> fac_inv(n), suf(n);
        fac_inv[n - 1] = T(1) / fac;
        suf[n - 1] = 1;
        for (int i = n - 1; i > 0; --i) {
            fac_inv[i - 1] = fac_inv[i] * i;
            suf[i - 1] = suf[i] * (t - (a * i + b));
        }
        T pre = 1, res = 0;
        for (int i = 0; i < n; ++i) {
            T val = ys[i] * pre * suf[i] * fac_inv[i] * fac_inv[n - i - 1];
            if ((n - 1 - i) & 1) res -= val;
            else                 res += val;
            pre *= t - (a * i + b);
        }
        return res / a.pow(n - 1);
    }
    // x = 0, 1, ...
    template <typename T>
    T lagrange_interpolation_arithmetic_progression(const std::vector<T>& ys, const T t) {
        return lagrange_interpolation_arithmetic_progression(T{1}, T{0}, ys, t);
    }
} // namespace suisen



#line 1 "library/sequence/powers.hpp"



#include <cstdint>
#line 1 "library/number/linear_sieve.hpp"



#include <cassert>
#include <numeric>
#line 7 "library/number/linear_sieve.hpp"

namespace suisen {
// reference: https://37zigen.com/linear-sieve/
class LinearSieve {
    public:
        LinearSieve(const int n) : _n(n), min_prime_factor(std::vector<int>(n + 1)) {
            std::iota(min_prime_factor.begin(), min_prime_factor.end(), 0);
            prime_list.reserve(_n / 20);
            for (int d = 2; d <= _n; ++d) {
                if (min_prime_factor[d] == d) prime_list.push_back(d);
                const int prime_max = std::min(min_prime_factor[d], _n / d);
                for (int prime : prime_list) {
                    if (prime > prime_max) break;
                    min_prime_factor[prime * d] = prime;
                }
            }
        }
        int prime_num() const noexcept { return prime_list.size(); }
        /**
         * Returns a vector of primes in [0, n].
         * It is guaranteed that the returned vector is sorted in ascending order.
         */
        const std::vector<int>& get_prime_list() const noexcept  {
            return prime_list;
        }
        const std::vector<int>& get_min_prime_factor() const noexcept { return min_prime_factor; }
        /**
         * Returns a vector of `{ prime, index }`.
         * It is guaranteed that the returned vector is sorted in ascending order.
         */
        std::vector<std::pair<int, int>> factorize(int n) const noexcept {
            assert(0 < n and n <= _n);
            std::vector<std::pair<int, int>> prime_powers;
            while (n > 1) {
                int p = min_prime_factor[n], c = 0;
                do { n /= p, ++c; } while (n % p == 0);
                prime_powers.emplace_back(p, c);
            }
            return prime_powers;
        }
    private:
        const int _n;
        std::vector<int> min_prime_factor;
        std::vector<int> prime_list;
};
} // namespace suisen


#line 6 "library/sequence/powers.hpp"

namespace suisen {
    // returns { 0^k, 1^k, ..., n^k }
    template <typename mint>
    std::vector<mint> powers(uint32_t n, uint64_t k) {
        const auto mpf = LinearSieve(n).get_min_prime_factor();
        std::vector<mint> res(n + 1);
        res[0] = k == 0;
        for (uint32_t i = 1; i <= n; ++i) res[i] = i == 1 ? 1 : uint32_t(mpf[i]) == i ? mint(i).pow(k) : res[mpf[i]] * res[i / mpf[i]];
        return res;
    }
} // namespace suisen


#line 8 "test/src/polynomial/lagrange_interpolation/cumulative_sum.test.cpp"

using mint = atcoder::modint1000000007;

int main() {
    long long n;
    int m, k;
    std::cin >> n >> m >> k;

    std::vector<mint> f = suisen::powers<mint>(k + m, k);
    for (int loop = 0; loop < m; ++loop) {
        for (int i = 1; i <= k + m; ++i) f[i] += f[i - 1];
    }

    std::cout << suisen::lagrange_interpolation_arithmetic_progression<mint>(f, n).val() << '\n';

    return 0;
}
Back to top page