ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#197742 | #2710. Grid Walk | snow_trace | 100 | 1307ms | 9208kb | C++11 | 1.4kb | 2023-11-14 09:33:33 | 2023-11-14 12:02:59 |
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(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
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: 69ms
memory: 9204kb
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: 57ms
memory: 9204kb
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: 64ms
memory: 9208kb
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: 68ms
memory: 9208kb
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: 64ms
memory: 9204kb
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: 67ms
memory: 9204kb
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: 7ms
memory: 9156kb
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: 10ms
memory: 9152kb
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: 3ms
memory: 9152kb
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: 10ms
memory: 9152kb
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: 5ms
memory: 9156kb
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: 10ms
memory: 9156kb
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: 101ms
memory: 9204kb
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: 119ms
memory: 9208kb
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: 111ms
memory: 9208kb
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: 103ms
memory: 9208kb
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: 111ms
memory: 9204kb
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: 116ms
memory: 9204kb
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: 105ms
memory: 9204kb
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: 9208kb
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