ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#197748 | #2710. Grid Walk | Womind | 100 | 1579ms | 4328kb | C++ | 2.2kb | 2023-11-14 10:20:55 | 2023-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