ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#197749 | #2710. Grid Walk | tkswls | 100 | 1644ms | 16924kb | C++ | 1.3kb | 2023-11-14 10:26:23 | 2023-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