QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291110 | #1998. Sleeping Cows | MoRanSky | 100 ✓ | 46ms | 59916kb | C++23 | 1.3kb | 2023-12-26 04:53:52 | 2023-12-26 04:53:52 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3005, P = 1e9 + 7;
int n, s[N], t[N], f[N][N], g[N][N], ans, fact[N];
void inline add(int &a, int b) {
(a += b) %= P;
}
int main() {
scanf("%d", &n);
fact[0] = 1;
for (int i = 1; i <= n; i++) scanf("%d", s + i), fact[i] = (LL)fact[i - 1] * i % P;
for (int i = 1; i <= n; i++) scanf("%d", t + i);
sort(s + 1, s + 1 + n);
sort(t + 1, t + 1 + n);
f[0][0] = 1;
for (int i = 1, j = 0; i <= n; i++) {
while (j < n && s[j + 1] <= t[i]) ++j;
for (int k = 0; k <= i; k++) {
if (!f[i - 1][k]) continue;
(f[i][k] += f[i - 1][k]) %= P;
if (j - k > 0) add(f[i][k + 1], (LL)f[i - 1][k] * (j - k) % P);
}
}
g[n + 1][0] = 1;
for (int i = n, j = n; i; i--) {
while (j && t[j] >= s[i]) j--;
for (int k = 0; k <= n - i; k++) {
if (!g[i + 1][k]) continue;
(g[i][k] += g[i + 1][k]) %= P;
if (n - j - k > 0) add(g[i][k + 1], (LL)g[i + 1][k] * (n - j - k) % P);
}
}
ans = f[n][n];
for (int i = n, j = n; i; i--) {
while (j && t[j] >= s[i]) j--;
int t = n - j;
for (int k = 0; k <= min(i - 1, t); k++) {
add(ans, (LL)f[j][i - 1 - k] * fact[k] % P * g[i + 1][t - k] % P);
}
}
printf("%d\n", ans);
return 0;
}
详细
Test #1:
score: 5
Accepted
time: 1ms
memory: 5864kb
input:
4 1 2 3 4 1 2 2 3
output:
9
result:
ok single line: '9'
Test #2:
score: 5
Accepted
time: 1ms
memory: 7992kb
input:
8 3 2 1 4 2 1 2 3 4 3 2 4 3 1 3 1
output:
12072
result:
ok single line: '12072'
Test #3:
score: 5
Accepted
time: 0ms
memory: 5992kb
input:
8 3 5 3 4 5 7 2 2 1 3 6 3 5 1 6 5
output:
2040
result:
ok single line: '2040'
Test #4:
score: 5
Accepted
time: 1ms
memory: 6144kb
input:
20 8 8 19 13 11 5 19 20 7 9 3 14 20 10 6 2 19 1 18 2 10 8 17 18 8 3 18 12 8 7 20 1 15 9 18 7 16 15 16 7
output:
616993812
result:
ok single line: '616993812'
Test #5:
score: 5
Accepted
time: 1ms
memory: 7972kb
input:
25 1 2 14 8 12 21 6 15 13 15 3 3 7 5 11 11 10 1 5 1 1 23 12 9 12 11 22 18 10 16 15 10 17 21 25 8 14 8 1 11 5 11 20 8 23 8 3 24 10 9
output:
768154666
result:
ok single line: '768154666'
Test #6:
score: 5
Accepted
time: 1ms
memory: 5968kb
input:
30 30 25 4 11 30 24 10 13 8 26 23 29 11 5 13 5 11 6 10 12 13 30 5 25 7 11 20 29 16 15 10 19 18 5 14 29 29 2 9 9 22 4 18 25 20 3 2 16 3 12 22 4 20 29 26 21 23 16 15 18
output:
600746778
result:
ok single line: '600746778'
Test #7:
score: 5
Accepted
time: 0ms
memory: 6024kb
input:
35 13 13 2 33 4 5 33 6 34 2 3 8 18 11 32 19 23 13 28 11 26 15 28 29 8 12 20 26 33 30 12 4 9 13 25 30 19 21 29 4 12 31 2 7 15 19 32 33 16 17 6 1 3 22 21 1 21 18 4 18 32 19 4 31 3 23 29 30 33 20
output:
996649995
result:
ok single line: '996649995'
Test #8:
score: 5
Accepted
time: 1ms
memory: 6148kb
input:
40 36 5 20 32 26 6 30 28 8 20 24 3 3 8 27 28 6 27 26 32 14 8 6 32 19 1 32 29 10 11 21 33 2 5 38 16 37 20 17 20 4 21 3 32 27 24 24 8 21 17 12 4 2 20 19 3 29 2 25 13 7 37 32 37 23 15 12 24 7 22 1 16 10 32 32 26 4 17 17 35
output:
101342743
result:
ok single line: '101342743'
Test #9:
score: 5
Accepted
time: 1ms
memory: 6068kb
input:
45 24 43 24 14 21 35 3 37 25 15 2 4 13 33 10 2 32 30 17 23 17 15 1 38 29 40 39 22 15 41 19 4 22 35 40 21 45 24 12 39 27 42 44 14 20 41 6 14 33 26 30 30 9 22 17 29 25 41 23 26 9 16 29 16 40 38 19 23 41 13 30 45 37 11 24 41 34 4 37 34 27 39 43 16 25 27 2 4 42 14
output:
277071326
result:
ok single line: '277071326'
Test #10:
score: 5
Accepted
time: 1ms
memory: 6068kb
input:
50 21 21 30 39 35 3 50 37 33 49 24 41 36 15 10 35 8 47 11 39 28 16 32 3 31 11 26 9 4 7 16 22 45 38 1 15 43 38 40 5 31 35 6 38 18 32 15 13 37 13 50 18 13 47 47 37 21 42 16 11 9 6 15 8 9 10 37 50 24 45 34 4 40 38 5 30 46 20 46 40 27 32 18 15 45 1 46 48 12 9 35 17 6 37 22 42 10 13 12 18
output:
206821887
result:
ok single line: '206821887'
Test #11:
score: 5
Accepted
time: 1ms
memory: 6216kb
input:
50 12 6 39 42 38 3 5 23 2 17 11 34 30 29 50 38 29 21 17 42 12 40 30 50 23 11 29 18 44 19 28 23 3 43 17 23 14 4 34 45 33 37 22 26 35 6 26 6 27 43 26 21 1 11 33 23 38 18 25 38 20 6 16 3 14 50 25 6 43 2 9 3 18 38 7 26 44 15 18 4 40 35 42 36 7 19 6 5 37 47 36 36 44 41 41 39 41 15 2 26
output:
48921366
result:
ok single line: '48921366'
Test #12:
score: 5
Accepted
time: 0ms
memory: 8056kb
input:
50 603618638 509652945 452821761 905343134 993119856 107402479 21661115 985366232 5403647 929670929 300628454 267418479 486075146 994923192 738208756 149576834 5343299 979112541 698973388 833524162 224337024 664535212 221379755 109775435 300881621 187224177 934765201 678265894 83671953 254207039 226...
output:
567180283
result:
ok single line: '567180283'
Test #13:
score: 5
Accepted
time: 2ms
memory: 9112kb
input:
200 67 151 52 3 131 175 155 8 38 92 86 59 157 107 21 3 72 3 118 125 168 15 182 31 36 65 167 160 25 85 162 83 88 155 177 165 176 98 86 50 98 66 199 173 120 10 56 56 38 39 56 91 156 75 134 188 160 108 151 171 198 51 125 200 1 152 178 162 89 136 58 57 28 86 111 101 151 88 194 87 47 83 125 72 99 35 33 1...
output:
334149037
result:
ok single line: '334149037'
Test #14:
score: 5
Accepted
time: 4ms
memory: 11800kb
input:
500 267 74 460 436 204 118 137 321 156 159 146 170 50 180 447 197 351 182 482 31 332 252 344 114 19 113 114 184 427 277 35 218 104 287 195 97 491 175 56 345 56 228 52 295 73 499 121 194 119 110 459 359 478 201 153 400 40 305 59 499 155 347 344 476 418 97 96 131 317 195 431 447 32 92 183 90 44 275 16...
output:
264346009
result:
ok single line: '264346009'
Test #15:
score: 5
Accepted
time: 7ms
memory: 18464kb
input:
1000 185 632 753 894 853 886 300 817 548 690 731 165 743 219 720 86 824 543 133 641 674 820 441 747 477 748 646 149 951 698 367 53 192 81 366 767 908 946 491 747 487 419 908 183 650 16 972 316 514 165 528 902 843 636 65 717 929 689 390 371 200 951 249 614 189 324 150 682 630 3 739 581 560 199 750 45...
output:
95176409
result:
ok single line: '95176409'
Test #16:
score: 5
Accepted
time: 11ms
memory: 28364kb
input:
1500 932 763 53 26 190 149 256 482 838 340 182 1463 1464 533 796 606 39 1314 123 927 1438 1449 491 997 1151 429 249 694 285 116 368 229 178 140 751 436 484 553 1172 1229 1185 726 144 1321 26 703 273 366 1090 802 213 818 433 1341 331 655 291 942 986 582 308 104 738 675 648 802 671 805 1292 1152 117 1...
output:
351371671
result:
ok single line: '351371671'
Test #17:
score: 5
Accepted
time: 27ms
memory: 38972kb
input:
2000 687 206 860 1775 152 653 1948 964 97 955 1333 1126 1296 451 1854 1833 426 98 1971 957 221 792 1234 1300 232 904 1 864 1857 1944 1237 332 233 680 1935 736 568 1886 160 720 1723 1782 1369 77 1602 892 1991 188 1036 1439 1233 191 1117 709 1801 1182 1623 381 1264 1578 1105 1569 170 333 791 1508 1322...
output:
606726949
result:
ok single line: '606726949'
Test #18:
score: 5
Accepted
time: 39ms
memory: 51056kb
input:
2500 1485 1755 2439 461 963 1630 1767 1554 1172 1482 907 553 1192 1573 2083 2406 1297 921 698 1141 1196 729 56 864 106 1558 607 719 182 1482 131 1557 114 851 989 303 1258 1567 1122 2457 1876 1349 362 1944 1240 328 1934 968 1882 1292 1786 43 1094 1430 1207 2009 2405 1891 1287 1178 613 555 1175 82 149...
output:
356358931
result:
ok single line: '356358931'
Test #19:
score: 5
Accepted
time: 35ms
memory: 59544kb
input:
3000 1928 708 1075 2062 20 924 788 2179 1571 2995 2169 1003 2845 556 902 1702 1885 1521 1227 2861 1013 1067 216 2674 155 1939 414 284 665 1591 178 2352 108 1984 2734 196 1391 2366 882 1903 2408 1885 1069 1276 1837 2512 2739 2516 2031 899 531 867 2605 2544 2895 118 2624 1424 1042 277 601 2628 1928 25...
output:
396583147
result:
ok single line: '396583147'
Test #20:
score: 5
Accepted
time: 46ms
memory: 59916kb
input:
3000 340484567 609927689 958770433 743372661 126678386 279388839 49653654 180951838 761205793 153056723 607734253 116419711 518864047 374424827 828499845 691742000 523756744 264292472 736277539 835174816 226863820 727282222 444262377 858246285 43107010 129651085 791861087 326513954 722218064 1809767...
output:
124485458
result:
ok single line: '124485458'