test/Partition.test.cpp

• View this file on GitHub
• Last update: 2021-04-19 17:40:00+09:00
• Problem: https://yukicoder.me/problems/no/269

Depends on

• Utility/get_MOD.cpp
• math/Partition.cpp
• math/modint.cpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/269"
#include "./../math/Partition.cpp"
#include "./../math/modint.cpp"
#include <iostream>
using namespace std;

int main() {
	int n, s, k;
	cin >> n >> s >> k;
	int sum = s - n * (n - 1) / 2 * k;
	if (sum < 0) {
		cout << 0 << '\n';
	} else {
		cout << Partition<mint>(n, sum)[n][sum] << '\n';
	}
}

#line 1 "test/Partition.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/269"
#line 2 "math/Partition.cpp"
#include <vector>

template <class T> std::vector<std::vector<T>> Partition(int num, int sum) {
	std::vector dp(num + 1, std::vector<T>(sum + 1));
	dp[0][0] = 1;
	for (int i = 1; i <= num; ++i) {
		for (int j = 0; j <= sum; ++j) {
			if (j - i >= 0) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - i];
			} else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	return dp;
}
#line 2 "Utility/get_MOD.cpp"
constexpr long long get_MOD() {
#ifdef SET_MOD
	return SET_MOD;
#else
	return 1000000007;
#endif
}
#line 3 "math/modint.cpp"
#include <iostream>
#line 5 "math/modint.cpp"
#include <utility>
#include <cassert>

template <int MOD> struct modint {
	using value_type = long long;

private:
	value_type n;

public:
	constexpr static modint factorial(int n) {
		assert(n >= 0);
		modint result = 1;
		for (int i = 1; i <= n; ++i) {
			result *= i;
		}
		return result;
	}
	constexpr modint(const value_type x = 0) : n(x % MOD) {
		if (n < 0) n += MOD;
	}
	constexpr value_type value() const {
		return n;
	}
	constexpr int mod() const {
		return MOD;
	}
	constexpr modint operator+() const {
		return *this;
	}
	constexpr modint operator-() const {
		return n ? MOD - n : 0;
	}
	constexpr modint& operator++() {
		if (MOD <= ++n) n = 0;
		return *this;
	}
	constexpr modint& operator--() {
		if (n <= 0) n = MOD;
		n--;
		return *this;
	}
	constexpr modint operator++(int) {
		modint t = *this;
		++*this;
		return t;
	}
	constexpr modint operator--(int) {
		modint t = *this;
		--*this;
		return t;
	}
	constexpr modint next() const {
		return ++modint(*this);
	}
	constexpr modint pred() const {
		return --modint(*this);
	}
	constexpr modint& operator+=(const modint& m) {
		n += m.n;
		if (n >= MOD) n -= MOD;
		return *this;
	}
	constexpr modint& operator-=(const modint& m) {
		n -= m.n;
		if (n < 0) n += MOD;
		return *this;
	}
	constexpr modint& operator*=(const modint& m) {
		n = n * m.n % MOD;
		return *this;
	}
	constexpr modint& operator/=(const modint& m) {
		value_type a = m.n, b = MOD, u = 1, v = 0;
		while (b) {
			value_type t = a / b;
			a -= t * b;
			std::swap(a, b);
			u -= t * v;
			std::swap(u, v);
		}
		n = n * u % MOD;
		if (n < 0) n += MOD;
		return *this;
	}
	constexpr bool operator==(const modint& m) const {
		return n == m.n;
	}
	constexpr bool operator!=(const modint& m) const {
		return n != m.n;
	}
	template <class M> constexpr modint pow(M m) const {
		if (0 <= m) {
			modint t = n, result = 1;
			while (m > 0) {
				if (m & 1) {
					result *= t;
					m--;
				} else {
					t *= t;
					m >>= 1;
				}
			}
			return result;
		} else {
			return (modint(1) / n).pow(-m);
		}
	}
	friend constexpr modint operator+(const modint& a, const modint& b) {
		return modint(a) += b;
	}
	friend constexpr modint operator-(const modint& a, const modint& b) {
		return modint(a) -= b;
	}
	friend constexpr modint operator*(const modint& a, const modint& b) {
		return modint(a) *= b;
	}
	friend constexpr modint operator/(const modint& a, const modint& b) {
		return modint(a) /= b;
	}
	friend std::ostream& operator<<(std::ostream& os, const modint<MOD>& m) {
		return os << m.value();
	}
	friend std::istream& operator>>(std::istream& is, modint<MOD>& m) {
		modint<MOD>::value_type x;
		is >> x;
		m = modint(x);
		return is;
	}
	template <class Scanner> void scan() {
		Scanner::scan(n);
		n %= MOD;
		if (n < 0) n += MOD;
	}
	template <class Printer> void print(const Printer& out) const {
		out.print(value());
	}
};

using mint = modint<get_MOD()>;
using VM = std::vector<mint>;
mint operator""_m(unsigned long long n) {
	return n;
}
#line 5 "test/Partition.test.cpp"
using namespace std;

int main() {
	int n, s, k;
	cin >> n >> s >> k;
	int sum = s - n * (n - 1) / 2 * k;
	if (sum < 0) {
		cout << 0 << '\n';
	} else {
		cout << Partition<mint>(n, sum)[n][sum] << '\n';
	}
}

Back to top page