test/yukicoder/665.test.cpp

View this file on GitHub
Last update: 2026-10-27 12:32:30+09:00
Problem: https://yukicoder.me/problems/no/665

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/665"
#include <atcoder/modint>
#include <iostream>
#include <vector>

#include "math/lagrange_interpolation.hpp"
using mint = atcoder::modint1000000007;
int main() {
    long long n;
    int k;
    std::cin >> n >> k;
    std::vector<mint> y(k + 2);
    for (int i = 1; i <= k + 1; i++) y[i] = y[i - 1] + mint(i).pow(k);
    std::cout << lagrange_interpolation(y, mint(n)).val() << '\n';
}

#line 1 "test/yukicoder/665.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/665"
#include <atcoder/modint>
#include <iostream>
#include <vector>

#line 2 "math/lagrange_interpolation.hpp"
#include <cassert>
#line 4 "math/lagrange_interpolation.hpp"

#line 4 "math/combinatorics.hpp"
template <typename mint>
struct combinatorics {
    static mint fact(int n) {
        ensure(n);
        return facts[n];
    }
    static mint fact_inv(int n) {
        ensure(n);
        return ifacts[n];
    }
    static mint inv(int n) {
        assert(1 <= n);
        ensure(n);
        return ifacts[n] * facts[n - 1];
    }
    static mint C(int n, int k) {
        if (n < 0 || n < k || k < 0) return 0;
        return fact(n) * fact_inv(n - k) * fact_inv(k);
    }
    static mint P(int n, int k) {
        if (n < 0 || n < k || k < 0) return 0;
        return fact(n) * fact_inv(n - k);
    }
    static mint H(int n, int k) {
        if (n < 0 || k < 0) return 0;
        if (k == 0) return 1;
        return C(n + k - 1, k);
    }
    static void ensure(int n) {
        assert(n < mint::mod());
        int sz = facts.size();
        if (sz > n) return;
        if (n < sz << 1) n = std::min(mint::mod() - 1, sz << 1);
        facts.resize(n + 1);
        ifacts.resize(n + 1);
        for (int i = sz; i <= n; i++) facts[i] = facts[i - 1] * i;
        ifacts[n] = facts[n].inv();
        for (int i = n; i >= sz; i--) ifacts[i - 1] = ifacts[i] * i;
    }

private:
    static inline std::vector<mint> facts{1};
    static inline std::vector<mint> ifacts{1};
};
#line 6 "math/lagrange_interpolation.hpp"
template <class mint> mint lagrange_interpolation(const std::vector<mint>& y, mint c) {
    int n = int(y.size());
    assert(n >= 1);
    long long cv = c.val();
    if (cv < n) return y[cv];
    std::vector<mint> pre(n + 1, 1), suf(n + 1, 1);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] * (c - i);
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] * (c - i);
    using comb = combinatorics<mint>;
    mint ret = 0;
    for (int i = 0; i < n; i++) {
        mint t = y[i] * pre[i] * suf[i + 1] * comb::fact_inv(i) * comb::fact_inv(n - 1 - i);
        ret += (n - 1 - i) & 1 ? -t : t;
    }
    return ret;
}
template <class mint>
mint lagrange_interpolation(const std::vector<mint>& x, const std::vector<mint>& y, mint c) {
    int n = int(x.size());
    assert(n >= 1 && int(y.size()) == n);
    mint ret = 0;
    for (int i = 0; i < n; i++) {
        mint num = 1, den = 1;
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            assert(x[i] != x[j]);
            num *= c - x[j];
            den *= x[i] - x[j];
        }
        ret += y[i] * num / den;
    }
    return ret;
}
#line 7 "test/yukicoder/665.test.cpp"
using mint = atcoder::modint1000000007;
int main() {
    long long n;
    int k;
    std::cin >> n >> k;
    std::vector<mint> y(k + 2);
    for (int i = 1; i <= k + 1; i++) y[i] = y[i - 1] + mint(i).pow(k);
    std::cout << lagrange_interpolation(y, mint(n)).val() << '\n';
}