QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#67281 | #5099. 朝圣道 | xlwang | 42 | 1979ms | 156744kb | C++14 | 1.6kb | 2022-12-10 11:24:30 | 2022-12-10 11:24:32 |
Judging History
answer
#include <bits/stdc++.h>
#include "pilgrimage.h"
#define ll long long
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
const int Maxn=3e3+20;
ll f[Maxn][Maxn<<1];
inline ll ksm(ll x,ll y,ll mod){
ll sum=1;
while(y){
if(y&1) sum=sum*x%mod;
y=y/2;
x=x*x%mod;
}
return sum;
}
int x,y;
inline void exgcd(int a,int b){
if(b==0){
x=1;
y=0;
return;
}
exgcd(b,a%b);
int t=x;
x=y;
y=t-a/b*y;
}
int mod;
const int Maxm=1e6+10;
int ans[Maxn];
int fac[Maxm],ifac[Maxm];
int p1,p2,p3;
void init(int o, int p){
mod=p;
f[0][3005]=1;
x=y=0;
exgcd(4,p);
p1=p3=(x+p)%p;
x=y=0;
exgcd(2,p);
p2=(x+p)%p;
fr(i,1,3000) fr(j,1,6020) f[i][j]=(f[i-1][j]*p2%p+f[i-1][j-1]*p3%p+f[i-1][j+1]*p1%p)%p;
fr(n,1,3000) fr(i,1,6020) ans[n]+=1ll*abs(i-3005)*f[n][i]%mod,ans[n]%=mod;
fac[0]=ifac[0]=1;
int N=mod-1;
fr(i,1,N) fac[i]=1ll*fac[i-1]*i%mod;
ifac[N]=ksm(fac[N],mod-2,mod);
rf(i,N-1,1) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
// fr(i,2990,3015) printf("f[%lld]=%lld\n",abs(i-3005),f[7][i]);
}
inline int C(long long x,long long y){
// printf("%lld %lld\n",x,y);
if(x<mod && y<mod) return 1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod;
return 1ll*C(x/mod,y/mod)*C(x%mod,y%mod)%mod;
}
int ask(long long n){
// printf("%lld %lld\n",n,p2);
if(n<=3000) return ans[n];
if(n==1){
return p2;
}
n-=2;
long long answer;
answer=ksm(p2,2*n+2,mod);
// printf("%lld %lld\n",n,answer);
answer=answer*((2*n)%mod+3)%mod;
// printf("%lld %lld\n",n,answer);
answer=answer*C(2*n+1,n)%mod;
// printf("%lld %lld\n",n,answer);
return answer;
}
详细
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 768ms
memory: 153288kb
input:
1 910276 554767 6 10 7 4 10 12 9 3 3 5 7 10 5 6 1 6 3 9 6 8 12 11 8 2 12 5 9 3 8 2 12 11 2 3 4 9 2 5 5 11 6 4 8 11 3 9 2 2 8 9 2 8 9 6 2 9 2 10 10 7 5 6 4 4 11 12 8 8 2 2 4 3 3 5 6 6 8 11 6 9 9 3 4 1 2 2 6 9 9 2 3 2 12 6 1 7 2 4 12 11 4 7 6 3 9 4 6 5 3 3 12 6 2 1 1 7 2 6 5 9 11 6 3 4 11 1 2 4 5 4 10...
output:
5419 364275 514407 329394 364275 229662 53120 520095 520095 509260 514407 364275 509260 5419 277384 5419 520095 53120 5419 115262 229662 243797 115262 416076 229662 509260 53120 520095 115262 416076 229662 243797 416076 520095 329394 53120 416076 509260 509260 243797 5419 329394 115262 243797 520095...
result:
ok 910276 numbers
Test #2:
score: 0
Accepted
time: 793ms
memory: 151372kb
input:
1 972231 293475 7 1 9 6 5 1 11 5 5 12 2 2 7 3 4 10 10 3 2 10 7 1 10 9 1 3 5 6 7 2 7 4 1 10 1 9 3 10 10 2 6 11 4 10 12 8 5 2 12 4 9 12 7 2 12 4 3 1 2 9 12 1 4 5 6 12 6 5 9 2 5 12 3 4 6 12 12 2 1 6 4 12 10 5 12 7 9 8 3 8 10 5 3 6 12 7 7 10 7 10 8 7 7 2 2 4 8 6 10 8 11 6 11 10 3 9 5 2 5 1 10 2 11 4 4 3...
output:
117936 146738 29445 289464 209790 146738 240513 209790 209790 158067 220107 220107 117936 201765 284305 145210 145210 201765 220107 145210 117936 146738 145210 29445 146738 201765 209790 289464 117936 220107 117936 284305 146738 145210 146738 29445 201765 145210 145210 220107 289464 240513 284305 14...
result:
ok 972231 numbers
Subtask #2:
score: 8
Accepted
Dependency #1:
100%
Accepted
Test #3:
score: 8
Accepted
time: 778ms
memory: 152032kb
input:
2 957481 386233 816 1256 2812 1370 1469 1439 33 929 1437 2680 1001 1846 1936 1161 1823 1417 2823 1753 2434 577 1671 676 174 2401 1762 123 785 604 1650 117 2344 1365 221 1096 1087 1057 457 2254 647 1827 266 1599 1445 83 2685 1372 1795 2595 1909 2605 1608 2656 1114 581 725 725 2964 1893 2997 2159 2457...
output:
243553 369562 36625 90220 62730 42787 241717 149359 268969 155264 320512 294338 253353 21209 383147 351989 377945 95957 11104 281882 322211 249147 314632 233795 328009 379666 87737 25996 373808 370185 100320 276912 381027 160702 232305 93658 378209 290139 141008 290287 259740 247075 57683 258680 366...
result:
ok 957481 numbers
Test #4:
score: 0
Accepted
time: 821ms
memory: 156744kb
input:
2 912746 991287 2945 439 558 2022 1589 2495 2517 2291 2215 160 319 1671 2800 2008 2885 29 41 580 1156 2553 1876 1137 2129 2338 1046 1818 2691 1454 1229 1965 635 1516 987 1629 140 2320 1715 2644 452 1353 2755 693 956 2518 1154 2441 946 137 496 786 2489 1509 190 2177 1216 1725 480 2572 1774 2465 298 2...
output:
660858 612612 0 511632 911772 0 0 0 92378 55539 511632 0 0 0 479655 660858 939807 894102 95931 260865 699732 0 583110 496485 0 630819 0 90117 116622 804474 466488 816354 174933 450585 988218 623007 0 208692 0 0 330429 0 758043 660858 95931 660858 0 138321 148614 208692 0 692478 277134 127908 831402 ...
result:
ok 912746 numbers
Subtask #3:
score: 12
Accepted
Test #5:
score: 12
Accepted
time: 768ms
memory: 147552kb
input:
3 1 334547 8234
output:
179079
result:
ok 1 number(s): "179079"
Subtask #4:
score: 18
Accepted
Dependency #3:
100%
Accepted
Test #6:
score: 18
Accepted
time: 1131ms
memory: 153464kb
input:
4 1000000 581873 49881 62491 206405 26106 129239 174098 141494 61402 149825 241992 8109 243567 71918 203927 278575 263516 143582 32237 195508 269119 9111 105700 80919 229859 150334 171917 78447 62500 190063 138903 6395 222902 118653 136505 242467 64984 170330 287622 27089 35823 107672 273459 188857 ...
output:
225562 278095 494263 533616 449513 172629 433105 169217 156602 470240 127840 224903 148625 143635 385698 428034 270424 224704 326598 317786 205590 556103 563899 492571 87003 417735 350849 476300 65308 462020 373541 56205 35476 425631 345156 395965 377993 402141 119653 299737 4555 400632 420936 58015...
result:
ok 1000000 numbers
Subtask #5:
score: 0
Wrong Answer
Dependency #4:
100%
Accepted
Test #7:
score: 0
Wrong Answer
time: 1979ms
memory: 155484kb
input:
5 1000000 840643 596357868225427095 792903040511847841 549819683428503148 982786835970534376 855138540813992974 101968907510306081 885121351101383723 127972727417081251 728407510651610501 998897446686193527 889398142082696651 17276066104970301 87773104284997915 716559595019194816 538865162230963483 ...
output:
662961 149057 145249 346555 251976 350957 13853 217351 686099 785672 618602 80127 434838 369030 457406 688329 243219 264897 462944 728980 522898 367925 754949 410150 679730 463222 735397 442162 321586 291582 311655 485386 586156 469241 670015 171419 707785 833727 417067 700430 541589 156227 826454 5...
result:
wrong answer 1st numbers differ - expected: '0', found: '662961'
Subtask #6:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 1868ms
memory: 152892kb
input:
6 958477 522361 280121915553826833 734266539148641647 72849162479700582 274266741463686096 60278972064195458 828423669427600612 571432949203039978 518511460268700898 486268614705621285 19216283231217074 611458416727512530 175147354285288662 799769622289998997 400123443628688299 145546980862133838 40...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 12th numbers differ - expected: '193620', found: '0'
Subtask #7:
score: 0
Wrong Answer
Dependency #3:
100%
Accepted
Test #13:
score: 8
Accepted
time: 772ms
memory: 150600kb
input:
7 1 731039 314313205082038759
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 778ms
memory: 149520kb
input:
7 1 587945 675184352277027016
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 755ms
memory: 150548kb
input:
7 1 732151 522404464427087971
output:
0
result:
ok 1 number(s): "0"
Test #16:
score: 0
Accepted
time: 778ms
memory: 152536kb
input:
7 1 952025 865782493150981281
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 732ms
memory: 146172kb
input:
7 1 151005 80048698775676684
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 782ms
memory: 151228kb
input:
7 1 819153 214538328031265195
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 758ms
memory: 145508kb
input:
7 1 84501 605460166753167761
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 795ms
memory: 149368kb
input:
7 1 579977 434091105518396762
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 744ms
memory: 146108kb
input:
7 1 161075 649828935660369724
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 740ms
memory: 149928kb
input:
7 1 629595 216539117331686464
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 737ms
memory: 147368kb
input:
7 1 317005 831315176686118434
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 727ms
memory: 146528kb
input:
7 1 204399 934354294367869212
output:
0
result:
ok 1 number(s): "0"
Test #25:
score: 0
Accepted
time: 737ms
memory: 145612kb
input:
7 1 98233 515248809013032256
output:
0
result:
ok 1 number(s): "0"
Test #26:
score: -8
Wrong Answer
time: 767ms
memory: 150612kb
input:
7 1 738315 930635383520033839
output:
0
result:
wrong answer 1st numbers differ - expected: '51840', found: '0'
Subtask #8:
score: 0
Wrong Answer
Test #33:
score: 0
Wrong Answer
time: 756ms
memory: 145136kb
input:
8 9963 251 831797004675585320 494759973681332858 701341496127272302 252910460485222469 250965009655458584 366193481309061299 633134388675839346 791999098066205672 196620805863610860 363773642045280947 466508590762410710 407790578717064135 181590911404670570 570642047249889864 70138464625729452 23634...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 204 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 24 0 0 0 0 0 0 0 0 0 0 0 0 63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 98th numbers differ - expected: '0', found: '24'
Subtask #9:
score: 0
Skipped
Dependency #2:
100%
Accepted
Dependency #5:
0%