QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153493#6756. 桂花树zlxFTH70 81ms3656kbC++143.2kb2023-08-30 08:23:272023-08-30 08:23:28

Judging History

你现在查看的是最新测评结果

  • [2023-08-30 08:23:28]
  • 评测
  • 测评结果:70
  • 用时:81ms
  • 内存:3656kb
  • [2023-08-30 08:23:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 3e4 + 5;
const int M = 3005;
const int mod = 1e9 + 7;

inline int qp(int a, int b = mod - 2) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    b /= 2;
  }
  return res;
}

int tc;
int n, m, K;
int fa[N];

inline int lca(int u, int v) {
  map<int, int> mp;
  int cur = u;
  while (cur) {
    mp[cur] = 1;
    cur = fa[cur];
  }
  cur = v;
  while (mp.find(cur) == mp.end()) {
    cur = fa[cur];
  }
  return cur;
}

namespace Sub1 {
int bl[N + M], Lca[10][10];
inline int find(int u) {
  while (u != bl[u]) {
    u = bl[u] = bl[bl[u]];
  }
  return u;
}
inline void merge(int u, int v) {
  u = find(u), v = find(v);
  bl[u] = v;
}

int to[N + M];
inline int LCA(int u, int v) {
  static int mp[10];
  memset(mp, 0, sizeof mp);
  int cur = u;
  while (cur) {
    mp[cur] = 1;
    cur = to[cur];
  }
  cur = v;
  while (!mp[cur]) {
    cur = to[cur];
  }
  return cur;
}

int ans;
void check() {
  int tot = n + m;
  iota(bl + 1, bl + tot + 1, 1);
  for (int i = 1; i <= tot; i++) if (to[i]) {
    merge(to[i], i);
  }
  int cnt = 0;
  for (int i = 1; i <= tot; i++) {
    cnt += (bl[i] == i);
    if (cnt > 1) return;
  }
  for (int i = 1; i <= tot; i++) {
    for (int j = i + 1; j <= tot; j++) {
      int u = LCA(i, j);
      if (i <= n && j <= n) {
        int v = Lca[i][j];
        if (u != v) return;
      }
      if (u > max(i, j) + K) return;
    }
  }
  (++ans) %= mod;
}
void dfs(int u) {
  if (u == n + m + 1) {
    check();
    return;
  }
  if (u == 1) {
    to[u] = 0;
    dfs(u + 1);
    return;
  }
  for (int v = 1; v <= n + m; v++) {
    if (u == v) continue;
    to[u] = v;
    if (v < u && to[v] == u) continue;
    dfs(u + 1);
  }
}
void main() {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      Lca[i][j] = lca(i, j);
    }
  }
  ans = 0;
  dfs(1);
  cout << ans << "\n";
}
}

void solve() {
  cin >> n >> m >> K;
  for (int i = 2; i <= n; i++) {
    cin >> fa[i];
  }
  if (n + m <= 8) {
    Sub1::main();
    return;
  }
  if (m == 0) {
    cout << 1 << "\n";
    return;
  }
  if (m == 1) {
    cout << (2 * n - 1) % mod << "\n";
    return;
  }
  if (m == 2) {
    int ans = 0;
    if (K > 0) {
      (ans += n * 2 % mod) %= mod;
      (ans += 1ll * n * n % mod) %= mod;
      (ans += 1ll * (n - 1) * n * 2 % mod) %= mod;
      (ans += 1ll * (n - 1) * (n - 2) % mod) %= mod;
      (ans += 4ll * (n - 1) % mod) %= mod;
    } else {
      (ans += n * 2 % mod) %= mod;
      (ans += 1ll * n * n % mod) %= mod;
      (ans += 1ll * (n - 1) * n * 2 % mod) %= mod;
      (ans += 1ll * (n - 1) * (n - 2) % mod) %= mod;
      (ans += 3ll * (n - 1) % mod) %= mod;
    }
    cout << ans << "\n";
    return;
  }
  // if (n == 1 && K == 0) {
  if (K == 0) {
    int ans = 1;
    for (int i = 1; i <= m; i++) {
      ans = 1ll * ans * (2 * i - 1 + 2 * (n - 1)) % mod;
    }
    cout << ans << "\n";
    return;
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> tc >> t;
  while (t--) solve();
  return 0;
}

详细

Test #1:

score: 5
Accepted
time: 81ms
memory: 3436kb

input:

1 15
4 2 9
1 2 3
4 4 1
1 1 1
4 3 10
1 2 3
4 2 10
1 2 3
2 3 0
1
2 2 8
1
2 4 10
1
3 3 0
1 2
3 2 0
1 1
2 2 0
1
2 4 9
1
4 2 0
1 1 1
2 4 1
1
4 4 8
1 1 1
3 3 0
1 2

output:

66
10132
787
66
105
16
1296
315
35
15
1296
63
1110
11384
315

result:

ok 15 numbers

Test #2:

score: 5
Accepted
time: 49ms
memory: 3472kb

input:

2 15
4 2 0
1 1 1
3 4 8
1 2
2 2 9
1
3 4 0
1 1
4 2 9
1 1 1
3 4 2
1 1
3 3 10
1 1
3 3 0
1 2
3 2 0
1 1
3 2 0
1 1
3 4 2
1 2
2 2 0
1
2 2 0
1
4 4 8
1 1 2
3 2 0
1 2

output:

63
4553
16
3465
66
4347
366
315
35
35
4347
15
15
11384
35

result:

ok 15 numbers

Test #3:

score: 5
Accepted
time: 21ms
memory: 3556kb

input:

3 15
25363 0 10
1 2 2 4 5 6 5 7 5 7 7 8 13 11 13 12 17 14 19 20 20 22 23 24 22 26 26 24 28 28 30 32 32 30 34 33 35 34 38 37 41 41 40 40 42 46 45 44 47 49 51 49 51 54 54 56 55 58 57 59 60 62 60 61 64 65 63 65 68 66 70 68 69 74 75 72 76 77 78 77 77 78 79 84 83 83 85 87 89 90 91 90 90 91 93 93 97 95 98...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 15 numbers

Test #4:

score: 5
Accepted
time: 0ms
memory: 3400kb

input:

4 15
95 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
81 1 0
1 1 3 3 2 4 4 4 7 8 8 11 11 12 15 16 17 18 19 17 19 22 20 22 24 25 27 24 25 26 28 29 32 33 32...

output:

189
161
157
183
179
179
185
165
161
179
191
159
199
177
195

result:

ok 15 numbers

Test #5:

score: 5
Accepted
time: 8ms
memory: 3656kb

input:

5 15
24238 1 9
1 2 2 3 2 3 7 6 6 8 11 8 13 14 14 13 14 15 15 20 17 21 19 24 25 22 23 28 27 29 28 31 32 34 35 32 35 35 39 37 38 42 39 41 43 42 47 47 45 48 49 52 50 52 51 55 53 57 58 58 60 58 60 64 62 66 66 65 65 69 68 68 73 71 72 73 75 78 77 76 78 82 81 84 82 85 84 87 86 89 90 90 90 90 91 93 94 94 98...

output:

48475
54131
56879
54501
49951
55359
46639
52775
56387
53417
55987
58213
48849
46865
56865

result:

ok 15 numbers

Test #6:

score: 5
Accepted
time: 1ms
memory: 3428kb

input:

6 15
90 2 0
1 1 3 3 4 6 3 5 6 1 4 8 6 3 7 2 8 17 12 1 15 8 10 17 4 7 22 1 16 15 13 17 6 24 18 20 29 24 5 37 26 19 1 36 10 11 1 32 12 29 25 36 43 25 36 35 27 30 48 13 57 43 3 48 20 49 10 42 33 32 15 67 3 72 18 59 45 65 22 47 21 76 44 36 70 31 40 36 75
97 2 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

32399
37731
39999
28223
29668
37731
36193
26895
35436
39301
33946
31771
30975
24335
36958

result:

ok 15 numbers

Test #7:

score: 5
Accepted
time: 22ms
memory: 3656kb

input:

7 15
23937 2 0
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 ...

output:

291919861
146761194
947431229
721917569
513436690
452531920
95169750
435600974
157568937
921186289
544059002
432348666
320565654
309379121
377927681

result:

ok 15 numbers

Test #8:

score: 5
Accepted
time: 1ms
memory: 3536kb

input:

8 15
1 89 0

1 88 0

1 86 0

1 81 0

1 89 0

1 88 0

1 85 0

1 88 0

1 99 0

1 93 0

1 94 0

1 79 0

1 97 0

1 88 0

1 96 0


output:

643555007
320020087
809556406
776533926
643555007
320020087
414090976
320020087
356146221
792287148
157695640
15616881
389622706
320020087
654868516

result:

ok 15 numbers

Test #9:

score: 5
Accepted
time: 1ms
memory: 3532kb

input:

9 15
1 85 0

1 86 0

1 90 0

1 87 0

1 87 0

1 91 0

1 81 0

1 79 0

1 86 0

1 80 0

1 81 0

1 88 0

1 98 0

1 89 0

1 78 0


output:

414090976
809556406
196345448
53257258
53257258
538525843
776533926
15616881
809556406
483084065
776533926
320020087
976427145
643555007
299462530

result:

ok 15 numbers

Test #10:

score: 5
Accepted
time: 1ms
memory: 3464kb

input:

10 15
1 2600 0

1 2562 0

1 2885 0

1 2926 0

1 2980 0

1 2796 0

1 2809 0

1 2441 0

1 2964 0

1 2384 0

1 2634 0

1 2284 0

1 2732 0

1 2525 0

1 2635 0


output:

980378455
337526154
558193103
125913045
124855760
503883918
199525532
902720193
515375300
777422724
363348923
334557029
939566213
938891504
485461889

result:

ok 15 numbers

Test #11:

score: 0
Wrong Answer
time: 1ms
memory: 3416kb

input:

11 15
1 97 8

1 98 8

1 75 9

1 86 10

1 91 10

1 80 10

1 99 10

1 75 10

1 81 3

1 86 8

1 76 10

1 79 9

1 77 9

1 79 8

1 92 10


output:


result:

wrong answer Answer contains longer sequence [length = 15], but output contains 0 elements

Test #12:

score: 0
Wrong Answer
time: 1ms
memory: 3464kb

input:

12 15
1 2419 9

1 3000 8

1 2952 9

1 2911 10

1 2596 8

1 2997 10

1 2479 10

1 2447 10

1 2504 8

1 2325 9

1 2473 10

1 2674 8

1 2817 9

1 2303 8

1 2253 6


output:


result:

wrong answer Answer contains longer sequence [length = 15], but output contains 0 elements

Test #13:

score: 5
Accepted
time: 1ms
memory: 3408kb

input:

13 15
96 77 0
1 1 2 2 3 3 4 4 5 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 8 8 65 17 9 33 83 76 52 42 17 56 39 82 26 53
89 96 0
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 ...

output:

875522633
817514869
984115449
171618725
413906221
67403237
626927815
102038917
731937401
81736574
147698013
5718686
570093465
291610
736092684

result:

ok 15 numbers

Test #14:

score: 5
Accepted
time: 1ms
memory: 3436kb

input:

14 15
79 92 0
1 2 1 3 2 5 6 6 6 10 7 8 10 13 14 13 15 16 17 18 17 18 21 24 25 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 18 33 33 18 9 48 19 2 6 12 28 3 22 50 5 24 14 10 15 42 11 44 36 38 58 21 9
96 81 0
1 2 3 4 3 2 4 7 7 1 7 10 12 13 1 9 14 6 13 18 4 2 4 14 25 3 3...

output:

69626057
106800079
696160675
125365500
105229737
980457872
857341479
727730150
931017912
72350415
700427628
857341479
458562426
105229737
33015237

result:

ok 15 numbers

Test #15:

score: 5
Accepted
time: 10ms
memory: 3600kb

input:

15 15
27219 2720 0
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...

output:

512213075
634563835
412223891
885815756
909933373
460122433
143582817
318866407
952581018
559698410
15451972
798343658
240180291
40997907
507956430

result:

ok 15 numbers

Test #16:

score: 5
Accepted
time: 14ms
memory: 3548kb

input:

16 15
23470 2270 0
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...

output:

613353516
498696894
341174230
524070747
458732519
657246209
497631698
460156266
650070681
438365748
579953962
638226266
303839474
655729798
51100917

result:

ok 15 numbers

Test #17:

score: 0
Wrong Answer
time: 0ms
memory: 3428kb

input:

17 15
94 82 9
1 2 2 3 3 6 6 8 6 10 7 10 13 10 14 14 16 17 18 17 20 18 23 24 22 26 25 27 25 26 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 59 39 56 52 21 51 66 59 33 68 29 34 62 47 59 76 54 72 40 40 3 4 63 33 44 73 59 18 19 70 25 77
93 86 8
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:


result:

wrong answer Answer contains longer sequence [length = 15], but output contains 0 elements

Test #18:

score: 0
Wrong Answer
time: 1ms
memory: 3420kb

input:

18 15
78 96 1
1 1 2 2 3 3 4 4 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 7 7 52 54 22 16 21 56 64 32 42 64 52 49 19
87 86 9
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:


result:

wrong answer Answer contains longer sequence [length = 15], but output contains 0 elements

Test #19:

score: 0
Wrong Answer
time: 18ms
memory: 3548kb

input:

19 15
26104 2591 3
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...

output:


result:

wrong answer Answer contains longer sequence [length = 15], but output contains 0 elements

Test #20:

score: 0
Wrong Answer
time: 19ms
memory: 3540kb

input:

20 15
22821 2558 8
1 1 1 3 2 4 2 5 5 5 7 7 13 4 15 12 1 17 15 6 10 10 13 20 20 1 16 14 9 9 28 24 14 28 2 28 35 20 30 37 1 9 21 35 42 23 41 11 15 29 10 1 13 6 24 11 11 46 32 39 32 10 59 57 20 24 51 24 60 28 65 16 31 42 25 12 27 28 53 49 15 12 58 73 83 47 7 71 2 2 26 57 82 61 17 17 48 96 23 83 2 41 59...

output:


result:

wrong answer Answer contains longer sequence [length = 15], but output contains 0 elements