test/combination.aoj.DPL_5_G.test.cpp

View this file on GitHub
Last update: 2020-05-13 18:08:04+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_5_G

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_5_G"

#include <iostream>
#include "../lib/modint.hpp"
#include "../lib/combination.hpp"

int main() {
    init_fact();
    int n, k; std::cin >> n >> k;
    Mint ans = 0;
    for (int j = 1; j <= k; j++) {
        Mint cnt = 0;
        for (int i = 0; i < j; i++) {
            cnt += Mint(i&1 ? -1 : 1)*C(j, i)*pow(Mint(j - i), (long long)n);
        }
        cnt *= inv[j];
        ans += cnt;
    }
    std::cout << ans << std::endl;
    return 0;
}

#line 1 "test/combination.aoj.DPL_5_G.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_5_G"

#include <iostream>
#line 1 "lib/modint.hpp"



#line 5 "lib/modint.hpp"

// Modint
struct Mint {
    static const long long mod = (long long)1e9 + 7;
    long long val;

    Mint() { val = 0; }
    Mint(long long a) { val = a; verify_value(); }

    void verify_value() {
        if (val >= mod) val %= mod;
        if (val < 0) val %= mod, val += mod;
    }

    Mint pow(long long p) const {
        Mint cur = Mint(val), ret = 1;
        while (p > 0) {
            if (p & 1) ret *= cur;
            cur *= cur;
            p >>= 1LL;
        }
        return ret;
    }
    Mint inv() const {
        if (val == 0)
            std::cerr << "WARNING: inv() is called with 0." << std::endl;
        return pow(mod - 2);
    }

    Mint operator+() const { return *this; }
    Mint operator-() const { return Mint(mod - val); }

    Mint operator+=(const Mint &a) {
        val += a.val;
        if (val >= mod) val -= mod;
        return Mint(val);
    }
    Mint operator*=(const Mint &a) {
        val *= a.val;
        if (val >= mod) val %= mod;
        return Mint(val);
    }
    Mint operator-=(const Mint &a) { return *this += -a; }
    Mint operator/=(const Mint &a) { return *this *= a.inv(); }

    Mint operator++() { return *this += Mint(1); }
    Mint operator--() { return *this -= Mint(1); }
    Mint operator++(int) {
        Mint ret = *this;
        ++(*this);
        return ret;
    }
    Mint operator--(int) {
        Mint ret = *this;
        --(*this);
        return ret;
    }

    operator long long() const { return val; }
};

Mint operator+(const Mint &a, const Mint &b) {
    long long ret = a.val + b.val;
    if (ret >= Mint::mod) ret -= Mint::mod;
    return Mint(ret);
}
Mint operator*(const Mint &a, const Mint &b) {
    long long ret = a.val * b.val;
    if (ret >= Mint::mod) ret %= Mint::mod;
    return Mint(ret);
}
Mint operator-(const Mint &a, const Mint &b) { return a + (-b); }
Mint operator/(const Mint &a, const Mint &b) { return a * b.inv(); }

std::ostream &operator<<(std::ostream &out, const Mint &a) { return out << a.val; }
std::istream &operator>>(std::istream &in, Mint &a) {
    in >> a.val;
    a.verify_value();
    return in;
}

Mint pow(Mint a, long long b) {
    return a.pow(b);
}


#line 1 "lib/combination.hpp"



#line 5 "lib/combination.hpp"
#include <vector>

constexpr int MAX_N = 2000003;
std::vector<Mint> fact(MAX_N), inv(MAX_N);

void init_fact() {
    fact[0] = inv[0] = 1;
    for (long long i = 1; i < MAX_N; i++) {
        fact[i] = fact[i - 1] * Mint(i);
        inv[i] = fact[i].inv();
    }
}

// aCb
Mint C(int a, int b) {
    if (a < 0 || b < 0 || a < b) return 0;
    Mint res = fact[a];
    res *= inv[b];
    res *= inv[a - b];
    return res;
}

// aPb
Mint P(int a, int b) {
    if (a < 0 || a < b) return 0;
    return fact[a] * inv[a - b];
}

// aHb
Mint H(int a, int b) {
    if (b == 0) return 1;
    return C(a + b - 1, b);
}


#line 6 "test/combination.aoj.DPL_5_G.test.cpp"

int main() {
    init_fact();
    int n, k; std::cin >> n >> k;
    Mint ans = 0;
    for (int j = 1; j <= k; j++) {
        Mint cnt = 0;
        for (int i = 0; i < j; i++) {
            cnt += Mint(i&1 ? -1 : 1)*C(j, i)*pow(Mint(j - i), (long long)n);
        }
        cnt *= inv[j];
        ans += cnt;
    }
    std::cout << ans << std::endl;
    return 0;
}