UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197748#2710. Grid WalkWomind1001579ms4328kbC++2.2kb2023-11-14 10:20:552023-11-14 12:03:19

answer

/*
    Name:
    Copyright:
    Author: 不要和 std 命名空间冲突!
    Date: 11/14/2023 9:45:41 AM
    Description:等会造成误差!文件读写即可!
*/
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b)  for (int i = (a); i <= (b); i++)
#define repe(i,a,b) for (int i = (a); i >= (b); i--)
bool Mbe;
inline int read() {
	int ans = 0, f = 1; char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -f;
	for(; ch >= '0' && ch <= '9'; ch = getchar()) ans = (ans << 3) + (ans << 1) + ch - '0';
	return ans * f;
}
const int mod = 1e9 + 7;
int ksm(int truth, int power) {
	int ans = 1;
	while(power) {
		if(power & 1) ans = 1ll * ans * truth % mod;
		power >>= 1;
		truth = 1ll * truth * truth % mod;
	}
	return ans;
}

const int Z = 2e6 + 5;
int fac[Z], ifac[Z];
void init_fac(int x) {
	for(int i = fac[0] = 1; i <= x; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[x] = ksm(fac[x], mod - 2);
	for(int i = x - 1; i >= 0; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
}

int C(int mu, int zi) {
	return fac[mu] * 1ll * ifac[zi] % mod * ifac[mu - zi] % mod;
}

const int N = 2e3 + 23;
int  n, k, m, f[N];
bool vis[N];
struct node {
	int x, y;
//	bool operator < ( node B) {
//		if(x == B.x) return y < B.y;
//		return x < B.x;
//	} 
}a[N];
bool cmp(node A, node B) {
	if(A.x == B.x) return A.y < B.y;
	return A.x < B.x;
} 

void mian() {
	n = read(), m = read(), k = read();
	rep(i,1,k) a[i].x = read(), a[i].y = read();
	sort(a + 1, a + k + 1, cmp);
//	rep(i,1,k) cout << a[i].x << " " << a[i].y << endl;
	init_fac(n + m);
	a[0].x = 0, a[0].y = 0; a[k + 1].x = n, a[k + 1].y = m;
	rep(i,1,k + 1) {
		f[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);
		rep(j,1,i - 1) {
			if(a[j].x <= a[i].x && a[j].y <= a[i].y) { // 一边等于 
				f[i] = (f[i] - 1ll * f[j] * C(a[i].y + a[i].x - a[j].y - a[j].x, a[i].x - a[j].x) % mod + mod) % mod; 
			}
		}
	} 
	cout << f[k + 1] << "\n";
}

bool Med;
int main(){
//    freopen("B.txt", "r", stdin);
//    freopen(".out", "w", stdout);
	fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0);
	int T = read();
	while(T--) mian();
	cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
	return 0;
}


详细

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

Test #1:

score: 5
Accepted
time: 69ms
memory: 1336kb

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: 67ms
memory: 1328kb

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: 69ms
memory: 1336kb

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: 65ms
memory: 1328kb

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: 71ms
memory: 1340kb

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: 66ms
memory: 1328kb

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: 19ms
memory: 3928kb

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: 13ms
memory: 3840kb

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: 20ms
memory: 4184kb

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: 16ms
memory: 4024kb

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: 17ms
memory: 4328kb

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: 21ms
memory: 4140kb

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: 135ms
memory: 4260kb

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: 130ms
memory: 4248kb

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: 137ms
memory: 3820kb

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: 3984kb

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: 131ms
memory: 4208kb

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: 130ms
memory: 4064kb

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: 135ms
memory: 3920kb

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: 133ms
memory: 3880kb

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