CSES - Putka Open 2020 – 2/5 - Results
Submission details
Task:Planeetat
Sender:Metabolix
Submission time:2020-09-26 14:20:48 +0300
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED24
#2ACCEPTED25
#3ACCEPTED51
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.01 s1, 2, 3details
#11ACCEPTED0.01 s2, 3details
#12ACCEPTED0.01 s2, 3details
#13ACCEPTED0.01 s2, 3details
#14ACCEPTED0.01 s3details
#15ACCEPTED0.20 s3details
#16ACCEPTED0.44 s3details
#17ACCEPTED0.44 s3details
#18ACCEPTED0.44 s3details
#19ACCEPTED0.43 s3details
#20ACCEPTED0.44 s3details
#21ACCEPTED0.45 s3details
#22ACCEPTED0.45 s3details
#23ACCEPTED0.44 s3details
#24ACCEPTED0.44 s3details
#25ACCEPTED0.44 s3details

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

correct output
1

user output
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
2

correct output
3
1

user output
3
1

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
3

correct output
17
9
1

user output
17
9
1

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
4

correct output
142
95
18
1

user output
142
95
18
1

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
5

correct output
1569
1220
305
30
1

user output
1569
1220
305
30
1

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
6

correct output
21576
18694
5595
745
45
...

user output
21576
18694
5595
745
45
...

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
7

correct output
355081
334369
113974
18515
1540
...

user output
355081
334369
113974
18515
1540
...

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
8

correct output
6805296
6852460
2581964
484729
49840
...

user output
6805296
6852460
2581964
484729
49840
...

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
9

correct output
148869153
158479488
64727522
13591116
1632099
...

user output
148869153
158479488
64727522
13591116
1632099
...

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
10

correct output
660215659
85349908
783995053
409987640
55545735
...

user output
660215659
85349908
783995053
409987640
55545735
...

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
20

correct output
8033007
474885151
998010619
720259168
345757330
...

user output
8033007
474885151
998010619
720259168
345757330
...

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
50

correct output
637699856
613177596
194234103
50828885
988168359
...

user output
637699856
613177596
194234103
50828885
988168359
...

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
100

correct output
894456323
406549429
962038245
430640330
61348310
...

user output
894456323
406549429
962038245
430640330
61348310
...

Test 14

Group: 3

Verdict: ACCEPTED

input
666

correct output
189730587
968711879
553374698
53051125
139917248
...

user output
189730587
968711879
553374698
53051125
139917248
...

Test 15

Group: 3

Verdict: ACCEPTED

input
3333

correct output
79235821
455292218
627100211
591681254
695866885
...

user output
79235821
455292218
627100211
591681254
695866885
...

Test 16

Group: 3

Verdict: ACCEPTED

input
4991

correct output
482116496
245260697
151422537
180441123
318466624
...

user output
482116496
245260697
151422537
180441123
318466624
...

Test 17

Group: 3

Verdict: ACCEPTED

input
4992

correct output
141010647
787351178
684701591
872974815
631476284
...

user output
141010647
787351178
684701591
872974815
631476284
...

Test 18

Group: 3

Verdict: ACCEPTED

input
4993

correct output
504034249
588971460
281533415
928250892
416697844
...

user output
504034249
588971460
281533415
928250892
416697844
...

Test 19

Group: 3

Verdict: ACCEPTED

input
4994

correct output
266134603
90079109
544661648
812099750
17249410
...

user output
266134603
90079109
544661648
812099750
17249410
...

Test 20

Group: 3

Verdict: ACCEPTED

input
4995

correct output
833898560
663839791
109127071
321675160
86285359
...

user output
833898560
663839791
109127071
321675160
86285359
...

Test 21

Group: 3

Verdict: ACCEPTED

input
4996

correct output
721158645
167929822
115103278
491345159
114397872
...

user output
721158645
167929822
115103278
491345159
114397872
...

Test 22

Group: 3

Verdict: ACCEPTED

input
4997

correct output
691405606
436947443
82656395
514529009
783319673
...

user output
691405606
436947443
82656395
514529009
783319673
...

Test 23

Group: 3

Verdict: ACCEPTED

input
4998

correct output
829675470
688714502
189351950
956110193
20883331
...

user output
829675470
688714502
189351950
956110193
20883331
...

Test 24

Group: 3

Verdict: ACCEPTED

input
4999

correct output
343936737
47032567
190931571
827280581
160866637
...

user output
343936737
47032567
190931571
827280581
160866637
...

Test 25

Group: 3

Verdict: ACCEPTED

input
5000

correct output
364064601
633559852
352848841
666954216
428009512
...

user output
364064601
633559852
352848841
666954216
428009512
...