CSES - Putka Open 2020 – 2/5

CSES - Putka Open 2020 – 2/5 - Results

Submission details
Task:	Planeetat
Sender:	hltk
Submission time:	2020-09-27 15:50:55 +0300
Language:	C++ (C++17)
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.02 s	1, 2, 3	details
#2	ACCEPTED	0.02 s	1, 2, 3	details
#3	ACCEPTED	0.02 s	1, 2, 3	details
#4	WRONG ANSWER	0.02 s	1, 2, 3	details
#5	WRONG ANSWER	0.02 s	1, 2, 3	details
#6	WRONG ANSWER	0.02 s	1, 2, 3	details
#7	WRONG ANSWER	0.03 s	1, 2, 3	details
#8	WRONG ANSWER	0.02 s	1, 2, 3	details
#9	WRONG ANSWER	0.02 s	1, 2, 3	details
#10	WRONG ANSWER	0.02 s	1, 2, 3	details
#11	WRONG ANSWER	0.02 s	2, 3	details
#12	WRONG ANSWER	0.07 s	2, 3	details
#13	TIME LIMIT EXCEEDED	--	2, 3	details
#14	TIME LIMIT EXCEEDED	--	3	details
#15	TIME LIMIT EXCEEDED	--	3	details
#16	TIME LIMIT EXCEEDED	--	3	details
#17	TIME LIMIT EXCEEDED	--	3	details
#18	TIME LIMIT EXCEEDED	--	3	details
#19	TIME LIMIT EXCEEDED	--	3	details
#20	TIME LIMIT EXCEEDED	--	3	details
#21	TIME LIMIT EXCEEDED	--	3	details
#22	TIME LIMIT EXCEEDED	--	3	details
#23	TIME LIMIT EXCEEDED	--	3	details
#24	TIME LIMIT EXCEEDED	--	3	details
#25	TIME LIMIT EXCEEDED	--	3	details

Code

#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 = 998244353;
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<mint> score(n);
	std::function<void(int, std::vector<int>&)> brute = [&](int sum, std::vector<int>& k) {
		if (sum == n) {
			int l = n;
			mint ways(1);
			for (auto& x : k)
				ways *= p[x];
			for (int i = 0, j = 0; i < int(k.size()); i = j) {
				while (j < int(k.size()) && k[i] == k[j])
					++j;
				ways *= nCr::choose(l, k[i] * (j - i));
				l -= k[i] * (j - i);
			}
			score[k.size() - 1] += ways;
			return;
		}
		for (int j = (k.empty() ? 1 : k.back()); j <= n - sum; ++j) {
			k.push_back(j);
			brute(sum + j, k);
			k.pop_back();
		}
	};
	std::vector<int> base;
	brute(0, base);
	for (auto& x : score)
		std::cout << x << '\n';
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1` view save

correct output
`1` view save

user output
`1` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2` view save

correct output
`3 1` view save

user output
`3 1` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`3` view save

correct output
`17 9 1` view save

user output
`17 9 1` view save

Test 4

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`4` view save

correct output
`142 95 18 1` view save

user output
`142 77 18 1` view save

Test 5

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`5` view save

correct output
`1569 1220 305 30 1` view save

user output
`1569 1220 215 30 1` view save

Test 6

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`6` view save

correct output
`21576 18694 5595 745 45 ...` view save

user output
`21576 16093 5217 475 45 ...` view save

Test 7

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`7` view save

correct output
`355081 334369 113974 18515 1540 ...` view save

user output
`355081 334369 85057 15869 910 ...` view save

Test 8

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`8` view save

correct output
`6805296 6852460 2581964 484729 49840 ...` view save

user output
`6805296 6166884 2184560 317797 39256 ...` view save

Test 9

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`9` view save

correct output
`148869153 158479488 64727522 13591116 1632099 ...` view save

user output
`148869153 158479488 53628119 9474696 952239 ...` view save

Test 10

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`10` view save

correct output
`660215659 85349908 783995053 409987640 55545735 ...` view save

user output
`665482621 782896752 534078847 302732480 32035323 ...` view save

Test 11

Group: 2, 3

Verdict: WRONG ANSWER

input
`20` view save

correct output
`8033007 474885151 998010619 720259168 345757330 ...` view save

user output
`460697506 793147852 687410479 3592777 290216859 ...` Truncated

Test 12

Group: 2, 3

Verdict: WRONG ANSWER

input
`50` view save

correct output
`637699856 613177596 194234103 50828885 988168359 ...` view save

user output
`613718872 235524219 831125122 132935096 622043637 ...` Truncated

Test 13

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`100` view save

correct output
`894456323 406549429 962038245 430640330 61348310 ...` view save

user output
(empty)

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`666` view save

correct output
`189730587 968711879 553374698 53051125 139917248 ...` view save

user output
(empty)

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`3333` view save

correct output
`79235821 455292218 627100211 591681254 695866885 ...` view save

user output
(empty)

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4991` view save

correct output
`482116496 245260697 151422537 180441123 318466624 ...` view save

user output
(empty)

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4992` view save

correct output
`141010647 787351178 684701591 872974815 631476284 ...` view save

user output
(empty)

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4993` view save

correct output
`504034249 588971460 281533415 928250892 416697844 ...` view save

user output
(empty)

Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4994` view save

correct output
`266134603 90079109 544661648 812099750 17249410 ...` view save

user output
(empty)

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4995` view save

correct output
`833898560 663839791 109127071 321675160 86285359 ...` view save

user output
(empty)

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4996` view save

correct output
`721158645 167929822 115103278 491345159 114397872 ...` view save

user output
(empty)

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4997` view save

correct output
`691405606 436947443 82656395 514529009 783319673 ...` view save

user output
(empty)

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4998` view save

correct output
`829675470 688714502 189351950 956110193 20883331 ...` view save

user output
(empty)

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`4999` view save

correct output
`343936737 47032567 190931571 827280581 160866637 ...` view save

user output
(empty)

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`5000` view save

correct output
`364064601 633559852 352848841 666954216 428009512 ...` view save

user output
(empty)

Putka Open 2020 – 2/5

Planeetat

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Tasks

Submissions (hltk)