Planeetat

#pragma GCC optimize ("O3")

#include <functional>
#include <iostream>
#include <vector>

using ll = long long;

template <typename T> T pow(T a, ll b) {
	T r = 1;
	for (; b; b /= 2, a *= a)
		if (b % 2) r *= a;
	return r;
}

// source: ecnerwala, own, benq
template <int MOD> struct modint {
	int v;
	modint() : v(0) {}
	modint(ll x) : v(x % MOD) {
		if (v < 0) v += MOD;
	}
	explicit operator int() const { return v; }
	explicit operator ll() const { return v; }

	friend std::ostream &operator<<(std::ostream &out, const modint &a) {
		return out << int(a);
	}
	friend std::istream &operator>>(std::istream &in, modint &a) {
		ll x;
		in >> x;
		a = modint(x);
		return in;
	}

	// only works if MOD is prime
	modint inv() const {
		return pow(*this, MOD - 2);
	}
	friend modint inv(const modint &x) { return x.inv(); }

	modint &operator+=(const modint &a) {
		v += a.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modint &operator-=(const modint &a) {
		v -= a.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modint &operator*=(const modint &a) {
		v = ll(v) * ll(a.v) % MOD;
		return *this;
	}
	modint &operator/=(const modint &a) { return *this *= a.inv(); }

	friend modint operator+(const modint &a, const modint &b) {
		return modint(a) += b;
	}
	friend modint operator-(const modint &a, const modint &b) {
		return modint(a) -= b;
	}
	friend modint operator*(const modint &a, const modint &b) {
		return modint(a) *= b;
	}
	friend modint operator/(const modint &a, const modint &b) {
		return modint(a) /= b;
	}
};

constexpr ll MOD = 1000000007;
using mint = modint<MOD>;

namespace nCr {
	std::vector<mint> fact, ifact;
	void init(int N = int(1e6)) {
		fact.resize(N + 1);
		ifact.resize(N + 1);
		fact[0] = 1;
		for (int i = 1; i <= N; ++i)
			fact[i] = fact[i - 1] * i;
		ifact[N] = 1 / fact[N];
		for (int i = N; i > 0; --i)
			ifact[i - 1] = i * ifact[i];
	}

	mint choose(int a, int b) {
		if (a < b || b < 0) return 0;
		return fact[a] * ifact[b] * ifact[a - b];
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	nCr::init();
	int n;
	std::cin >> n;
	std::vector<mint> p(n + 1);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= i; ++j)
			p[i] += nCr::choose(i, j) * pow(mint(i - j), i - j) * pow(mint(j), j);
	for (int i = 1; i <= n; ++i)
		p[i] /= i;
	std::vector<std::vector<mint>> dp(n + 1, std::vector<mint>(n + 1));
	dp[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		auto new_dp = dp;
		for (int j = 1; i * j <= n; ++j) {
			for (int k = n - i * j; k >= 0; --k) {
				for (int z = n - j; z >= 0; --z) {
					new_dp[k + i * j][z + j] += pow(p[i] * nCr::ifact[i], j) * nCr::ifact[j] * dp[k][z];
				}
			}
		}
		dp = new_dp;
	}
	for (int i = 1; i <= n; ++i)
		std::cout << dp[n][i] * nCr::fact[n] << '\n';
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 2, 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED