| Task: | Planeetat |
| Sender: | ArktinenKarpalo |
| Submission time: | 2020-09-27 04:49:52 +0300 |
| Language: | C++ (C++11) |
| Status: | READY |
| Result: | 0 |
| group | verdict | score |
|---|---|---|
| #1 | WRONG ANSWER | 0 |
| #2 | WRONG ANSWER | 0 |
| #3 | WRONG ANSWER | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.11 s | 1, 2, 3 | details |
| #2 | ACCEPTED | 0.11 s | 1, 2, 3 | details |
| #3 | ACCEPTED | 0.11 s | 1, 2, 3 | details |
| #4 | ACCEPTED | 0.11 s | 1, 2, 3 | details |
| #5 | ACCEPTED | 0.11 s | 1, 2, 3 | details |
| #6 | ACCEPTED | 0.11 s | 1, 2, 3 | details |
| #7 | ACCEPTED | 0.11 s | 1, 2, 3 | details |
| #8 | ACCEPTED | 0.11 s | 1, 2, 3 | details |
| #9 | ACCEPTED | 0.11 s | 1, 2, 3 | details |
| #10 | WRONG ANSWER | 0.11 s | 1, 2, 3 | details |
| #11 | WRONG ANSWER | 0.11 s | 2, 3 | details |
| #12 | WRONG ANSWER | 0.11 s | 2, 3 | details |
| #13 | WRONG ANSWER | 0.11 s | 2, 3 | details |
| #14 | WRONG ANSWER | 0.11 s | 3 | details |
| #15 | WRONG ANSWER | 0.11 s | 3 | details |
| #16 | WRONG ANSWER | 0.11 s | 3 | details |
| #17 | WRONG ANSWER | 0.11 s | 3 | details |
| #18 | WRONG ANSWER | 0.11 s | 3 | details |
| #19 | WRONG ANSWER | 0.11 s | 3 | details |
| #20 | WRONG ANSWER | 0.11 s | 3 | details |
| #21 | WRONG ANSWER | 0.11 s | 3 | details |
| #22 | WRONG ANSWER | 0.11 s | 3 | details |
| #23 | WRONG ANSWER | 0.11 s | 3 | details |
| #24 | WRONG ANSWER | 0.11 s | 3 | details |
| #25 | WRONG ANSWER | 0.11 s | 3 | details |
Code
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define M 1000000007
using namespace std;
ll ans[5511][5511];
ll pt(ll a, ll p) {
ll b = 1;
while(p) {
if(p%2==1)
b = (b*a)%M;
p /= 2;
a = (a*a)%M;
}
return b;
}
ll divv(ll a, ll b) {
return (a*pt(b, M-2))%M;
}
ll kc[5555];
ll kertoma(ll luk) {
return kc[luk];
}
ll pc[5555];
ll pot(ll p, ll e) {
return pc[p];
}
int main() {
cout.tie(0);
cin.tie(0);
ios_base::sync_with_stdio(0);
pc[0] = 1;
kc[0] = 1;
for(int i=1; i<=5000; i++) {
kc[i] = (kc[i-1]*i)%M;
pc[i] = 1;
for(int j=1; j<=i; j++)
pc[i] = (pc[i]*i)%M;
}
for(int i=1; i<=5000; i++) {
ans[i][i] = 1;
}
ans[0][1] = 1;
for(int i=2; i<=100; i++) {
ans[i][1] = pot(i,i)-1;
for(int j=i-1; j>=2; j--) {
ans[i][j] = 0;
for(int k=1; k<i; k++) {
if(i-k < j-1)
continue;
ans[i][j] += ((ans[k][1]*ans[i-k][j-1])%M*divv(kertoma(i),(kertoma(i-k)*kertoma(k))%M))%M;
ans[i][j] %= M;
}
ans[i][j] /= j;
ans[i][1] = ((ans[i][1]-ans[i][j])+M)%M;
}
}
int n;
cin >> n;
for(int i=1; i<=n; i++)
cout << ans[n][i] << "\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: WRONG ANSWER
| input |
|---|
| 10 |
| correct output |
|---|
| 660215659 85349908 783995053 409987640 55545735 ... |
| user output |
|---|
| 576882326 85349908 117328381 159987638 55545735 ... |
Test 11
Group: 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| 20 |
| correct output |
|---|
| 8033007 474885151 998010619 720259168 345757330 ... |
| user output |
|---|
| 753403547 208608541 204843125 194330567 165048937 ... Truncated |
Test 12
Group: 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| 50 |
| correct output |
|---|
| 637699856 613177596 194234103 50828885 988168359 ... |
| user output |
|---|
| 430960859 422185417 214691 172726953 45752008 ... Truncated |
Test 13
Group: 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| 100 |
| correct output |
|---|
| 894456323 406549429 962038245 430640330 61348310 ... |
| user output |
|---|
| 34002450 429023185 302587135 113829244 87887329 ... Truncated |
Test 14
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 666 |
| correct output |
|---|
| 189730587 968711879 553374698 53051125 139917248 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 15
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 3333 |
| correct output |
|---|
| 79235821 455292218 627100211 591681254 695866885 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 16
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 4991 |
| correct output |
|---|
| 482116496 245260697 151422537 180441123 318466624 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 17
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 4992 |
| correct output |
|---|
| 141010647 787351178 684701591 872974815 631476284 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 18
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 4993 |
| correct output |
|---|
| 504034249 588971460 281533415 928250892 416697844 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 19
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 4994 |
| correct output |
|---|
| 266134603 90079109 544661648 812099750 17249410 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 20
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 4995 |
| correct output |
|---|
| 833898560 663839791 109127071 321675160 86285359 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 21
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 4996 |
| correct output |
|---|
| 721158645 167929822 115103278 491345159 114397872 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 22
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 4997 |
| correct output |
|---|
| 691405606 436947443 82656395 514529009 783319673 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 23
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 4998 |
| correct output |
|---|
| 829675470 688714502 189351950 956110193 20883331 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 24
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 4999 |
| correct output |
|---|
| 343936737 47032567 190931571 827280581 160866637 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |
Test 25
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 5000 |
| correct output |
|---|
| 364064601 633559852 352848841 666954216 428009512 ... |
| user output |
|---|
| 0 0 0 0 0 ... Truncated |