QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#465309 | #9. 简单回路 | Ciriya666 | 0 | 27ms | 13144kb | Python3 | 1.9kb | 2024-07-06 20:00:56 | 2024-07-06 20:00:58 |
Judging History
answer
MOD = 1000000007
def count_valid_simple_loops(n, m, k, obstacles, queries):
# Initialize grid and obstacles
grid = [[0] * (m + 1) for _ in range(n + 1)]
for obstacle in obstacles:
x, y = obstacle
grid[x][y] = 1
# Initialize dp array
dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[1][1] = 1 # Start point
# Compute dp array
for i in range(1, n + 1):
for j in range(1, m + 1):
if i == 1 and j == 1:
continue
if grid[i][j] == 1:
dp[i][j] = 0
else:
if i > 1:
dp[i][j] += dp[i - 1][j]
if j > 1:
dp[i][j] += dp[i][j - 1]
dp[i][j] %= MOD
# Compute prefix sums for dp array
prefix_dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
prefix_dp[i][j] = (dp[i][j] + prefix_dp[i - 1][j] + prefix_dp[i][j - 1] - prefix_dp[i - 1][j - 1]) % MOD
# Answer queries
results = []
for query in queries:
x, y = query
if x > 1:
result = (prefix_dp[x][y] - prefix_dp[x - 1][y]) % MOD
else:
result = prefix_dp[x][y] % MOD
results.append(result)
return results
# Reading input
import sys
input = sys.stdin.read().split()
n = int(input[0])
m = int(input[1])
k = int(input[2])
obstacles = []
index = 3
for _ in range(k):
x = int(input[index])
y = int(input[index + 1])
obstacles.append((x, y))
index += 2
Q = int(input[index])
queries = []
index += 1
for _ in range(Q):
x = int(input[index])
y = int(input[index + 1])
queries.append((x, y))
index += 2
# Solve the problem
results = count_valid_simple_loops(n, m, k, obstacles, queries)
# Print results
for result in results:
print(result)
詳細信息
Test #1:
score: 0
Wrong Answer
time: 15ms
memory: 10684kb
input:
100 1 10 68 1 13 1 48 1 51 1 30 1 90 1 74 1 79 1 80 1 63 1 10 73 1 84 1 10 1 44 1 3 1 16 1 17 1 47 1 49 1 94 1
output:
0 0 1 0 1 0 0 0 0 0
result:
wrong answer 3rd lines differ - expected: '0', found: '1'
Test #2:
score: 0
Wrong Answer
time: 9ms
memory: 10940kb
input:
1000 2 10 468 2 177 1 597 1 396 1 548 2 279 1 601 1 349 1 453 2 217 2 100 954 1 468 1 427 2 948 1 739 2 605 2 177 1 20 2 506 1 778 2 141 1 621 1 273 1 203 2 584 2 718 2 371 2 973 2 892 2 374 2 585 2 419 2 953 2 347 2 575 2 353 2 830 1 196 1 603 2 630 2 144 2 84 2 566 1 598 2 749 1 878 1 322 1 250 2 ...
output:
0 0 0 0 0 0 0 21 0 0 1 0 0 176 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 145 85 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 135 0 85 0 0 0 176 0 1 41 0 0 1 0 0 1 0 0 0 0 0 0 1 0 28 0 0 0 0 127 0 58 0 0 0 0 0 0
result:
wrong answer 1st lines differ - expected: '16238', found: '0'
Test #3:
score: 0
Wrong Answer
time: 15ms
memory: 10976kb
input:
1000 2 10 378 2 63 1 276 2 245 2 826 1 422 1 634 1 970 1 707 1 386 1 100 987 1 262 2 913 1 201 1 685 1 969 2 382 1 460 1 45 1 535 2 54 2 16 2 436 2 668 1 136 1 210 1 660 2 956 1 743 1 549 2 228 2 967 2 624 2 465 1 135 1 854 1 593 1 359 2 941 1 459 1 456 2 763 2 558 2 116 2 38 2 187 2 108 2 749 1 911...
output:
0 0 0 0 0 0 0 0 1 0 55 17 0 0 0 0 0 0 0 0 62 0 0 0 0 0 0 0 0 0 0 0 0 62 39 62 62 0 0 62 0 0 62 61 0 0 0 0 0 0 0 0 0 0 0 0 0 22 0 1 0 59 0 0 0 0 62 0 62 0 0 43 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 62 0 0 0 0 62 0 0 0
result:
wrong answer 1st lines differ - expected: '221', found: '0'
Test #4:
score: 0
Wrong Answer
time: 15ms
memory: 11132kb
input:
1000 3 10 186 3 140 3 410 1 639 1 836 2 399 2 432 3 712 1 946 3 958 3 100 203 3 895 1 351 1 503 2 991 1 61 2 760 1 647 3 70 3 75 1 522 2 539 3 417 1 53 2 404 1 467 2 283 1 313 2 793 3 290 2 410 1 827 1 572 1 534 3 765 2 977 1 97 3 797 3 966 3 404 2 479 1 653 3 212 2 164 2 960 1 655 1 304 1 182 1 190...
output:
3519 0 1 10 0 62 0 2160 2556 1 10 1080 0 54 1 10 1 314 3620 291 0 0 0 1030 10 0 4851 3660 0 6 0 2220 213 165 0 0 1 1 945 239 1540 0 3750 1 1 1 113 209 10 359 10 10 1 10 0 2590 327 10 1 0 1 1 0 7875 20835 3020 0 200 1 0 0 352 312 0 0 0 0 3220 43684 0 0 0 1 0 0 0 960 0 388 6601 3610 980 3724 1 10 1431...
result:
wrong answer 1st lines differ - expected: '774407976', found: '3519'
Test #5:
score: 0
Wrong Answer
time: 17ms
memory: 11080kb
input:
1000 5 10 230 1 368 1 815 1 540 3 496 4 860 4 892 1 183 2 175 2 704 1 100 365 1 79 5 154 1 775 4 451 2 382 2 641 2 509 2 613 4 629 2 24 3 628 4 438 2 894 5 386 3 588 5 742 2 700 2 470 5 333 4 347 3 824 2 98 2 946 4 359 4 199 3 903 1 13 2 545 4 718 5 158 3 462 5 15 3 138 5 101 3 525 5 394 2 282 3 566...
output:
0 1837620 1 2560440 46 46 46 46 1401654 46 325 1458234 46 999868163 23602 395995133 46 46 125942819 3720331 21808 46 99 1456728 4286741 15406 0 14 1274970 605368323 12720 70272195 136 16234505 5253 317148107 46 18818 46 1213737 3185017 333885037 593400529 162 46 0 47 1 740486819 21302 157 3891299 11...
result:
wrong answer 1st lines differ - expected: '255313133', found: '0'
Test #6:
score: 0
Wrong Answer
time: 17ms
memory: 11444kb
input:
1000 6 10 459 1 653 6 840 4 256 3 298 1 841 2 749 1 30 5 155 2 534 5 100 703 1 169 2 577 3 818 1 784 5 520 3 106 5 52 4 38 1 533 1 729 4 88 4 586 5 828 6 547 1 194 2 74 4 448 3 673 6 778 1 180 3 612 1 814 6 784 6 658 3 969 3 350 5 606 2 257 1 753 3 309 4 480 4 355 4 33 2 47 4 195 3 282 4 867 5 226 4...
output:
0 15 44904 0 430393134 36810 5732265 26235 1 0 17605385 121485 445272027 565288018 0 40 73150 26586 946037511 0 12286 0 483466393 208722989 56406 82108 362792685 142 1 69896 2175005 5434265 2643515 34 19600 12796 2039587 737966615 1556699 622789382 19104047 2712545 277593107 0 597801584 10492787 262...
result:
wrong answer 1st lines differ - expected: '999278415', found: '0'
Test #7:
score: 0
Wrong Answer
time: 27ms
memory: 13056kb
input:
1000 6 10 322 5 8 2 165 5 590 3 823 6 171 1 987 1 130 2 474 3 838 5 10000 854 4 329 1 324 2 361 4 479 4 657 6 27 1 121 3 57 5 790 4 81 1 246 3 720 5 917 4 430 6 506 3 129 3 752 2 119 6 382 1 146 4 233 3 420 5 20 1 413 5 925 5 466 4 682 5 632 4 128 4 574 1 503 4 543 1 274 3 273 5 742 2 399 4 36 3 237...
output:
6633597 0 40 2942458 4957837 239454741 1 6583 334447 6035837 1 11309 830843411 7382037 579509601 1320 7531 40 167868064 0 440452 10789 308888052 1 281607078 611923576 4835503 622543485 5261637 306121 0 4975597 0 12429 120294575 40 3576640 463 992604910 903743732 17750668 315616 724299451 7737197 491...
result:
wrong answer 1st lines differ - expected: '595188785', found: '6633597'
Test #8:
score: 0
Wrong Answer
time: 16ms
memory: 13032kb
input:
1000 6 10 454 6 42 2 861 3 46 2 592 2 220 1 641 1 415 4 687 3 803 5 10000 646 2 362 3 870 5 523 5 589 4 984 1 981 1 361 4 496 5 584 2 271 1 707 1 111 5 714 3 855 4 793 5 943 2 459 2 422 2 194 6 404 6 786 3 12 5 33 6 628 3 199 1 87 2 882 4 207 2 890 5 121 5 769 2 611 2 398 5 869 6 479 6 926 1 952 4 3...
output:
0 40830 298123665 116845313 11383750 0 0 5102110 965806465 173 0 0 4091532 0 19090054 232594196 0 173 173 361375312 29546199 0 1820 501942 80274 1 42 19090054 162 679924745 5516057 0 0 673079285 439463965 251169761 0 19090054 173 6753 0 0 0 757998 0 4495 1963869 1842102 19090054 279033611 173 80274 ...
result:
wrong answer 1st lines differ - expected: '907977256', found: '0'
Test #9:
score: 0
Wrong Answer
time: 23ms
memory: 13008kb
input:
1000 6 10 855 4 342 2 897 3 652 6 279 2 715 3 439 1 582 6 711 1 249 3 10000 581 2 907 2 221 6 92 2 355 3 342 2 130 5 820 6 90 2 802 1 803 1 87 3 170 5 553 4 432 2 891 1 523 2 519 4 174 6 933 6 796 3 691 6 982 5 871 1 430 6 230 2 133 6 271 4 442 6 268 6 452 5 656 2 502 3 14 3 248 2 470 2 710 5 954 5 ...
output:
96 96 699109492 93 9714 1 12840751 11061628 91 0 0 3916 36890001 6600167 91 0 96 5790389 447490653 449250666 7872 926364315 644831156 0 715559313 231 387610812 2644024 121660684 124550865 852091923 96 20505 120 249 96 820813412 619838132 135 96 15552 160 487936464 142233807 0 7662 96 96 11712 96 290...
result:
wrong answer 1st lines differ - expected: '55066393', found: '96'
Test #10:
score: 0
Wrong Answer
time: 22ms
memory: 13144kb
input:
1000 6 10 959 3 380 5 181 5 388 6 749 5 342 5 944 1 918 3 870 1 753 4 10000 383 4 321 3 646 1 893 4 776 3 664 2 518 5 234 1 114 6 639 1 764 1 207 1 877 3 273 5 764 1 799 5 385 6 314 3 982 6 784 6 819 5 83 6 651 4 221 3 355 1 829 4 144 6 862 3 786 2 385 6 857 4 53 4 55 4 710 4 186 2 735 2 878 3 955 5...
output:
9511040 52003 1 48039770 302253 665 175621731 1 182637273 1 1 1 385836 193809799 1 546951220 614057958 49770 691810278 784400433 899680375 39175752 46407404 24753 1 24199175 571880029 372816 787 614057958 34196435 27720 30856 60157236 187 736 386705 898344849 21528 58084541 25754162 9 845 216153 127...
result:
wrong answer 1st lines differ - expected: '933292809', found: '9511040'