UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197749#2710. Grid Walktkswls1001644ms16924kbC++1.3kb2023-11-14 10:26:232023-11-14 12:03:23

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int t, n, m, k;
const ll mod = 1000000007;
ll jie[1000016], inv[1000016], f[2005];
inline ll ksm(ll p, ll q = mod - 2) {
	ll base = 1;
	while (q) {
		if (q & 1) base = base * p % mod;
		q >>= 1;
		p = p * p % mod;
	}
	return base;
}
inline ll C(int p, int q) {
	return jie[p] * inv[q] % mod * inv[p - q] % mod;
}
inline ll get_ans(int p, int q) { // p行 q 列网格图 方案数
	return C(q + p - 2, p - 1);
}
struct node {
	int x, y;
} b[2005];
bool cmp(node p, node q) {
	return (p.x == q.x) ? (p.y < q.y) : (p.x < q.x);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	jie[0] = 1;
	for (int i = 1; i <= 1000005; i++) {
		jie[i] = jie[i - 1] * i % mod;
	}
	inv[1000005] = ksm(jie[1000005]);
	for (int i = 1000004; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
	cin >> t;
	while (t--) {
		cin >> n >> m >> k;
		for (int i = 1; i <= k; i++) {
			cin >> b[i].x >> b[i].y;
		}
		b[++k] = node{n, m};
		sort(b + 1, b + k + 1, cmp);
		for (int i = 1; i <= k; i++) {
			f[i] = get_ans(b[i].x, b[i].y);
			for (int j = 1; j < i; j++) {
				if (b[j].x <= b[i].x && b[j].y <= b[i].y) {
					f[i] = (f[i] + mod - f[j] * get_ans(b[i].x - b[j].x + 1, b[i].y - b[j].y + 1) % mod) % mod;
				}
			}
		}
		cout << f[k] << "\n";
	}
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 84ms
memory: 16924kb

input:

5
1647 1919 2000
671 415
1640 499
812 187
479 239
1085 600
816 717
1298 1458
726 1399
722 896
372 80...

output:

377000217
399221016
806541777
277049805
210022893

result:

ok 5 lines

Test #2:

score: 5
Accepted
time: 79ms
memory: 16920kb

input:

5
1638 1359 2000
1110 206
145 922
459 179
881 122
1254 1131
658 88
272 377
923 408
1616 703
374 1031...

output:

986097449
550531267
618817688
536374685
631251709

result:

ok 5 lines

Test #3:

score: 5
Accepted
time: 84ms
memory: 16924kb

input:

5
1452 1423 2000
248 777
1250 342
996 1341
1279 56
1152 554
645 1123
622 1085
323 584
1394 270
334 1...

output:

119792100
844541168
391949339
992605134
332171730

result:

ok 5 lines

Test #4:

score: 5
Accepted
time: 88ms
memory: 16924kb

input:

5
1310 1148 2000
771 778
364 1073
407 869
907 316
1228 458
58 134
1135 733
1199 998
150 1026
864 560...

output:

477903576
850182935
477392181
317164821
366923491

result:

ok 5 lines

Test #5:

score: 5
Accepted
time: 83ms
memory: 16924kb

input:

5
1303 1057 2000
1078 302
652 24
287 805
70 803
721 825
396 287
799 302
1070 583
435 34
1264 326
365...

output:

505970666
659095790
806001196
199671186
995466458

result:

ok 5 lines

Test #6:

score: 5
Accepted
time: 83ms
memory: 16924kb

input:

5
1865 1000 2000
1827 819
418 796
1786 868
66 552
1000 445
1393 677
975 889
1049 617
246 808
1188 88...

output:

744749949
129418597
702360779
916158602
140217126

result:

ok 5 lines

Test #7:

score: 5
Accepted
time: 16ms
memory: 16884kb

input:

5
156853 182494 0
131754 128585 0
158639 110178 0
145393 154909 0
168580 147099 0

output:

749060742
852150556
818848252
265627528
519332711

result:

ok 5 lines

Test #8:

score: 5
Accepted
time: 15ms
memory: 16884kb

input:

5
159739 133365 0
157360 141159 0
121162 131860 0
151178 171138 0
144364 184158 0

output:

979158800
116511003
324350537
821862703
673603087

result:

ok 5 lines

Test #9:

score: 5
Accepted
time: 19ms
memory: 16880kb

input:

5
105692 162860 0
183343 188626 0
145757 111436 0
124879 196578 0
111816 159521 0

output:

769494352
379610022
701309141
774074335
158776213

result:

ok 5 lines

Test #10:

score: 5
Accepted
time: 12ms
memory: 16880kb

input:

5
119156 180997 1
77193 179909
140657 157547 1
22313 57487
184689 115534 1
52853 1884
132895 129818 ...

output:

556113428
873362948
784744720
732015649
730444754

result:

ok 5 lines

Test #11:

score: 5
Accepted
time: 7ms
memory: 16884kb

input:

5
148437 141256 1
90763 48826
174479 141752 1
155182 115773
156969 139879 1
91340 18099
106775 16372...

output:

536241252
564293575
488812768
898123916
813565910

result:

ok 5 lines

Test #12:

score: 5
Accepted
time: 16ms
memory: 16884kb

input:

5
193695 172716 1
178513 140519
166852 192969 1
160460 101934
117783 187193 1
55355 27063
133468 112...

output:

954252782
952869266
162640106
754391018
969607690

result:

ok 5 lines

Test #13:

score: 5
Accepted
time: 127ms
memory: 16920kb

input:

5
163667 141799 2000
5275 32523
26542 40424
23904 100431
82953 79064
2183 137514
62082 115888
121695...

output:

896526635
709871705
428666870
882795541
762866872

result:

ok 5 lines

Test #14:

score: 5
Accepted
time: 132ms
memory: 16920kb

input:

5
177869 198777 2000
69714 74171
38922 121803
59524 25137
110382 150491
176801 184965
128602 2068
57...

output:

830249249
402257091
19434112
179079955
325672221

result:

ok 5 lines

Test #15:

score: 5
Accepted
time: 128ms
memory: 16920kb

input:

5
171285 149660 2000
68126 101973
42013 40695
149886 36828
49002 95248
58185 57392
84867 52441
29261...

output:

189866695
455741374
699174819
242837769
460363284

result:

ok 5 lines

Test #16:

score: 5
Accepted
time: 135ms
memory: 16920kb

input:

5
163623 165233 2000
73426 118980
19749 40742
129921 162958
51536 129327
22577 99041
160740 133603
1...

output:

300594327
110221680
984222937
675516304
650864983

result:

ok 5 lines

Test #17:

score: 5
Accepted
time: 142ms
memory: 16924kb

input:

5
136651 146021 2000
50205 18678
40627 85963
25621 15399
80388 102113
65784 67747
118405 97796
96718...

output:

759539848
54536828
371455196
880857078
581259637

result:

ok 5 lines

Test #18:

score: 5
Accepted
time: 133ms
memory: 16920kb

input:

5
192860 149311 2000
155686 144359
135603 10041
166782 131396
58381 3350
169088 138203
51633 11724
1...

output:

229448528
743031781
321444118
374130313
975211144

result:

ok 5 lines

Test #19:

score: 5
Accepted
time: 130ms
memory: 16924kb

input:

5
157602 103332 2000
148773 59658
29391 18987
68444 39138
9199 70072
77226 87278
125652 10250
28184 ...

output:

24213611
639700069
237941903
206526446
642516799

result:

ok 5 lines

Test #20:

score: 5
Accepted
time: 131ms
memory: 16924kb

input:

5
137075 110768 2000
118931 97190
108017 60169
111943 32747
73134 35103
79314 110693
505 83349
22748...

output:

319689623
498637555
138423814
112741391
6367989

result:

ok 5 lines