QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#465309#9. 简单回路Ciriya6660 27ms13144kbPython31.9kb2024-07-06 20:00:562024-07-06 20:00:58

Judging History

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

  • [2024-07-06 20:00:58]
  • 评测
  • 测评结果:0
  • 用时:27ms
  • 内存:13144kb
  • [2024-07-06 20:00:56]
  • 提交

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'