CSES - Putka Open 2020 – 2/5

Submission details
Task:	Planeetat
Sender:	Metabolix
Submission time:	2020-09-26 14:20:48 +0300
Language:	C++ (C++11)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	24
#2	ACCEPTED	25
#3	ACCEPTED	51

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 3	details
#2	ACCEPTED	0.01 s	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	ACCEPTED	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.01 s	1, 2, 3	details
#7	ACCEPTED	0.01 s	1, 2, 3	details
#8	ACCEPTED	0.01 s	1, 2, 3	details
#9	ACCEPTED	0.01 s	1, 2, 3	details
#10	ACCEPTED	0.01 s	1, 2, 3	details
#11	ACCEPTED	0.01 s	2, 3	details
#12	ACCEPTED	0.01 s	2, 3	details
#13	ACCEPTED	0.01 s	2, 3	details
#14	ACCEPTED	0.01 s	3	details
#15	ACCEPTED	0.20 s	3	details
#16	ACCEPTED	0.44 s	3	details
#17	ACCEPTED	0.44 s	3	details
#18	ACCEPTED	0.44 s	3	details
#19	ACCEPTED	0.43 s	3	details
#20	ACCEPTED	0.44 s	3	details
#21	ACCEPTED	0.45 s	3	details
#22	ACCEPTED	0.45 s	3	details
#23	ACCEPTED	0.44 s	3	details
#24	ACCEPTED	0.44 s	3	details
#25	ACCEPTED	0.44 s	3	details

Code

#include <iostream>

/*
# Stirling numbers of first kind
# https://oeis.org/A008275
def s(n, k):
	if (n == 0) and (k == 0):
		return 1
	if (n == 0) or (k == 0):
		return 0
	return s(n-1, k-1) - (n-1) * s(n-1, k)

# Triangle T(n,k) read by rows giving number of labeled mappings (or functional digraphs) from n points to themselves (endofunctions) with k cycles, k=1..n. 
# https://oeis.org/A060281
def T(n, k):
	# = Sum_{j=0..n-1} C(n-1,j)*n^(n-1-j)*(-1)^(k+j+1)*A008275(j+1,k)
	# = Sum_{j=0..n-1} binomial(n-1,j)*n^(n-1-j)*s(j+1,k).
	return sum(binomial(n-1, j) * n**(n-1-j) * s(j+1, k) for j in range(n))
*/

const int MOD = 1000000007;
const int MAX = 5002;

long power(long a, long b) {
	long ret = 1;
	while (b) {
		if (b & 1) {
			ret *= a;
			ret %= MOD;
		}
		b >>= 1;
		a *= a;
		a %= MOD;
	}
	return ret;
}
long mydiv(long a, long b) {
	return a * power(b, MOD - 2) % MOD;
}

long fac[MAX];
long bin[MAX];
long powers[MAX];
long s[MAX][MAX];

int main() {
	int n;
	std::cin >> n;

	fac[0] = fac[1] = 1;
	for (int i = 2; i < n; ++i) {
		fac[i] = (fac[i-1] * i) % MOD;
	}

	bin[0] = 1;
	for (int i = 1; i < n; ++i) {
		bin[i] = mydiv(mydiv(fac[n-1], fac[n-1 - i]), fac[i]);
	}

	powers[0] = 1;
	for (int i = 1; i <= n; ++i) {
		powers[i] = (powers[i-1] * n) % MOD;
	}

	s[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			s[i][j] = (s[i-1][j-1] + (i-1) * s[i-1][j]) % MOD;
		}
	}

	for (int i = 1; i <= n; ++i) {
		long v = 0;
		for (int j = 0; j < n; ++j) {
			v += bin[j] * powers[n-1-j] % MOD * s[j+1][i] % MOD;
		}
		std::cout << (v % MOD) << '\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: ACCEPTED

input
`4` view save

correct output
`142 95 18 1` view save

user output
`142 95 18 1` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5` view save

correct output
`1569 1220 305 30 1` view save

user output
`1569 1220 305 30 1` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`6` view save

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

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

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
`7` view save

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

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

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
`8` view save

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

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

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
`9` view save

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

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

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
`10` view save

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

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

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
`20` view save

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

user output
`8033007 474885151 998010619 720259168 345757330 ...` Truncated

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
`50` view save

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

user output
`637699856 613177596 194234103 50828885 988168359 ...` Truncated

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
`100` view save

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

user output
`894456323 406549429 962038245 430640330 61348310 ...` Truncated

Test 14

Group: 3

Verdict: ACCEPTED

input
`666` view save

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

user output
`189730587 968711879 553374698 53051125 139917248 ...` Truncated

Test 15

Group: 3

Verdict: ACCEPTED

input
`3333` view save

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

user output
`79235821 455292218 627100211 591681254 695866885 ...` Truncated

Test 16

Group: 3

Verdict: ACCEPTED

input
`4991` view save

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

user output
`482116496 245260697 151422537 180441123 318466624 ...` Truncated

Test 17

Group: 3

Verdict: ACCEPTED

input
`4992` view save

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

user output
`141010647 787351178 684701591 872974815 631476284 ...` Truncated

Test 18

Group: 3

Verdict: ACCEPTED

input
`4993` view save

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

user output
`504034249 588971460 281533415 928250892 416697844 ...` Truncated

Test 19

Group: 3

Verdict: ACCEPTED

input
`4994` view save

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

user output
`266134603 90079109 544661648 812099750 17249410 ...` Truncated

Test 20

Group: 3

Verdict: ACCEPTED

input
`4995` view save

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

user output
`833898560 663839791 109127071 321675160 86285359 ...` Truncated

Test 21

Group: 3

Verdict: ACCEPTED

input
`4996` view save

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

user output
`721158645 167929822 115103278 491345159 114397872 ...` Truncated

Test 22

Group: 3

Verdict: ACCEPTED

input
`4997` view save

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

user output
`691405606 436947443 82656395 514529009 783319673 ...` Truncated

Test 23

Group: 3

Verdict: ACCEPTED

input
`4998` view save

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

user output
`829675470 688714502 189351950 956110193 20883331 ...` Truncated

Test 24

Group: 3

Verdict: ACCEPTED

input
`4999` view save

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

user output
`343936737 47032567 190931571 827280581 160866637 ...` Truncated

Test 25

Group: 3

Verdict: ACCEPTED

input
`5000` view save

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

user output
`364064601 633559852 352848841 666954216 428009512 ...` Truncated

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 (Metabolix)