UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197731#2710. Grid Walkwosile1001279ms4300kbC++111.4kb2023-11-14 08:42:312023-11-14 12:02:04

answer

#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef long long ll;
int ft[400005],inv[400005];
int f[2005];
int T;
#define mod 1000000007
int qp(int x,int y){
//	printf("%d %d\n",x,y);
	int ans=1;
	while(y){
//		printf("%d\n",y);
		if(y&1)ans=1LL*ans*x%mod;
		x=1LL*x*x%mod;
		y>>=1;
	}
	return ans;
}
int k;
pair<int,int>a[2005];
int read(){
	int x=0,c=getchar()-48;
	while(c<0 || c>9)c=getchar()-48;
	while(c>=0 && c<=9){
		x=x*10+c;
		c=getchar()-48;
	}
	return x;
}
int C(int x,int y){
//	printf("C(%d,%d)\n",x,y);
	if(x<y || y<0)return 0;
	return 1LL*ft[x]*inv[y]%mod*inv[x-y]%mod;
}
int main(){
	T=read();
	ft[0]=1;
	for(int i=1;i<=400000;i++)ft[i]=1LL*ft[i-1]*i%mod;
	inv[400000]=qp(ft[400000],mod-2);
	for(int i=400000;i>=1;i--)inv[i-1]=1LL*inv[i]*i%mod;
	while(T--){
		n=read();
		m=read();
		k=read();
		for(int i=1;i<=k;i++){
			a[i].first=read();
			a[i].second=read();
		}
		a[++k]=make_pair(n,m);
		sort(a+1,a+k+1);
//		for(int i=1;i<=k;i++)printf("(%d,%d)\n",a[i].first,a[i].second);
		for(int i=1;i<=k;i++){
			f[i]=C(a[i].first+a[i].second-2,a[i].first-1);
			for(int j=1;j<i;j++)if(a[j].second<=a[i].second)f[i]=(f[i]-1LL*f[j]*C(a[i].first-a[j].first+a[i].second-a[j].second,a[i].first-a[j].first))%mod;
			f[i]=(f[i]+mod)%mod;
//			printf("f[%d]=%d\n",i,f[i]);
		}
		printf("%d\n",f[k]);
	}
	return 0;
}

详细

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

Test #1:

score: 5
Accepted
time: 67ms
memory: 4300kb

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: 70ms
memory: 4296kb

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

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

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

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: 64ms
memory: 4296kb

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: 6ms
memory: 4296kb

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: 3ms
memory: 4292kb

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: 6ms
memory: 4296kb

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: 6ms
memory: 4292kb

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

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: 6ms
memory: 4296kb

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: 106ms
memory: 4296kb

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: 107ms
memory: 4300kb

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: 102ms
memory: 4300kb

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: 104ms
memory: 4300kb

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: 103ms
memory: 4296kb

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: 111ms
memory: 4296kb

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: 103ms
memory: 4300kb

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: 107ms
memory: 4300kb

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