Task: | Planeetat |
Sender: | Olli |
Submission time: | 2020-09-26 15:30:56 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 49 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 24 |
#2 | ACCEPTED | 25 |
#3 | RUNTIME ERROR | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.57 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.57 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.57 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.57 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.57 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.57 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.57 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.57 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.57 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.57 s | 1, 2, 3 | details |
#11 | ACCEPTED | 0.57 s | 2, 3 | details |
#12 | ACCEPTED | 0.58 s | 2, 3 | details |
#13 | ACCEPTED | 0.58 s | 2, 3 | details |
#14 | RUNTIME ERROR | 0.57 s | 3 | details |
#15 | RUNTIME ERROR | 0.57 s | 3 | details |
#16 | RUNTIME ERROR | 0.57 s | 3 | details |
#17 | RUNTIME ERROR | 0.57 s | 3 | details |
#18 | RUNTIME ERROR | 0.57 s | 3 | details |
#19 | RUNTIME ERROR | 0.58 s | 3 | details |
#20 | RUNTIME ERROR | 0.58 s | 3 | details |
#21 | RUNTIME ERROR | 0.57 s | 3 | details |
#22 | RUNTIME ERROR | 0.57 s | 3 | details |
#23 | RUNTIME ERROR | 0.57 s | 3 | details |
#24 | RUNTIME ERROR | 0.57 s | 3 | details |
#25 | RUNTIME ERROR | 0.57 s | 3 | details |
Code
#include <iostream>using namespace std;typedef long long ll;const int M = 1e9 + 7;const int N = 255;ll ans[N][N]; //ans[x][y] tells how many ways there is to divide x into y componentsll b[N][N]; //b[n][k] = (n choose k)ll fa[N];ll f[N][N]; //Adjoin x more, when there are k readyll exp(ll a, ll e) {if(e == 0) return 1;if(e%2 == 0) {ll b = exp(a, e/2);return (b*b)%M;}ll b = exp(a, e-1);return (a*b)%M;}int main() {fa[0] = 1;for(ll i = 1; i < N; ++i) {fa[i] = fa[i-1]*i;fa[i] %= M;}for(int i = 0; i < N; ++i) {b[i][0] = 1;b[i][i] = 1;}for(int i = 1; i < N; ++i) {for(int j = 1; j < i; ++j) {b[i][j] = b[i-1][j-1] + b[i-1][j];b[i][j] %= M;}}for(int k = 0; k < N; ++k) {f[0][k] = 1;}for(int x = 1; x < N; ++x) {for(int k = 1; k < N; ++k) {for(int i = 1; i <= x; ++i) {ll cur = exp(k, i)*b[x][i];cur %= M;cur *= f[x-i][i];f[x][k] += cur;f[x][k] %= M;}}}for(int x = 1; x < N; ++x) {//Handle the case of one connected component separatelyif(x == 1) {ans[x][1] = 1;continue;}for(int k = 1; k <= x; ++k) {ll cur = b[x][k]*fa[k-1];cur %= M;cur *= f[x-k][k];ans[x][1] += cur;ans[x][1] %= M;}//Take a//Then add some edge//Then choose orientations//There are two ways to choose the orientationsfor(int y = 2; y <= x; ++y) {//Case work on the size of the component of node 1for(int i = 1; i <= x; ++i) {ll cur = b[x-1][i-1]*ans[i][1];cur %= M;cur *= ans[x-i][y-1];ans[x][y] += cur;ans[x][y] %= M;if(x == 3) {// cout << x << " " << y << " " << i << " " << cur << " " << ans[x-i][y-1] << "\n";}}}}int n;cin >> n;for(int i = 1; i <= n; ++i) {cout << ans[n][i] << " ";}cout << "\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 1 |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
7 |
correct output |
---|
355081 334369 113974 18515 1540 ... |
user output |
---|
355081 334369 113974 18515 154... |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
8 |
correct output |
---|
6805296 6852460 2581964 484729 49840 ... |
user output |
---|
6805296 6852460 2581964 484729... |
Test 9
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
9 |
correct output |
---|
148869153 158479488 64727522 13591116 1632099 ... |
user output |
---|
148869153 158479488 64727522 1... |
Test 10
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 |
correct output |
---|
660215659 85349908 783995053 409987640 55545735 ... |
user output |
---|
660215659 85349908 783995053 4... |
Test 11
Group: 2, 3
Verdict: ACCEPTED
input |
---|
20 |
correct output |
---|
8033007 474885151 998010619 720259168 345757330 ... |
user output |
---|
8033007 474885151 998010619 72... Truncated |
Test 12
Group: 2, 3
Verdict: ACCEPTED
input |
---|
50 |
correct output |
---|
637699856 613177596 194234103 50828885 988168359 ... |
user output |
---|
637699856 613177596 194234103 ... Truncated |
Test 13
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 |
correct output |
---|
894456323 406549429 962038245 430640330 61348310 ... |
user output |
---|
894456323 406549429 962038245 ... Truncated |
Test 14
Group: 3
Verdict: RUNTIME ERROR
input |
---|
666 |
correct output |
---|
189730587 968711879 553374698 53051125 139917248 ... |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: RUNTIME ERROR
input |
---|
3333 |
correct output |
---|
79235821 455292218 627100211 591681254 695866885 ... |
user output |
---|
(empty) |
Test 16
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4991 |
correct output |
---|
482116496 245260697 151422537 180441123 318466624 ... |
user output |
---|
(empty) |
Test 17
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4992 |
correct output |
---|
141010647 787351178 684701591 872974815 631476284 ... |
user output |
---|
(empty) |
Test 18
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4993 |
correct output |
---|
504034249 588971460 281533415 928250892 416697844 ... |
user output |
---|
(empty) |
Test 19
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4994 |
correct output |
---|
266134603 90079109 544661648 812099750 17249410 ... |
user output |
---|
(empty) |
Test 20
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4995 |
correct output |
---|
833898560 663839791 109127071 321675160 86285359 ... |
user output |
---|
(empty) |
Test 21
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4996 |
correct output |
---|
721158645 167929822 115103278 491345159 114397872 ... |
user output |
---|
(empty) |
Test 22
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4997 |
correct output |
---|
691405606 436947443 82656395 514529009 783319673 ... |
user output |
---|
(empty) |
Test 23
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4998 |
correct output |
---|
829675470 688714502 189351950 956110193 20883331 ... |
user output |
---|
(empty) |
Test 24
Group: 3
Verdict: RUNTIME ERROR
input |
---|
4999 |
correct output |
---|
343936737 47032567 190931571 827280581 160866637 ... |
user output |
---|
(empty) |
Test 25
Group: 3
Verdict: RUNTIME ERROR
input |
---|
5000 |
correct output |
---|
364064601 633559852 352848841 666954216 428009512 ... |
user output |
---|
(empty) |