yukicoder No.391 CODING WAR

写像12相の

• 玉は区別する
• 箱も区別する
• 各箱の玉は 1 個以上

という場合の問題！！！

問題へのリンク

問題概要

個の互いに区別できる玉を、 個の互いに区別できる箱に入れる。

ただし、どの箱についても玉が 1 個以上入るようにするな方法が何通りあるか、1000000007 で割ったあまりを求めよ。

制約

• 
• 

解法

写像12相そのもので、これと同じ！！！

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_5_C&lang=jpjudge.u-aizu.ac.jp

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;


// modint
// 1000000007 で割ったあまりに関する四則演算を直感的に行える
template<int MODULO> struct Fp {
    long long val;

    constexpr Fp(long long v = 0) noexcept : val(v % MODULO) {
        if (val < 0) v += MODULO;
    }
    constexpr Fp operator - () const noexcept {
        return val ? MODULO - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MODULO) val -= MODULO;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MODULO;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MODULO;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MODULO, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MODULO;
        if (val < 0) val += MODULO;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
};

template<int MODULO> constexpr ostream& operator <<
(ostream &os, const Fp<MODULO>& x) noexcept {
    return os << x.val;
}
template<int MODULO> constexpr istream& operator >>
(istream &is, Fp<MODULO>& x) noexcept {
    return is >> x.val;
}

template<int MODULO> constexpr Fp<MODULO> modpow
(const Fp<MODULO> &a, long long n) noexcept {
    if (n == 0) return 1;
    auto t = modpow(a, n / 2);
    t = t * t;
    if (n & 1) t = t * a;
    return t;
}


// 二項係数ライブラリ
template<int MODULO> struct BiCoef {
    vector<Fp<MODULO> > fac, inv, finv;
    constexpr BiCoef(int n) noexcept : fac(n, 1), inv(n, 1), finv(n, 1) {
        for(int i = 2; i < n; i++){
            fac[i] = fac[i-1] * i;
            inv[i] = -inv[MODULO%i] * (MODULO/i);
            finv[i] = finv[i-1] * inv[i];
        }
    }
    constexpr Fp<MODULO> com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fac[n] * finv[k] * finv[n-k];
    }
};



// ここから解答
const int MAX = 201010;
const int MOD = 1000000007;
using mint = Fp<MOD>; // mod 計算を直感的に

int main() {
    BiCoef<MOD> bc(MAX); // 二項係数計算の前処理

    long long N, K;
    cin >> N >> K;
    mint res = 0;
    for (int i = 0; i <= K; ++i) {
        mint tmp = bc.com(K, i) * modpow(mint(i), N);
        if ( (K-i) & 1 ) res -= tmp;
        else res += tmp;
    }
    cout << res << endl;
}