test/partition_number.test.cpp

• View this file on GitHub
• Last update: 2023-01-28 20:23:48+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/5/DPL_5_J

Depends on

• math/mint.cpp
• math/partition_number.cpp

Code

#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/5/DPL_5_J"
#include "../math/mint.cpp"
#include "../math/partition_number.cpp"

using mint2 = ModInt<1000000007>;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int n, k;
    cin >> n >> k;
    PartitionNumber<mint2> pn(n, k);
    pn.solve();
    cout << pn(n, k) << '\n';

    return 0;
}

#line 1 "test/partition_number.test.cpp"
#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/5/DPL_5_J"
#line 3 "math/mint.cpp"
using namespace std;

template <int MOD>
struct ModInt {
  public:
    long long x;
    ModInt(long long x = 0) : x((x % MOD + MOD) % MOD) {}
    constexpr ModInt &operator+=(const ModInt a) noexcept {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    constexpr ModInt &operator-=(const ModInt a) noexcept {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    constexpr ModInt &operator*=(const ModInt a) noexcept {
        (x *= a.x) %= MOD;
        return *this;
    }
    constexpr ModInt &operator/=(const ModInt a) noexcept { return *this *= a.inverse(); }

    constexpr ModInt operator+(const ModInt a) const noexcept { return ModInt(*this) += a.x; }
    constexpr ModInt operator-(const ModInt a) const noexcept { return ModInt(*this) -= a.x; }
    constexpr ModInt operator*(const ModInt a) const noexcept { return ModInt(*this) *= a.x; }
    constexpr ModInt operator/(const ModInt a) const noexcept { return ModInt(*this) /= a.x; }

    friend constexpr std::ostream &operator<<(std::ostream &os, const ModInt<MOD> a) noexcept { return os << a.x; }
    friend constexpr std::istream &operator>>(std::istream &is, ModInt<MOD> &a) noexcept {
        is >> a.x;
        a.x = (a.x % MOD + MOD) % MOD;
        return is;
    }

    ModInt inverse() const noexcept { // x ^ (-1)
        long long a = x, b = MOD, p = 1, q = 0;
        while (b) {
            long long d = a / b;
            a -= d * b;
            swap(a, b);
            p -= d * q;
            swap(p, q);
        }
        return ModInt(p);
    }
    ModInt pow(long long N) const noexcept { // x ^ N
        ModInt a = 1;
        ModInt y = this->x;
        while (N) {
            if (N & 1) a *= y;
            y *= y;
            N >>= 1;
        }
        return a;
    }
};

template <typename U, int MOD>
inline ModInt<MOD> operator*(const U &c, const ModInt<MOD> &a) { return {c * a.x}; }

using mint = ModInt<998244353>;
#line 3 "math/partition_number.cpp"
using namespace std;

// PartionNumber
// n個の区別できないものをk個の区別できない箱に0個以上に分割する方法が何通りあるか求める.
// これをP(n,k)とするとP(n,0) = 0 (n > 0)
template <typename T>
struct PartitionNumber {
    int n, k;
    vector<vector<T>> dp;

    PartitionNumber(int n, int k) : n(n), k(k) {
        dp.assign(n + 1, vector<T>(k + 1, T(0)));
    }

    // solve
    // 0 <= i <= n,0 <= j <= kの分割数を求める.
    // 計算量: O(nk)
    void solve() {
        dp[0][0] = T(1);
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i][j - 1];
                if (i - j >= 0) dp[i][j] += dp[i - j][j];
            }
        }
    }

    // P(i,j)を返す.
    // 制約: 0 <= i <= n,0 <= j <= k
    T operator()(int i, int j) {
        return dp[i][j];
    }
};
#line 7 "test/partition_number.test.cpp"

using mint2 = ModInt<1000000007>;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int n, k;
    cin >> n >> k;
    PartitionNumber<mint2> pn(n, k);
    pn.solve();
    cout << pn(n, k) << '\n';

    return 0;
}

Back to top page