UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197741#2710. Grid Walksnow_trace1001453ms9152kbC++111.3kb2023-11-14 09:33:052023-11-14 12:02:54

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1000000007;
int qp(int p,int q){
	int ans = 1,pro = p;
	while(q){
		if(q&1)ans = ans*pro%mod;pro = pro*pro%mod;q>>=1;
	}return ans;
}
int niyuan(int x){
	return qp(x,mod-2);
}
int n,m,k;
int dp[5005];
int jie[500005],inv[500005];
pair<int,int>a[5005];int x[5005],y[5005];
int C(int n,int m){
	if(n<m)return 0;
	return jie[n]*inv[m]%mod*inv[n-m]%mod;
}
bool cmp(pair<int,int>a,pair<int,int>b){
	if(a.second == b.second)return a.first<b.first;
	return a.second<b.second;
}void solve(){
	cin >> n >> m >> k;;
	for(int i = 1;i<=k;i++)cin >> a[i].first >> a[i].second;
	a[k+1].first = n,a[++k].second = m;
	for(int i =0;i<=k;i++)dp[i] = 0;
	sort(a+1,a+1+k,cmp);dp[0] = 1;
	for(int i = 1;i<=k;i++)x[i] = a[i].first,y[i] = a[i].second;
	for(int i= 1;i<=k;i++){
		dp[i] = C(x[i]+y[i]-2,x[i]-1);
		for(int j = 1;j<i;j++){
			if(x[i]>=x[j] and y[i]>=y[j]){
				dp[i]-=C(x[i]-x[j]+y[i]-y[j],x[i]-x[j])*dp[j]%mod;
			}
		}dp[i] = (dp[i]%mod+mod)%mod;
	}cout << dp[k] << endl;
}
signed main(){
	
	jie[0] = inv[0] = 1;
	for(int i = 1;i<=500000;i++)jie[i] = jie[i-1]*i%mod;inv[500000] = niyuan(jie[500000]);
	for(int i = 499999;i>=1;i--)inv[i] = inv[i+1]*(i+1)%mod;
	int t;cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

详细

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

Test #1:

score: 5
Accepted
time: 66ms
memory: 9152kb

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: 68ms
memory: 9152kb

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

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

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

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: 62ms
memory: 9148kb

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: 5ms
memory: 9100kb

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

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

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: 9ms
memory: 9100kb

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

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: 9ms
memory: 9100kb

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: 109ms
memory: 9148kb

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: 118ms
memory: 9152kb

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: 117ms
memory: 9148kb

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: 109ms
memory: 9148kb

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: 109ms
memory: 9152kb

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: 121ms
memory: 9152kb

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: 178ms
memory: 9152kb

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: 151ms
memory: 9148kb

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