QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#420375 | #2816. 过河卒二 | liqingyang# | AC ✓ | 165ms | 4224kb | C++17 | 1.4kb | 2024-05-24 16:53:52 | 2024-05-24 16:53:53 |
Judging History
answer
#include<iostream>
#include<algorithm>
using namespace std;
const int mod=59393;
inline int qpow(int a,int b)
{
int ret=1;
while(b)
{
if(b&1)
{
ret=(long long)
ret*a%mod;
}
a=(long long)
a*a%mod,b>>=1;
}
return ret;
}
int n,m,K,s[mod+5],inv[mod+5],f[25][25];
pair<int,int> a[25];
inline int C(int n,int m)
{
return n<m?0:(n<mod?(long long)s[n]*inv[m]*inv[n-m]%mod
:(long long)C(n/mod,m/mod)*C(n%mod,m%mod)%mod);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
for(int i=s[0]=inv[0]=1;i<=mod;i++)
{
s[i]=(long long)s[i-1]*i%mod;
inv[i]=qpow(s[i],mod-2);
}
cin>>n>>m>>K;
for(int i=1;i<=K;i++)
{
cin>>a[i].first>>a[i].second;
}
sort(a+1,a+K+1);
a[0]={1,1},a[++K]={n+1,m+1};
for(int i=0;i<=K;i++)
{
for(int j=i+1;j<=K;j++)
{
if(a[i].second>a[j].second)
{
continue;
}
int n=a[j].first-a[i].first;
int m=a[j].second-a[i].second;
long long sum=0;
for(int k=0;k<=min(n,m);k++)
{
sum+=(long long)
C(n-k+m-k+k,k)*C(n-k+m-k,n-k);
}
f[i][j]=sum%mod;
}
}
long long Ans=0;
for(int i=0;i<(1<<K-1);i++)
{
int last=0,ans=1;
for(int j=1;j<K;j++)
{
if(i&(1<<j-1))
{
ans=(long long)
ans*f[last][j]%mod;
last=j;
}
}
ans=(long long)ans*f[last][K]%mod;
Ans+=((__builtin_popcount(i)&1)?-1:1)*ans;
}
cout<<(Ans%mod+mod)%mod<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 101ms
memory: 4084kb
input:
1737 2613 20 1695 2081 1449 1419 868 1636 879 2454 1400 1778 1364 2166 1343 1563 1229 2012 1308 1674 1712 2004 1392 1716 1118 1690 1693 1986 1641 2221 1454 1937 1554 1944 997 2083 1242 1503 990 1834 986 1438
output:
47388
result:
ok single line: '47388'
Test #2:
score: 0
Accepted
time: 110ms
memory: 4204kb
input:
37183 50656 20 19376 46381 26095 33186 22143 36608 22985 46098 37134 47561 29505 37971 33937 39976 30735 35845 18593 27027 24886 31630 31919 48391 31646 31818 32959 30489 28111 33154 19190 30567 21345 33181 27168 29608 25105 37750 27601 30901 31909 28946
output:
24648
result:
ok single line: '24648'
Test #3:
score: 0
Accepted
time: 117ms
memory: 4156kb
input:
44420 91969 20 26580 82240 39885 61285 41566 67220 36272 54211 43473 80094 35306 85527 24022 61262 29798 81055 24511 76963 39082 63249 31639 48137 36127 50250 24651 59458 31061 75543 33310 62799 34926 60731 38397 91900 30238 55599 37632 78084 30203 68381
output:
15204
result:
ok single line: '15204'
Test #4:
score: 0
Accepted
time: 3ms
memory: 4156kb
input:
580805600 54167 0
output:
23746
result:
ok single line: '23746'
Test #5:
score: 0
Accepted
time: 157ms
memory: 4148kb
input:
826964258 69871 20 549552592 47200 515793697 54386 614188758 68095 562588168 39532 442360278 63494 548867812 64969 431340934 47675 754746960 67013 465366759 64806 468411232 57998 642243607 57593 460525676 54551 537102308 66550 497820482 69282 512530411 44066 804850336 62103 647345365 43172 415023030...
output:
13365
result:
ok single line: '13365'
Test #6:
score: 0
Accepted
time: 165ms
memory: 4196kb
input:
730956188 82754 20 446994358 80794 370767296 72114 588336811 61575 461868174 59127 687944030 47654 415192065 64512 676919795 68879 501594582 79353 500183604 77871 369691859 45105 700735165 64997 710627893 76323 422390555 64482 455803600 71287 531930698 60905 512993094 76984 448561503 47257 433564005...
output:
11564
result:
ok single line: '11564'
Test #7:
score: 0
Accepted
time: 3ms
memory: 4084kb
input:
33024 81694 0
output:
34973
result:
ok single line: '34973'
Test #8:
score: 0
Accepted
time: 98ms
memory: 4140kb
input:
32506 85138 20 32235 51865 18196 73834 21810 62856 25280 78735 29905 81850 20980 62326 32392 84165 26666 47713 16292 44472 21821 52166 17956 63418 22186 71351 21874 55903 30929 44205 28833 69843 22645 68970 18044 60713 22875 84981 16932 48656 19083 73733
output:
11558
result:
ok single line: '11558'
Test #9:
score: 0
Accepted
time: 87ms
memory: 4208kb
input:
28794 91901 20 15780 47550 16228 63624 22519 67507 27276 68129 20208 55660 14445 83194 19890 87105 16995 51790 23562 81574 24909 81655 19645 91242 21712 69349 18700 87961 16386 80377 22261 73605 17150 71793 25231 88055 19094 48227 21872 51066 21575 62419
output:
6126
result:
ok single line: '6126'
Test #10:
score: 0
Accepted
time: 6ms
memory: 4208kb
input:
874334884 76845 0
output:
49888
result:
ok single line: '49888'
Test #11:
score: 0
Accepted
time: 5ms
memory: 4156kb
input:
600400150 76601 0
output:
36078
result:
ok single line: '36078'
Test #12:
score: 0
Accepted
time: 82ms
memory: 4140kb
input:
1809 1900 20 1409 1731 1270 1624 1785 1625 1535 1623 1237 1454 1192 1885 1061 1017 1234 1426 1568 1524 1371 1720 924 1436 1150 1642 1577 1203 1381 980 1803 1492 1730 1723 1017 1618 1081 1825 1109 1854 1531 1723
output:
9086
result:
ok single line: '9086'
Test #13:
score: 0
Accepted
time: 28ms
memory: 4152kb
input:
657937727 76253 16 353360364 70916 357516312 53327 589177133 67883 597034765 50623 384898823 58437 379751019 57493 483681045 56498 491539894 53349 610557723 52343 360648343 54993 564102363 39521 419962522 48853 335872303 57105 349100555 67118 468779229 40570 356587597 52710
output:
6809
result:
ok single line: '6809'
Test #14:
score: 0
Accepted
time: 23ms
memory: 4088kb
input:
557724458 54762 14 301629598 47965 436413263 32002 511367835 52269 501044435 50636 299578901 28534 442296296 27498 448704742 41005 363834222 40929 525245696 46031 416274768 51532 415318717 51977 471948030 35370 360058356 49586 440592956 42732
output:
48600
result:
ok single line: '48600'
Test #15:
score: 0
Accepted
time: 122ms
memory: 4152kb
input:
859488244 92109 20 544104338 69060 574192703 77696 486974372 51244 838791582 58699 789748054 55477 604464016 48730 563348127 71652 604126025 60353 670354360 83868 545369547 61775 500525928 49175 432206293 59438 610533110 86479 725144760 71616 693875041 80105 569929288 63697 598742162 71768 677965652...
output:
38594
result:
ok single line: '38594'
Test #16:
score: 0
Accepted
time: 108ms
memory: 4204kb
input:
571070677 52797 20 400551828 30665 417408550 42374 556056493 29785 545655329 28420 484510833 34597 394794339 26740 393526624 40979 436842959 38386 334890610 26606 454767316 37800 537509244 26471 414205915 49455 307519590 30092 544680508 49131 570832559 47979 314571056 49645 361844188 27979 425374340...
output:
49481
result:
ok single line: '49481'
Test #17:
score: 0
Accepted
time: 106ms
memory: 4196kb
input:
567821896 50758 20 321797528 49814 374121935 45703 490334188 45215 314721780 34261 451832051 32195 526382301 35211 408792934 30303 480618183 25425 322239004 41763 293013851 27555 546634104 47215 328456647 44971 319292507 32076 321272107 33387 547421667 45073 545966920 39232 412035955 37941 520427824...
output:
16479
result:
ok single line: '16479'
Test #18:
score: 0
Accepted
time: 109ms
memory: 4136kb
input:
829753401 69714 20 828274315 53293 441063740 68010 698899637 58231 416172227 50421 816338110 51423 567894784 60791 523156675 59065 425721069 48231 472508977 41852 553049724 65905 427790091 61017 433173036 57318 451714261 55511 447745667 41203 677368642 50502 461038435 43078 421673283 64698 535187871...
output:
4298
result:
ok single line: '4298'
Test #19:
score: 0
Accepted
time: 4ms
memory: 4224kb
input:
3 3 3 2 2 2 3 3 2
output:
4
result:
ok single line: '4'
Test #20:
score: 0
Accepted
time: 4ms
memory: 4196kb
input:
873835081 1 1 233 1
output:
464
result:
ok single line: '464'
Test #21:
score: 0
Accepted
time: 96ms
memory: 4140kb
input:
701639588 65456 20 20 1 19 2 18 3 17 4 16 5 15 6 14 7 13 8 12 9 11 10 10 11 9 12 8 13 7 14 6 15 5 16 4 17 3 18 2 19 1 20
output:
3978
result:
ok single line: '3978'
Test #22:
score: 0
Accepted
time: 8ms
memory: 4204kb
input:
849211396 72758 3 1 2 2 1 2 2
output:
0
result:
ok single line: '0'
Test #23:
score: 0
Accepted
time: 4ms
memory: 4144kb
input:
28361 5 0
output:
26840
result:
ok single line: '26840'
Test #24:
score: 0
Accepted
time: 62ms
memory: 4144kb
input:
739003251 85837 19 9 1 8 2 7 3 6 4 5 5 4 6 3 7 2 8 1 9 10 1 9 2 8 3 7 4 6 5 5 6 4 7 3 8 2 9 1 10
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 127ms
memory: 4156kb
input:
507994226 96662 20 284011294 62806 284011294 62807 284011294 62808 284011295 62806 284011295 62808 284011296 62806 284011296 62807 284011296 62808 488809005 61432 407416480 52884 453544878 55418 479921899 93244 391347376 69358 286757302 80030 398726073 58037 462496452 83242 462496451 83242 462496453...
output:
44165
result:
ok single line: '44165'
Test #26:
score: 0
Accepted
time: 116ms
memory: 4192kb
input:
811734066 68881 20 555484862 68881 584626108 59286 811734066 68881 485588255 46189 493509169 38906 521875803 60358 530848207 41681 755512545 68881 811734066 51709 451042683 47790 681190796 48083 593014418 55702 763130281 43438 684714882 49051 791604023 54672 738158852 63435 811734066 55936 757540221...
output:
17066
result:
ok single line: '17066'
Test #27:
score: 0
Accepted
time: 105ms
memory: 4072kb
input:
719906313 53423 20 606574998 35079 606574999 35079 606574997 35079 598361139 53384 570753681 49836 573910670 38732 427670480 45517 410946812 47351 649756131 46500 649756133 46500 649756132 46501 649756132 46499 432262915 27119 406363477 48245 630227996 30441 526431392 52368 409342397 39014 560125856...
output:
16397
result:
ok single line: '16397'
Test #28:
score: 0
Accepted
time: 128ms
memory: 4140kb
input:
704271417 92848 20 534221616 57197 534030676 49952 529264547 60547 366697878 60100 355234832 55539 608719578 91610 700793935 56558 584423467 81540 432441768 62743 540852563 65916 534221617 57197 534030677 49952 529264548 60547 366697879 60100 355234833 55539 608719579 91610 700793936 56558 584423468...
output:
4464
result:
ok single line: '4464'
Test #29:
score: 0
Accepted
time: 63ms
memory: 4136kb
input:
571503360 92367 19 571503351 92367 571503352 92367 571503353 92367 571503354 92367 571503355 92367 571503356 92367 571503357 92367 571503358 92367 571503359 92367 571503360 92367 571503360 92366 571503360 92365 571503360 92364 571503360 92363 571503360 92362 571503360 92361 571503360 92360 571503360...
output:
15311
result:
ok single line: '15311'
Test #30:
score: 0
Accepted
time: 82ms
memory: 4132kb
input:
48913 9 20 47423 9 40190 4 42976 7 31269 6 25293 8 40386 7 44085 5 34147 7 36001 9 33675 5 37520 7 28913 9 41113 7 29853 9 34528 6 30834 8 46176 7 34012 5 37849 8 34960 6
output:
57975
result:
ok single line: '57975'
Test #31:
score: 0
Accepted
time: 86ms
memory: 4140kb
input:
45953 9 20 44300 8 31177 7 30055 6 26867 8 31774 9 43485 6 41933 9 43902 4 30082 7 37977 7 31152 6 31876 9 27661 6 38824 8 38769 9 33768 7 39013 7 35137 6 28438 9 40478 8
output:
58444
result:
ok single line: '58444'
Test #32:
score: 0
Accepted
time: 4ms
memory: 4080kb
input:
884877140 5 0
output:
50291
result:
ok single line: '50291'
Test #33:
score: 0
Accepted
time: 81ms
memory: 4140kb
input:
773735608 10 20 434780922 8 459862387 10 598361139 6 570753681 10 737688182 5 427670480 8 410946812 6 649756131 8 520725240 10 432262915 8 526431392 8 549026451 10 409342397 6 421060472 8 704271417 7 640920306 5 534221616 9 534030676 10 529264547 5 395217379 8
output:
17180
result:
ok single line: '17180'
Test #34:
score: 0
Accepted
time: 89ms
memory: 4140kb
input:
608719578 5 20 540038792 5 584423467 4 432441768 5 540852563 2 501183788 5 547016517 3 388941970 4 358579302 4 351620759 2 336499263 5 519341861 4 537713518 5 477509895 3 404357527 4 383929357 5 344543931 4 362230509 3 454582199 3 571503360 5 325607169 3
output:
42628
result:
ok single line: '42628'
Test #35:
score: 0
Accepted
time: 0ms
memory: 4140kb
input:
47785 96479 0
output:
2711
result:
ok single line: '2711'