QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #200033 | #7348. Counting Orders | S_Explosion# | AC ✓ | 102ms | 198636kb | C++20 | 1.7kb | 2023-10-04 15:09:48 | 2023-10-04 15:09:49 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#include <cstring>
#include <vector>
#include <bitset>
template <typename Tp>
inline void read(Tp &x) {
x = 0;
bool f = true; char ch = getchar();
for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
x = f ? x : -x;
}
const int N = 5e3, Mod = 1e9 + 7;
bool vis[N + 5];
int dp[N + 5][N + 5], siz[N + 5], C[N + 5][N + 5];
std::vector<int> Vec[N + 5];
void dfs(int u) {
siz[u] = 1;
int sz = 0, cur = 1;
for (int v : Vec[u]) {
dfs(v);
siz[u] += siz[v];
if (!vis[v]) {
sz += siz[v];
cur = 1LL * cur * dp[v][0] % Mod * C[sz][siz[v]] % Mod;
}
}
if (vis[u]) {
dp[u][1] = cur;
return;
}
for (int v : Vec[u]) {
if (!vis[v]) continue;
vis[u] = true;
for (int i = 0; i <= sz; ++i)
for (int j = 1; j <= siz[v]; ++j) {
dp[u][i + j + 1] = (dp[u][i + j + 1] + 1LL * cur * dp[v][j] % Mod * C[i + j - 1][j - 1] % Mod * C[siz[u] - (i + j + 1)][siz[v] - j]) % Mod;
}
}
if (!vis[u]) dp[u][0] = cur;
}
int main() {
int n;
read(n);
C[0][0] = 1;
for (int i = 1; i <= n; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod;
}
for (int i = 2; i <= n; ++i) {
int x;
read(x);
Vec[x].push_back(i);
}
int u, k;
read(u), read(k);
vis[u] = true;
dfs(1);
printf("%d\n", dp[1][k]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5760kb
input:
6 1 1 1 2 3 2 3
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5916kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
2 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5728kb
input:
2 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5920kb
input:
2 1 2 1
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 5720kb
input:
2 1 2 2
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 7772kb
input:
3 1 1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 0ms
memory: 5744kb
input:
3 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 0ms
memory: 5952kb
input:
3 1 1 1 3
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5784kb
input:
3 1 1 2 1
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
3 1 1 2 2
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 7928kb
input:
3 1 1 2 3
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
3 1 1 3 1
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
3 1 1 3 2
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 5796kb
input:
3 1 1 3 3
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 5752kb
input:
3 1 2 1 1
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
3 1 2 1 2
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 1ms
memory: 5740kb
input:
3 1 2 1 3
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 1ms
memory: 5800kb
input:
3 1 2 2 1
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 1ms
memory: 5788kb
input:
3 1 2 2 2
output:
1
result:
ok 1 number(s): "1"
Test #21:
score: 0
Accepted
time: 0ms
memory: 5788kb
input:
3 1 2 2 3
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 1ms
memory: 5720kb
input:
3 1 2 3 1
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
3 1 2 3 2
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
3 1 2 3 3
output:
1
result:
ok 1 number(s): "1"
Test #25:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
10 1 2 1 2 5 5 6 6 6 7 7
output:
288
result:
ok 1 number(s): "288"
Test #26:
score: 0
Accepted
time: 1ms
memory: 10196kb
input:
100 1 2 3 4 2 6 3 4 9 7 10 5 11 12 10 13 15 14 18 10 20 18 18 16 23 25 20 18 9 25 30 6 4 29 33 31 31 12 12 17 6 32 34 22 22 44 35 14 35 19 48 33 44 51 41 38 53 49 45 46 42 23 58 54 51 49 41 53 53 28 64 62 38 68 71 74 64 66 69 61 58 80 32 49 81 36 61 79 47 40 57 68 57 54 51 65 68 93 29 82 47
output:
934287420
result:
ok 1 number(s): "934287420"
Test #27:
score: 0
Accepted
time: 5ms
memory: 26436kb
input:
500 1 2 3 1 3 5 7 8 9 6 11 8 6 7 12 10 8 9 16 19 21 20 10 16 20 6 20 26 5 23 30 32 33 21 33 19 37 27 12 27 22 38 33 40 36 41 29 25 21 38 44 48 40 53 20 55 39 55 36 37 42 58 31 64 47 43 56 62 58 64 69 56 47 71 57 42 44 65 42 35 46 68 27 23 27 73 67 82 81 60 86 91 56 23 93 93 55 65 46 51 30 47 22 24 7...
output:
875617161
result:
ok 1 number(s): "875617161"
Test #28:
score: 0
Accepted
time: 4ms
memory: 42896kb
input:
1000 1 1 3 2 5 4 3 8 6 8 10 7 8 13 11 9 12 18 19 18 19 15 4 23 21 17 13 28 19 15 28 26 21 33 24 30 32 30 20 36 40 36 40 44 26 19 11 15 33 26 23 50 49 47 9 56 49 19 38 49 19 50 29 50 48 58 56 37 41 50 44 29 69 68 31 51 71 62 78 59 28 74 45 35 60 58 47 62 70 75 91 38 57 80 58 52 74 80 92 68 75 50 36 9...
output:
792949708
result:
ok 1 number(s): "792949708"
Test #29:
score: 0
Accepted
time: 82ms
memory: 198568kb
input:
5000 1 2 3 3 4 4 2 7 3 7 10 7 9 3 8 7 15 8 14 18 19 21 22 17 18 17 13 27 20 28 19 23 24 8 16 17 30 25 29 37 33 39 38 34 29 18 8 16 42 23 41 7 29 29 35 48 33 43 56 34 45 45 17 46 39 66 44 62 40 8 48 41 57 58 44 26 35 41 49 66 35 54 70 58 23 35 21 35 77 76 53 51 80 63 89 20 58 91 65 71 85 48 48 98 87 ...
output:
419392926
result:
ok 1 number(s): "419392926"
Test #30:
score: 0
Accepted
time: 100ms
memory: 196988kb
input:
5000 1 2 2 4 4 6 6 8 9 8 7 4 12 12 8 10 14 13 10 19 20 19 17 24 21 23 20 26 26 21 21 9 18 27 24 33 35 32 37 19 34 24 32 29 45 40 28 26 29 44 34 45 26 46 31 41 47 58 5 46 47 36 27 36 32 32 27 17 63 42 40 33 50 34 23 51 74 38 72 47 37 69 70 56 43 84 46 53 37 30 48 74 35 35 29 67 81 83 49 83 38 102 42 ...
output:
623786557
result:
ok 1 number(s): "623786557"
Test #31:
score: 0
Accepted
time: 100ms
memory: 196864kb
input:
5000 1 2 2 1 3 6 2 8 7 9 11 4 10 6 14 14 13 16 15 19 18 22 20 12 25 21 27 15 18 14 23 26 25 30 35 33 30 22 34 15 27 38 33 24 15 41 45 35 24 14 38 52 53 24 27 50 47 39 29 38 49 50 38 59 59 29 66 39 41 54 31 40 62 56 70 51 51 32 52 59 69 35 68 55 22 75 8 25 85 74 42 80 51 88 44 56 69 30 33 95 50 80 37...
output:
582112868
result:
ok 1 number(s): "582112868"
Test #32:
score: 0
Accepted
time: 102ms
memory: 197124kb
input:
5000 1 1 3 3 5 5 7 8 8 10 10 11 6 7 14 16 15 7 19 19 19 9 13 23 19 17 9 22 17 22 25 14 33 16 10 28 30 12 31 28 16 15 31 41 30 14 28 30 49 35 49 41 42 19 10 50 52 57 55 40 50 43 48 36 20 28 43 62 41 59 23 48 29 4 46 63 30 54 66 71 44 45 65 53 83 67 42 50 45 87 49 70 84 41 65 57 48 76 17 8 95 83 32 4 ...
output:
674953981
result:
ok 1 number(s): "674953981"
Test #33:
score: 0
Accepted
time: 77ms
memory: 198532kb
input:
5000 1 1 2 2 3 5 7 2 8 9 8 9 9 14 13 16 9 14 15 20 20 20 11 8 6 22 14 18 22 30 27 28 14 30 32 29 35 7 38 33 28 37 38 35 36 43 34 40 35 5 12 51 39 19 6 52 32 34 34 53 52 62 57 13 47 36 57 17 65 30 61 55 73 43 73 75 61 77 26 51 53 57 70 52 35 51 4 40 27 49 90 1 59 88 90 80 58 87 98 33 85 35 56 88 92 9...
output:
671195906
result:
ok 1 number(s): "671195906"
Test #34:
score: 0
Accepted
time: 1ms
memory: 5820kb
input:
10 1 2 2 4 5 5 6 4 7 10 2
output:
0
result:
ok 1 number(s): "0"
Test #35:
score: 0
Accepted
time: 0ms
memory: 10272kb
input:
100 1 2 3 4 5 2 7 8 6 9 11 8 11 11 12 14 15 15 19 15 16 22 17 22 7 24 25 27 13 17 19 13 27 32 31 36 31 34 29 26 24 38 41 44 26 42 45 30 39 46 48 16 49 52 39 32 44 26 26 49 38 50 61 45 58 66 62 56 66 61 36 60 53 53 62 66 64 57 54 48 79 64 55 73 47 80 75 25 76 57 55 28 93 56 79 84 97 61 78 35 64
output:
160007065
result:
ok 1 number(s): "160007065"
Test #36:
score: 0
Accepted
time: 0ms
memory: 24744kb
input:
500 1 2 2 4 4 4 3 8 8 9 2 5 13 9 9 10 13 16 8 15 20 22 11 9 24 25 13 17 15 6 30 15 27 33 24 31 29 13 29 39 32 40 31 38 33 27 19 23 46 23 29 12 47 18 50 42 51 54 38 46 20 44 36 58 51 63 66 41 56 42 64 53 63 64 34 72 60 68 63 63 65 82 41 71 78 86 71 80 43 78 81 78 88 65 70 93 79 71 97 49 91 64 28 79 1...
output:
708692459
result:
ok 1 number(s): "708692459"
Test #37:
score: 0
Accepted
time: 3ms
memory: 46772kb
input:
1000 1 2 3 2 4 6 6 5 8 3 10 12 8 12 6 8 11 14 19 14 21 19 18 22 9 24 25 24 21 29 16 28 23 16 34 7 24 22 38 35 31 35 27 44 31 12 47 16 21 30 38 39 36 23 53 43 44 48 45 44 60 62 59 41 33 61 32 39 65 52 66 56 67 69 69 60 38 53 56 56 25 81 75 66 36 84 74 55 45 67 60 54 88 63 93 75 91 29 70 82 55 101 94 ...
output:
133137719
result:
ok 1 number(s): "133137719"
Test #38:
score: 0
Accepted
time: 89ms
memory: 190644kb
input:
5000 1 2 3 4 3 2 5 8 8 5 11 9 12 13 14 13 10 16 7 15 13 20 20 22 23 25 27 20 26 16 27 32 23 14 26 15 27 25 29 29 31 21 41 37 43 43 46 30 43 43 50 44 52 40 35 42 52 31 52 41 47 35 38 58 32 50 67 31 62 25 70 42 25 56 58 31 74 67 56 57 64 59 81 81 76 82 86 74 43 59 61 64 64 81 75 64 58 44 82 65 92 70 9...
output:
577114100
result:
ok 1 number(s): "577114100"
Test #39:
score: 0
Accepted
time: 85ms
memory: 196992kb
input:
5000 1 2 3 3 4 6 7 8 7 9 11 11 12 14 14 15 15 14 13 18 20 21 17 23 5 26 18 28 14 22 22 24 33 28 27 22 17 37 33 29 36 41 35 28 31 33 42 38 31 49 19 32 33 37 49 52 41 47 52 38 29 59 41 50 52 65 62 35 17 61 62 38 73 63 72 22 47 71 64 78 56 78 50 36 49 63 75 50 83 44 52 79 76 86 95 81 89 64 76 72 72 97 ...
output:
178903931
result:
ok 1 number(s): "178903931"
Test #40:
score: 0
Accepted
time: 88ms
memory: 197136kb
input:
5000 1 2 3 3 4 4 4 6 6 6 11 12 13 14 14 16 12 18 15 6 20 13 23 14 19 19 20 19 26 29 16 25 20 33 15 35 30 38 24 36 16 42 30 44 39 33 31 46 40 43 39 28 45 46 53 39 32 27 49 60 50 35 44 43 46 43 58 52 66 59 27 61 61 71 72 70 73 70 79 51 66 34 52 81 66 75 43 47 79 90 81 85 58 87 70 91 96 89 67 80 31 92 ...
output:
675255564
result:
ok 1 number(s): "675255564"
Test #41:
score: 0
Accepted
time: 94ms
memory: 198552kb
input:
5000 1 2 3 4 4 6 7 5 9 8 10 6 11 14 14 12 17 8 10 14 20 16 19 20 14 18 23 19 28 28 31 7 20 34 33 33 21 20 22 36 33 17 30 35 36 34 47 37 11 39 29 39 48 48 35 37 30 28 46 50 52 60 49 40 49 39 55 66 51 44 49 60 35 67 50 72 51 58 64 80 79 76 65 53 70 55 84 77 52 61 60 91 50 87 67 80 54 73 63 99 70 78 70...
output:
195147938
result:
ok 1 number(s): "195147938"
Test #42:
score: 0
Accepted
time: 84ms
memory: 198636kb
input:
5000 1 2 3 4 4 4 6 7 8 10 9 12 13 10 14 6 15 14 13 12 20 21 23 22 23 12 14 28 27 28 26 24 28 11 35 16 34 25 20 37 23 39 38 35 38 46 47 45 43 44 49 31 37 53 33 48 53 53 58 40 36 52 53 38 64 48 52 52 33 61 57 64 54 52 30 74 68 46 76 79 66 64 42 80 75 83 58 85 47 89 83 58 21 90 68 94 55 86 60 99 70 79 ...
output:
212469262
result:
ok 1 number(s): "212469262"
Test #43:
score: 0
Accepted
time: 1ms
memory: 6000kb
input:
10 1 1 1 2 3 2 1 2 3 1 10
output:
0
result:
ok 1 number(s): "0"
Test #44:
score: 0
Accepted
time: 2ms
memory: 10396kb
input:
100 1 1 1 1 1 1 2 5 5 1 3 3 5 2 8 2 12 1 9 5 13 13 4 1 4 3 3 5 4 10 2 6 5 7 10 15 7 3 5 19 8 8 20 12 21 14 18 17 1 35 3 7 13 28 10 5 30 23 5 21 21 18 18 21 38 54 18 4 4 16 2 47 12 25 32 7 13 7 12 19 14 2 6 1 20 11 25 42 17 42 19 53 47 40 17 31 19 24 54 4 44
output:
211835866
result:
ok 1 number(s): "211835866"
Test #45:
score: 0
Accepted
time: 2ms
memory: 24832kb
input:
500 1 1 1 2 2 3 5 1 1 2 2 2 2 1 11 8 2 2 2 6 6 1 10 9 1 4 3 3 1 20 20 6 1 8 8 9 14 3 3 12 13 12 8 8 13 10 14 17 23 24 34 9 11 16 7 9 23 6 8 47 14 5 37 20 8 15 3 1 44 17 17 21 6 24 22 57 52 5 13 48 66 1 6 55 19 25 47 26 10 2 15 14 22 19 44 10 2 54 35 14 45 39 14 38 8 28 8 17 9 18 58 2 19 77 16 20 5 6...
output:
37541524
result:
ok 1 number(s): "37541524"
Test #46:
score: 0
Accepted
time: 0ms
memory: 43672kb
input:
1000 1 1 1 1 2 1 1 4 3 1 1 1 2 3 5 7 4 6 3 2 3 5 3 8 7 5 6 3 20 9 28 18 2 12 1 4 8 2 6 29 12 4 11 1 10 24 8 5 1 2 8 30 30 1 14 7 19 12 7 2 25 37 41 18 10 8 1 33 34 17 9 6 20 25 41 3 4 8 1 20 1 11 10 10 8 8 15 37 3 7 1 10 32 30 1 44 54 34 38 15 23 14 8 25 16 2 14 54 15 41 79 92 4 2 11 2 11 2 97 1 1 2...
output:
865872955
result:
ok 1 number(s): "865872955"
Test #47:
score: 0
Accepted
time: 59ms
memory: 196840kb
input:
5000 1 1 1 3 2 2 2 4 1 3 3 8 3 7 1 13 3 1 1 1 6 2 18 3 1 6 13 12 23 17 5 10 7 5 14 8 27 25 15 8 12 11 8 19 12 4 1 18 7 13 17 9 2 2 3 11 25 25 24 8 5 9 28 32 18 24 29 16 21 3 6 6 10 31 12 5 23 19 10 55 1 13 25 21 10 21 15 35 4 34 67 16 46 20 6 14 58 35 11 53 20 12 9 19 2 9 26 5 11 8 1 16 36 35 13 87 ...
output:
540272977
result:
ok 1 number(s): "540272977"
Test #48:
score: 0
Accepted
time: 16ms
memory: 196840kb
input:
5000 1 2 1 2 1 2 2 1 2 1 2 2 3 6 3 2 2 7 5 7 4 7 5 10 19 4 9 4 4 23 24 8 1 11 8 2 20 1 5 10 2 2 3 8 1 9 11 3 1 7 27 14 27 4 7 23 18 17 2 31 10 8 8 12 3 7 12 2 5 20 20 3 6 48 9 5 16 1 1 13 26 54 4 17 20 6 13 2 9 3 11 2 48 29 7 18 13 6 5 24 4 23 18 18 1 37 2 17 62 37 74 41 8 11 5 28 31 83 32 30 68 26 ...
output:
343721989
result:
ok 1 number(s): "343721989"
Test #49:
score: 0
Accepted
time: 79ms
memory: 196968kb
input:
5000 1 1 1 3 1 1 1 4 2 2 2 2 5 6 6 2 4 3 2 6 4 10 9 1 11 14 4 12 1 2 21 20 8 15 3 4 14 12 10 32 24 32 16 10 11 16 18 5 3 1 7 9 11 2 23 35 2 5 19 37 26 9 4 37 13 31 10 3 1 14 11 11 52 35 30 17 19 41 1 27 23 24 42 45 24 16 9 7 48 19 2 17 36 6 7 57 24 7 74 14 17 17 13 11 54 23 46 30 41 49 46 31 21 3 12...
output:
512669151
result:
ok 1 number(s): "512669151"
Test #50:
score: 0
Accepted
time: 27ms
memory: 198576kb
input:
5000 1 1 1 1 3 1 3 1 1 4 1 5 3 7 4 6 1 3 4 1 1 14 4 7 1 7 8 3 14 7 15 3 20 5 6 7 5 13 5 6 2 1 3 1 20 2 2 6 33 15 11 5 3 15 22 24 40 15 8 9 11 7 9 11 6 37 49 10 18 27 12 30 9 10 28 24 53 20 2 40 29 2 6 18 69 4 6 37 42 23 15 6 18 56 5 15 10 17 19 43 13 76 47 61 26 9 81 5 11 41 39 1 50 28 18 38 19 3 48...
output:
0
result:
ok 1 number(s): "0"
Test #51:
score: 0
Accepted
time: 51ms
memory: 196840kb
input:
5000 1 1 1 1 1 1 1 2 3 1 1 6 1 3 2 3 5 9 7 5 3 9 2 5 2 4 11 6 1 16 10 17 9 9 12 8 29 15 30 22 11 9 1 11 6 28 5 10 13 41 4 17 7 8 1 3 2 9 11 30 14 12 11 22 14 20 14 8 14 3 35 39 30 5 2 15 16 17 7 33 26 29 35 44 52 39 11 43 14 58 57 25 15 18 6 11 55 18 1 7 15 40 48 3 6 69 37 17 47 31 1 11 15 43 7 24 4...
output:
302907113
result:
ok 1 number(s): "302907113"
Test #52:
score: 0
Accepted
time: 51ms
memory: 168912kb
input:
5000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...
output:
1
result:
ok 1 number(s): "1"