QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#75581 | #4910. Numbers | 4182_543_731 | 100 ✓ | 2595ms | 149472kb | C++ | 3.2kb | 2023-02-05 20:48:19 | 2023-02-05 20:48:22 |
Judging History
answer
#include<cstdio>
#include<cmath>
using namespace std;
#define N 1059000
#define M 23
int n,mod,su=1,l[M],w[M],p[M],sp,as=1,sv;
int pw(int a,int b){int as=1;while(b){if(b&1)as=1ll*as*a%mod;a=1ll*a*a%mod;b>>=1;}return as;}
struct comp{double a,b;};
comp operator +(comp a,comp b){return (comp){a.a+b.a,a.b+b.b};}
comp operator -(comp a,comp b){return (comp){a.a-b.a,a.b-b.b};}
comp operator *(comp a,comp b){return (comp){a.a*b.a-a.b*b.b,a.a*b.b+a.b*b.a};}
comp gr[2][N*2],c1[N],c2[N],c3[N],c4[N],fft[N];
int rev[N*2];
void init(int d=20)
{
double pi=acos(-1);
for(int l=2;l<=1<<d;l<<=1)for(int i=0;i<l;i++)rev[i+l]=(rev[(i>>1)+l]>>1)|((i&1)*(l>>1));
for(int t=0;t<2;t++)
for(int l=2;l<=1<<d;l<<=1)for(int i=0;i<l>>1;i++)
gr[t][l+i]=(comp){cos(2*pi/l*i),sin(2*pi/l*i*(t?1:-1))};
}
void dft(int s,comp *a,int t)
{
for(int i=0;i<s;i++)fft[rev[i+s]]=a[i];
for(int l=2;l<=s;l<<=1)
for(int i=0;i<s;i+=l)
for(int j=0;j<l>>1;j++)
{
comp v1=fft[i+j],v2=fft[i+j+(l>>1)]*gr[t][l+j];
fft[i+j]=v1+v2;fft[i+j+(l>>1)]=v1-v2;
}
double tp=t?1:1.0/s;
for(int i=0;i<s;i++)a[i]=(comp){fft[i].a*tp,fft[i].b*tp};
}
void mtt(int l,int *a,int *b,int *c)
{
for(int i=0;i<l;i++)
{
c1[i]=(comp){a[i]>>15,0};c2[i]=(comp){a[i]&32767,0};
c3[i]=(comp){b[i]>>15,0};c4[i]=(comp){b[i]&32767,0};
}
dft(l,c1,1);dft(l,c2,1);dft(l,c3,1);dft(l,c4,1);
for(int i=0;i<l;i++)
{
comp v1=c1[i]*c3[i],v2=c1[i]*c4[i]+c2[i]*c3[i],v3=c2[i]*c4[i];
c1[i]=v1,c2[i]=v2,c3[i]=v3;
}
dft(l,c1,0);dft(l,c2,0);dft(l,c3,0);
for(int i=0;i<l;i++)
{
long long f1=c1[i].a+0.4,f2=c2[i].a+0.4,f3=c3[i].a+0.4;
c[i]=(((f1%mod)<<30)+((f2%mod)<<15)+f3)%mod;
}
}
int a[N],b[N],c[N];
int v1[N],v2[N],f[N],g[N],rw[N];
void bluestein(int l,int *f,int *g,int w)
{
if(l<=64)
{
for(int i=0;i<l;i++)g[i]=0;
for(int i=0,a=1;i<l;i++,a=1ll*a*w%mod)
for(int j=0,b=1;j<l;j++,b=1ll*b*a%mod)
g[j]=(g[j]+1ll*f[i]*b)%mod;
return;
}
for(int i=0,a=1,b=1;i<=l*2;i++,a=1ll*a*b%mod,b=1ll*b*w%mod)rw[i]=a;
int le=1;while(le<l*2)le<<=1;
for(int i=0;i<le;i++)a[i]=b[i]=0;
for(int i=0;i<l*2;i++)a[i]=rw[i];
for(int i=1;i<=l;i++)b[i]=1ll*pw(rw[l-i],mod-2)*f[l-i]%mod;
mtt(le,a,b,c);
for(int i=0;i<l;i++)g[i]=1ll*c[i+l]*pw(rw[i],mod-2)%mod;
}
void trs(int *v)
{
for(int i=1,le=1;i<=n;le*=l[i],i++)
for(int j=0;j<su;j+=le*l[i])
for(int k=0;k<le;k++)
{
for(int p=0;p<l[i];p++)f[p]=v[j+k+p*le];
bluestein(l[i],f,g,w[i]);
for(int p=0;p<l[i];p++)v[j+k+p*le]=g[p];
}
}
void dfs(int d,int x,int v)
{
if(d==0){v1[x]=v;return;}
x*=l[d];
for(int i=0,q=1;i<l[d];i++,q=1ll*q*w[d]%mod)dfs(d-1,x,(v+mod-1ll*q*p[d]%mod)%mod),x++;
}
void dfs2(int d,int x,int y)
{
if(d==0){v2[x]=(2ll*(sv+mod)-v1[x]-v1[y])%mod;return;}
x*=l[d],y*=l[d];
for(int i=0;i<l[d];i++)dfs2(d-1,x+i,y+(l[d]-i)%l[d]);
}
int main()
{
int mx=0,li=1;
scanf("%d%d%*d",&n,&mod);
for(int i=1;i<=n;i++)scanf("%d%d%d",&l[i],&p[i],&w[i]),su*=l[i],sp+=p[i],mx=mx<l[i]?l[i]:mx;
for(int i=1;i<=n;i++)p[i]=1ll*p[i]*pw(sp,mod-2)%mod;
while((1<<li)<mx*2)li++;
init(li);
dfs(n,0,1);
for(int i=0;i<su;i++)v1[i]=pw(v1[i],mod-2),sv=(sv+v1[i])%mod;
trs(v1);
dfs2(n,0,0);
for(int i=0;i<su;i++)as=(as+1ll*su*pw(v2[i],mod-2))%mod;
printf("%d\n",as);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 2
Accepted
Test #1:
score: 2
Accepted
time: 305ms
memory: 39844kb
input:
1 1040016149 1 114514 86782 975423317
output:
114514
result:
ok 1 number(s): "114514"
Subtask #2:
score: 8
Accepted
Test #2:
score: 8
Accepted
time: 2ms
memory: 4424kb
input:
1 917829557 2 7 409960 84299716
output:
7
result:
ok 1 number(s): "7"
Test #3:
score: 0
Accepted
time: 1ms
memory: 2360kb
input:
2 1021037011 2 3 673845 456586624 2 557323 1021037010
output:
325765596
result:
ok 1 number(s): "325765596"
Test #4:
score: 0
Accepted
time: 1ms
memory: 2280kb
input:
2 974672641 2 2 919159 974672640 4 945246 788001635
output:
206340059
result:
ok 1 number(s): "206340059"
Test #5:
score: 0
Accepted
time: 1ms
memory: 2372kb
input:
3 942949663 2 2 900268 942949662 2 314911 942949662 2 488210 942949662
output:
697012073
result:
ok 1 number(s): "697012073"
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #6:
score: 10
Accepted
time: 1ms
memory: 2556kb
input:
2 1040469361 3 3 607396 156553896 20 622587 835710357
output:
212836966
result:
ok 1 number(s): "212836966"
Test #7:
score: 0
Accepted
time: 1ms
memory: 2288kb
input:
6 932284961 3 2 976786 932284960 2 296977 932284960 2 640048 932284960 2 883210 932284960 2 178849 932284960 2 292747 932284960
output:
767388139
result:
ok 1 number(s): "767388139"
Test #8:
score: 0
Accepted
time: 0ms
memory: 2376kb
input:
3 972511489 3 4 270846 275326774 6 901035 3644392 3 450749 3644391
output:
386017324
result:
ok 1 number(s): "386017324"
Test #9:
score: 0
Accepted
time: 1ms
memory: 2436kb
input:
4 952654361 3 4 353315 567578568 2 265582 952654360 2 429959 952654360 5 62389 840524015
output:
942289666
result:
ok 1 number(s): "942289666"
Test #10:
score: 0
Accepted
time: 1ms
memory: 2452kb
input:
3 969859729 3 3 342202 745159492 9 270897 686337727 3 216159 745159492
output:
184152966
result:
ok 1 number(s): "184152966"
Test #11:
score: 0
Accepted
time: 1ms
memory: 2340kb
input:
3 953647801 3 7 943891 755724372 4 151642 109446108 3 775757 89434891
output:
811899700
result:
ok 1 number(s): "811899700"
Test #12:
score: 0
Accepted
time: 0ms
memory: 2380kb
input:
3 1029304937 3 4 54303 379091496 2 193487 1029304936 11 607170 762447147
output:
626421900
result:
ok 1 number(s): "626421900"
Test #13:
score: 0
Accepted
time: 0ms
memory: 2348kb
input:
3 904885561 3 3 554090 196965144 2 945499 904885560 15 747460 217098071
output:
676301027
result:
ok 1 number(s): "676301027"
Test #14:
score: 0
Accepted
time: 1ms
memory: 2296kb
input:
6 986788531 3 2 522554 986788530 2 316305 986788530 2 94022 986788530 2 249256 986788530 2 625960 986788530 3 405298 837112629
output:
441366932
result:
ok 1 number(s): "441366932"
Test #15:
score: 0
Accepted
time: 1ms
memory: 2372kb
input:
2 1023351421 3 20 337665 403345072 5 40276 480359844
output:
1002751099
result:
ok 1 number(s): "1002751099"
Subtask #4:
score: 8
Accepted
Test #16:
score: 8
Accepted
time: 4ms
memory: 2604kb
input:
2 998244353 4 4 61786 911660635 238 287234 493901365
output:
223055892
result:
ok 1 number(s): "223055892"
Test #17:
score: 0
Accepted
time: 3ms
memory: 2444kb
input:
2 998244353 4 7 25813 683624219 112 96355 961521397
output:
97474170
result:
ok 1 number(s): "97474170"
Test #18:
score: 0
Accepted
time: 3ms
memory: 2392kb
input:
2 998244353 4 56 87114 727469702 14 24912 983690962
output:
592417090
result:
ok 1 number(s): "592417090"
Test #19:
score: 0
Accepted
time: 1ms
memory: 2384kb
input:
2 998244353 4 32 147776 617152567 28 775643 859007132
output:
566596649
result:
ok 1 number(s): "566596649"
Test #20:
score: 0
Accepted
time: 3ms
memory: 2452kb
input:
2 998244353 4 17 545281 464157011 56 816599 3898319
output:
469481867
result:
ok 1 number(s): "469481867"
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 1ms
memory: 2432kb
input:
7 1023063703 5 2 265354 1023063702 2 526733 1023063702 2 685323 1023063702 2 856929 1023063702 2 116643 1023063702 2 909182 1023063702 2 533391 1023063702
output:
72258463
result:
ok 1 number(s): "72258463"
Test #22:
score: 0
Accepted
time: 1ms
memory: 2408kb
input:
8 909973201 5 2 803753 909973200 2 909951 909973200 2 686418 909973200 2 751586 909973200 2 596938 909973200 2 931460 909973200 2 613477 909973200 2 716815 909973200
output:
446664445
result:
ok 1 number(s): "446664445"
Test #23:
score: 0
Accepted
time: 0ms
memory: 2372kb
input:
9 1016555329 5 2 955958 1016555328 2 672234 1016555328 2 870436 1016555328 2 31291 1016555328 2 206731 1016555328 2 727640 1016555328 2 134125 1016555328 2 893866 1016555328 2 138706 1016555328
output:
808692189
result:
ok 1 number(s): "808692189"
Test #24:
score: 0
Accepted
time: 0ms
memory: 2308kb
input:
10 1007394217 5 2 961834 1007394216 2 209391 1007394216 2 715582 1007394216 2 553353 1007394216 2 213960 1007394216 2 589617 1007394216 2 666503 1007394216 2 407731 1007394216 2 152967 1007394216 2 848445 1007394216
output:
9280802
result:
ok 1 number(s): "9280802"
Test #25:
score: 0
Accepted
time: 3ms
memory: 2384kb
input:
10 968522221 5 2 21932 968522220 2 675564 968522220 2 378437 968522220 2 81037 968522220 2 963992 968522220 2 311430 968522220 2 699121 968522220 2 45417 968522220 2 275308 968522220 2 411066 968522220
output:
692011298
result:
ok 1 number(s): "692011298"
Subtask #6:
score: 12
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #26:
score: 12
Accepted
time: 2ms
memory: 2420kb
input:
4 972401761 6 2 972661 972401760 15 255992 126248662 12 878880 606133410 2 224371 972401760
output:
115576065
result:
ok 1 number(s): "115576065"
Test #27:
score: 0
Accepted
time: 1ms
memory: 2448kb
input:
4 904442113 6 4 455381 759185044 32 370753 618464921 3 500887 212337160 2 124789 904442112
output:
423186989
result:
ok 1 number(s): "423186989"
Test #28:
score: 0
Accepted
time: 1ms
memory: 2516kb
input:
2 1044288001 6 200 909466 831914154 4 635879 349141366
output:
992703804
result:
ok 1 number(s): "992703804"
Test #29:
score: 0
Accepted
time: 3ms
memory: 2408kb
input:
3 995557889 6 208 995170 150328412 2 962966 995557888 2 870197 995557888
output:
559608682
result:
ok 1 number(s): "559608682"
Test #30:
score: 0
Accepted
time: 3ms
memory: 2448kb
input:
3 926933113 6 4 600105 859154928 24 395570 903534782 9 869027 266882176
output:
586077830
result:
ok 1 number(s): "586077830"
Test #31:
score: 0
Accepted
time: 3ms
memory: 2404kb
input:
4 1018608697 6 28 136320 512857858 2 391617 1018608696 2 416876 1018608696 8 640950 421343802
output:
275871736
result:
ok 1 number(s): "275871736"
Test #32:
score: 0
Accepted
time: 2ms
memory: 2352kb
input:
5 909759601 6 10 839897 853552356 2 969093 909759600 4 795795 674156232 2 423545 909759600 6 600787 419741593
output:
241411297
result:
ok 1 number(s): "241411297"
Test #33:
score: 0
Accepted
time: 3ms
memory: 2500kb
input:
4 998016823 6 27 155873 262940187 2 158035 998016822 9 202421 553668428 2 21539 998016822
output:
118420215
result:
ok 1 number(s): "118420215"
Test #34:
score: 0
Accepted
time: 3ms
memory: 2496kb
input:
4 910702297 6 3 890425 906157449 24 469847 206340805 2 422607 910702296 7 67244 714860697
output:
836808927
result:
ok 1 number(s): "836808927"
Test #35:
score: 0
Accepted
time: 2ms
memory: 2524kb
input:
2 965490689 6 4 468310 246473372 256 256288 754419658
output:
20502222
result:
ok 1 number(s): "20502222"
Subtask #7:
score: 8
Accepted
Dependency #6:
100%
Accepted
Test #36:
score: 8
Accepted
time: 10ms
memory: 2540kb
input:
4 1040169409 7 2 835454 1040169408 3 772774 636723579 4 342482 586400067 192 334236 48598666
output:
836620519
result:
ok 1 number(s): "836620519"
Test #37:
score: 0
Accepted
time: 11ms
memory: 2420kb
input:
5 1001291201 7 2 380607 1001291200 8 447454 176535093 32 876312 112032651 5 769899 24926973 2 833606 1001291200
output:
773216067
result:
ok 1 number(s): "773216067"
Test #38:
score: 0
Accepted
time: 14ms
memory: 2500kb
input:
3 1027170721 7 108 162949 530583958 8 335705 915297592 6 762677 864984184
output:
944135384
result:
ok 1 number(s): "944135384"
Test #39:
score: 0
Accepted
time: 15ms
memory: 2772kb
input:
4 965986561 7 672 958339 534727307 2 543173 965986560 2 884696 965986560 2 78668 965986560
output:
731390335
result:
ok 1 number(s): "731390335"
Test #40:
score: 0
Accepted
time: 11ms
memory: 2484kb
input:
5 1033312897 7 2 847300 1033312896 22 496446 176836498 4 545327 842729668 4 825711 842729668 8 55521 221623844
output:
111025694
result:
ok 1 number(s): "111025694"
Test #41:
score: 0
Accepted
time: 17ms
memory: 2604kb
input:
4 974073601 7 80 688089 65481914 6 743381 676241902 2 457097 974073600 6 433647 676241902
output:
20654041
result:
ok 1 number(s): "20654041"
Test #42:
score: 0
Accepted
time: 19ms
memory: 2548kb
input:
4 988969921 7 192 682290 823722245 2 231872 988969920 4 644835 908425877 4 599428 80544044
output:
327364135
result:
ok 1 number(s): "327364135"
Test #43:
score: 0
Accepted
time: 9ms
memory: 2424kb
input:
4 905233921 7 10 797498 529875391 40 404554 190390703 8 51869 591750273 2 267795 905233920
output:
840539530
result:
ok 1 number(s): "840539530"
Test #44:
score: 0
Accepted
time: 16ms
memory: 2556kb
input:
4 995124209 7 8 15181 811988629 4 25011 700264330 4 29108 700264330 52 401060 745256833
output:
704350003
result:
ok 1 number(s): "704350003"
Test #45:
score: 0
Accepted
time: 26ms
memory: 2512kb
input:
3 942316129 7 12 857153 473633986 72 777888 329202798 8 483455 869896725
output:
388869095
result:
ok 1 number(s): "388869095"
Test #46:
score: 0
Accepted
time: 16ms
memory: 2800kb
input:
3 1035901441 7 896 435538 726832882 4 15200 453561200 2 924673 1035901440
output:
938917469
result:
ok 1 number(s): "938917469"
Test #47:
score: 0
Accepted
time: 17ms
memory: 3128kb
input:
2 1019232001 7 4 673885 248868967 1920 754816 341141141
output:
476117109
result:
ok 1 number(s): "476117109"
Test #48:
score: 0
Accepted
time: 16ms
memory: 3636kb
input:
2 957116737 7 3888 412700 63632954 2 333017 957116736
output:
21716613
result:
ok 1 number(s): "21716613"
Test #49:
score: 0
Accepted
time: 28ms
memory: 2568kb
input:
2 1018688833 7 168 928533 47528245 48 431265 446651888
output:
377651323
result:
ok 1 number(s): "377651323"
Test #50:
score: 0
Accepted
time: 21ms
memory: 3032kb
input:
2 930680833 7 2048 213064 343165841 4 619665 206937758
output:
710731553
result:
ok 1 number(s): "710731553"
Subtask #8:
score: 6
Accepted
Dependency #4:
100%
Accepted
Test #51:
score: 6
Accepted
time: 1282ms
memory: 77260kb
input:
2 998244353 8 229376 553453 626702417 2 148397 998244352
output:
942359197
result:
ok 1 number(s): "942359197"
Test #52:
score: 0
Accepted
time: 2037ms
memory: 6536kb
input:
2 998244353 8 544 790355 550966489 896 187218 528905230
output:
821359943
result:
ok 1 number(s): "821359943"
Test #53:
score: 0
Accepted
time: 1949ms
memory: 7400kb
input:
2 998244353 8 3808 61621 800472218 128 340446 90326106
output:
313652514
result:
ok 1 number(s): "313652514"
Test #54:
score: 0
Accepted
time: 1969ms
memory: 7376kb
input:
2 998244353 8 3584 84070 488937671 136 502854 265129779
output:
311354359
result:
ok 1 number(s): "311354359"
Test #55:
score: 0
Accepted
time: 1859ms
memory: 7360kb
input:
2 998244353 8 128 745552 249745217 3808 24183 979437006
output:
800304170
result:
ok 1 number(s): "800304170"
Subtask #9:
score: 8
Accepted
Dependency #8:
100%
Accepted
Test #56:
score: 8
Accepted
time: 1013ms
memory: 4876kb
input:
2 998244353 9 1024 890631 674816215 256 505634 280778420
output:
252098958
result:
ok 1 number(s): "252098958"
Test #57:
score: 0
Accepted
time: 1919ms
memory: 6624kb
input:
3 998244353 9 256 272030 680107844 952 390160 81552934 2 248471 998244352
output:
659256944
result:
ok 1 number(s): "659256944"
Test #58:
score: 0
Accepted
time: 1301ms
memory: 10516kb
input:
3 998244353 9 14336 680183 785721917 8 733319 509520358 4 727219 86583718
output:
685697293
result:
ok 1 number(s): "685697293"
Test #59:
score: 0
Accepted
time: 1397ms
memory: 24192kb
input:
2 998244353 9 60928 148823 499088267 8 950907 372528824
output:
777164685
result:
ok 1 number(s): "777164685"
Test #60:
score: 0
Accepted
time: 762ms
memory: 4896kb
input:
3 998244353 9 4 486207 86583718 1904 558847 739086177 32 759123 910687289
output:
57611731
result:
ok 1 number(s): "57611731"
Test #61:
score: 0
Accepted
time: 1160ms
memory: 4756kb
input:
4 998244353 9 2 17862 998244352 2 536183 998244352 136 576612 607112440 512 287212 914464108
output:
714839257
result:
ok 1 number(s): "714839257"
Test #62:
score: 0
Accepted
time: 1603ms
memory: 6264kb
input:
5 998244353 9 4 931852 86583718 4 915233 86583718 7 355297 14553391 34 970627 511225650 128 974908 381262342
output:
711640581
result:
ok 1 number(s): "711640581"
Test #63:
score: 0
Accepted
time: 1467ms
memory: 6304kb
input:
6 998244353 9 238 953000 458625863 4 188309 911660635 2 335975 998244352 8 787731 509520358 4 209142 86583718 8 365300 509520358
output:
713841626
result:
ok 1 number(s): "713841626"
Test #64:
score: 0
Accepted
time: 645ms
memory: 4324kb
input:
5 998244353 9 4 101133 86583718 32 902625 666194801 34 58866 995719509 7 224335 779057549 8 994132 488723995
output:
365734961
result:
ok 1 number(s): "365734961"
Test #65:
score: 0
Accepted
time: 937ms
memory: 5984kb
input:
7 998244353 9 14 235694 983690962 8 744104 625715529 8 637536 625715529 8 100975 488723995 4 483443 911660635 2 863459 998244352 8 618213 509520358
output:
704893603
result:
ok 1 number(s): "704893603"
Test #66:
score: 0
Accepted
time: 878ms
memory: 4688kb
input:
6 998244353 9 8 237280 625715529 4 164854 911660635 4 222248 911660635 4 542353 86583718 4 863270 911660635 136 555788 418624303
output:
24164169
result:
ok 1 number(s): "24164169"
Test #67:
score: 0
Accepted
time: 676ms
memory: 4228kb
input:
7 998244353 9 112 335624 263656516 2 404823 998244352 2 612984 998244352 8 460719 509520358 4 759780 911660635 2 525332 998244352 8 561035 625715529
output:
831206565
result:
ok 1 number(s): "831206565"
Test #68:
score: 0
Accepted
time: 500ms
memory: 4188kb
input:
6 998244353 9 14 275099 314620134 8 772812 372528824 8 546908 625715529 2 662447 998244352 16 164487 661054123 8 993159 488723995
output:
50327783
result:
ok 1 number(s): "50327783"
Test #69:
score: 0
Accepted
time: 455ms
memory: 4164kb
input:
16 998244353 9 2 223902 998244352 2 356273 998244352 7 102151 530734902 2 124503 998244352 2 231032 998244352 2 764641 998244352 2 439592 998244352 2 626656 998244352 2 827889 998244352 2 683287 998244352 2 527533 998244352 2 96136 998244352 2 595457 998244352 2 630440 998244352 2 402492 998244352 2...
output:
662143805
result:
ok 1 number(s): "662143805"
Test #70:
score: 0
Accepted
time: 1371ms
memory: 149272kb
input:
1 998244353 9 487424 494448 849013356
output:
487424
result:
ok 1 number(s): "487424"
Subtask #10:
score: 10
Accepted
Dependency #5:
100%
Accepted
Test #71:
score: 10
Accepted
time: 59ms
memory: 2532kb
input:
15 969740263 10 2 373621 969740262 2 946569 969740262 2 253224 969740262 2 664561 969740262 2 611912 969740262 2 204304 969740262 2 746434 969740262 2 336578 969740262 2 200784 969740262 2 557632 969740262 2 651211 969740262 2 559106 969740262 2 610198 969740262 2 799763 969740262 2 908557 969740262
output:
411647692
result:
ok 1 number(s): "411647692"
Test #72:
score: 0
Accepted
time: 117ms
memory: 2796kb
input:
16 991926851 10 2 712792 991926850 2 396612 991926850 2 850616 991926850 2 678097 991926850 2 939368 991926850 2 978032 991926850 2 226041 991926850 2 545440 991926850 2 261283 991926850 2 142065 991926850 2 350488 991926850 2 915911 991926850 2 355737 991926850 2 57300 991926850 2 584284 991926850 ...
output:
529574589
result:
ok 1 number(s): "529574589"
Test #73:
score: 0
Accepted
time: 248ms
memory: 3320kb
input:
17 1004734669 10 2 774339 1004734668 2 761099 1004734668 2 350815 1004734668 2 956243 1004734668 2 13259 1004734668 2 547506 1004734668 2 459082 1004734668 2 817986 1004734668 2 724570 1004734668 2 935942 1004734668 2 560680 1004734668 2 520194 1004734668 2 260207 1004734668 2 852274 1004734668 2 56...
output:
426830028
result:
ok 1 number(s): "426830028"
Test #74:
score: 0
Accepted
time: 515ms
memory: 4332kb
input:
18 934497901 10 2 116198 934497900 2 820160 934497900 2 77657 934497900 2 611949 934497900 2 498059 934497900 2 471331 934497900 2 90116 934497900 2 413650 934497900 2 938011 934497900 2 455321 934497900 2 808088 934497900 2 467664 934497900 2 1790 934497900 2 746901 934497900 2 649412 934497900 2 9...
output:
132988262
result:
ok 1 number(s): "132988262"
Test #75:
score: 0
Accepted
time: 512ms
memory: 4480kb
input:
18 997115969 10 2 677091 997115968 2 182601 997115968 2 859073 997115968 2 844740 997115968 2 486819 997115968 2 239614 997115968 2 605204 997115968 2 108805 997115968 2 547452 997115968 2 78461 997115968 2 662608 997115968 2 930644 997115968 2 950692 997115968 2 223335 997115968 2 405750 997115968 ...
output:
576918483
result:
ok 1 number(s): "576918483"
Subtask #11:
score: 12
Accepted
Dependency #10:
100%
Accepted
Test #76:
score: 12
Accepted
time: 530ms
memory: 4028kb
input:
4 1032431401 11 22 699510 258557651 35 925197 147665025 12 561090 444222341 22 908847 573733633
output:
99475181
result:
ok 1 number(s): "99475181"
Test #77:
score: 0
Accepted
time: 727ms
memory: 4768kb
input:
5 990258361 11 26 569351 462961367 6 80029 91923647 28 860702 695739176 13 338538 474254325 5 292764 939161661
output:
153420054
result:
ok 1 number(s): "153420054"
Test #78:
score: 0
Accepted
time: 785ms
memory: 4836kb
input:
5 942013381 11 11 779531 345150756 6 675857 348180154 5 505879 317895062 22 723269 596862625 42 880286 229109913
output:
402752746
result:
ok 1 number(s): "402752746"
Test #79:
score: 0
Accepted
time: 1117ms
memory: 5732kb
input:
5 962729461 11 3 778362 370070893 10 605034 216793322 11 337490 739455560 28 33633 871490348 44 355775 427272628
output:
591659186
result:
ok 1 number(s): "591659186"
Test #80:
score: 0
Accepted
time: 878ms
memory: 5732kb
input:
6 980201041 11 6 509634 440462155 4 665806 169208619 13 174944 769308185 13 802268 979901095 7 735659 594468251 15 716016 587533173
output:
196440161
result:
ok 1 number(s): "196440161"
Test #81:
score: 0
Accepted
time: 1224ms
memory: 5900kb
input:
5 1006335331 11 33 465476 412382195 26 62659 649367959 10 379814 435149835 26 32613 193899237 2 362546 1006335330
output:
767433541
result:
ok 1 number(s): "767433541"
Test #82:
score: 0
Accepted
time: 1095ms
memory: 6024kb
input:
7 1025362801 11 2 103702 1025362800 3 230121 393065710 3 866490 393065710 5 996945 438528644 7 75346 889862126 22 727767 723881393 33 744345 331906350
output:
624948293
result:
ok 1 number(s): "624948293"
Test #83:
score: 0
Accepted
time: 1294ms
memory: 6296kb
input:
6 927400321 11 34 690193 633272049 14 271947 158466609 5 29155 48767577 3 680991 558580854 34 504089 50083535 2 269784 927400320
output:
529445988
result:
ok 1 number(s): "529445988"
Test #84:
score: 0
Accepted
time: 537ms
memory: 4172kb
input:
6 1026720001 11 5 856582 192380835 4 275465 826256064 2 577506 1026720000 30 726584 514798836 8 226229 122245655 24 708136 70845584
output:
196483828
result:
ok 1 number(s): "196483828"
Test #85:
score: 0
Accepted
time: 784ms
memory: 4700kb
input:
7 1048614337 11 8 81957 714673501 28 132495 421563936 2 981004 1048614336 2 730100 1048614336 2 504455 1048614336 42 710077 567746601 4 890757 467835333
output:
717647484
result:
ok 1 number(s): "717647484"
Test #86:
score: 0
Accepted
time: 761ms
memory: 4844kb
input:
6 1048924801 11 10 89570 521413525 4 496152 501406936 2 700711 1048924800 8 812007 592618035 48 653132 179779517 10 998767 343279042
output:
956663514
result:
ok 1 number(s): "956663514"
Test #87:
score: 0
Accepted
time: 912ms
memory: 5104kb
input:
5 1010095921 11 6 530393 687121127 30 440107 843763139 12 684275 324267076 4 691228 475079850 40 649981 506902675
output:
525817982
result:
ok 1 number(s): "525817982"
Test #88:
score: 0
Accepted
time: 869ms
memory: 5400kb
input:
7 935718661 11 20 799816 725732576 4 922930 747355853 2 463829 935718660 2 766609 935718660 4 175830 747355853 15 238560 611128660 20 768805 48007705
output:
339402274
result:
ok 1 number(s): "339402274"
Test #89:
score: 0
Accepted
time: 1094ms
memory: 5868kb
input:
7 904611457 11 3 896340 681718948 4 145563 9216110 8 315633 570585560 42 124915 772177444 2 790943 904611456 7 756555 392957847 8 680504 387697417
output:
513967674
result:
ok 1 number(s): "513967674"
Test #90:
score: 0
Accepted
time: 1006ms
memory: 6048kb
input:
7 954670081 11 2 181551 954670080 6 601961 633710667 20 415802 518488008 16 36518 470515757 6 527605 633710667 2 772131 954670080 10 592493 212387045
output:
845226312
result:
ok 1 number(s): "845226312"
Subtask #12:
score: 6
Accepted
Dependency #7:
100%
Accepted
Dependency #9:
100%
Accepted
Dependency #11:
100%
Accepted
Test #91:
score: 6
Accepted
time: 1320ms
memory: 10132kb
input:
2 940283521 12 10128 916891 881732406 40 319509 229502633
output:
819210562
result:
ok 1 number(s): "819210562"
Test #92:
score: 0
Accepted
time: 1500ms
memory: 7996kb
input:
3 964109281 12 4460 529113 561201332 2 584568 964109280 48 959674 576980669
output:
185961710
result:
ok 1 number(s): "185961710"
Test #93:
score: 0
Accepted
time: 1733ms
memory: 5956kb
input:
3 985543201 12 12 423534 630035952 80 534310 861430626 454 886448 982755151
output:
158666490
result:
ok 1 number(s): "158666490"
Test #94:
score: 0
Accepted
time: 1217ms
memory: 6424kb
input:
4 974715601 12 10 822569 896595666 12 381386 199317125 2 592870 974715600 1832 873842 760178656
output:
512490541
result:
ok 1 number(s): "512490541"
Test #95:
score: 0
Accepted
time: 1270ms
memory: 7148kb
input:
4 959195761 12 2330 338858 281585961 4 224822 442548969 8 161907 456904616 6 171896 132568499
output:
901449688
result:
ok 1 number(s): "901449688"
Test #96:
score: 0
Accepted
time: 1245ms
memory: 6316kb
input:
5 906775561 12 5 108955 894444589 8 23657 502875925 12 69485 110286081 2 298454 906775560 478 562053 185780167
output:
117102764
result:
ok 1 number(s): "117102764"
Test #97:
score: 0
Accepted
time: 1459ms
memory: 6152kb
input:
5 921044161 12 32 488663 76321973 5 345291 507072799 6 357954 895020767 241 381073 310674276 2 516952 921044160
output:
21557079
result:
ok 1 number(s): "21557079"
Test #98:
score: 0
Accepted
time: 1408ms
memory: 6356kb
input:
4 960105121 12 20 61235 629292865 502 758953 338610188 6 31315 307440177 8 309913 475159507
output:
539745126
result:
ok 1 number(s): "539745126"
Test #99:
score: 0
Accepted
time: 1590ms
memory: 6408kb
input:
5 1004489641 12 257 442823 397311768 8 616213 469865403 4 50596 408619556 20 322882 375967564 3 453830 583595012
output:
526555385
result:
ok 1 number(s): "526555385"
Test #100:
score: 0
Accepted
time: 1417ms
memory: 7460kb
input:
4 1002845101 12 30 937948 43797392 4036 664622 563453039 2 76177 1002845100 2 992569 1002845100
output:
235148813
result:
ok 1 number(s): "235148813"
Test #101:
score: 0
Accepted
time: 1460ms
memory: 6792kb
input:
4 936437461 12 30 958117 452004031 4 233553 578995550 2 800696 936437460 2026 445979 901166189
output:
842824070
result:
ok 1 number(s): "842824070"
Test #102:
score: 0
Accepted
time: 1392ms
memory: 8500kb
input:
4 967479361 12 5095 693179 480545460 4 557405 24233647 8 145874 594769868 3 287627 802063289
output:
136118600
result:
ok 1 number(s): "136118600"
Test #103:
score: 0
Accepted
time: 1362ms
memory: 8552kb
input:
4 925761121 12 6126 135605 711742328 4 428900 296402215 2 586889 925761120 10 492678 408666890
output:
573527672
result:
ok 1 number(s): "573527672"
Test #104:
score: 0
Accepted
time: 1500ms
memory: 8812kb
input:
6 1041722401 12 5 164243 565473986 2 669751 1041722400 6 495765 971750216 2 771390 1041722400 4 270828 827058779 1031 895005 554360088
output:
721402587
result:
ok 1 number(s): "721402587"
Test #105:
score: 0
Accepted
time: 1499ms
memory: 9340kb
input:
5 997939981 12 3 835560 887273591 10 538742 92659661 4 310465 448614931 2 123413 997939980 2066 103520 853352
output:
993763929
result:
ok 1 number(s): "993763929"
Test #106:
score: 0
Accepted
time: 1551ms
memory: 9396kb
input:
5 949188841 12 2 141270 949188840 20 493997 317310843 2 853188 949188840 2078 838599 833342537 3 552003 403814483
output:
889441128
result:
ok 1 number(s): "889441128"
Test #107:
score: 0
Accepted
time: 398ms
memory: 6172kb
input:
8 1036067761 12 10 416938 177402038 4 559871 951496097 12 175026 919588307 4 595348 951496097 2 982924 1036067760 2 405420 1036067760 4 347313 951496097 7 946965 429684228
output:
553020182
result:
ok 1 number(s): "553020182"
Test #108:
score: 0
Accepted
time: 645ms
memory: 6940kb
input:
8 1004240161 12 6 296913 663971589 6 366581 663971589 8 147391 748751600 2 955732 1004240160 10 85111 577005150 2 931695 1004240160 2 79627 1004240160 14 934105 575837948
output:
440759412
result:
ok 1 number(s): "440759412"
Test #109:
score: 0
Accepted
time: 932ms
memory: 7188kb
input:
8 953156161 12 2 749780 953156160 2 666434 953156160 2 664135 953156160 8 578893 936686511 6 48776 789310653 4 980429 190825120 2 470040 953156160 110 859649 241053346
output:
774169072
result:
ok 1 number(s): "774169072"
Test #110:
score: 0
Accepted
time: 1006ms
memory: 5568kb
input:
8 979767361 12 2 425831 979767360 16 178102 9165626 2 240448 979767360 2 797490 979767360 2 120283 979767360 30 335709 674074218 2 760289 979767360 26 320926 553345576
output:
166534822
result:
ok 1 number(s): "166534822"
Test #111:
score: 0
Accepted
time: 1297ms
memory: 5864kb
input:
9 1040921701 12 2 342279 1040921700 2 575382 1040921700 12 338599 38878157 2 289503 1040921700 4 390795 195107884 2 210642 1040921700 70 512604 525671225 4 612237 845813817 2 953087 1040921700
output:
478615806
result:
ok 1 number(s): "478615806"
Test #112:
score: 0
Accepted
time: 1004ms
memory: 6068kb
input:
8 902221321 12 2 727095 902221320 11 566951 570627224 2 207388 902221320 2 217661 902221320 21 171322 496957039 4 328618 364571187 8 67174 659903664 8 35381 349978672
output:
325234098
result:
ok 1 number(s): "325234098"
Test #113:
score: 0
Accepted
time: 1041ms
memory: 6156kb
input:
9 1011754801 12 7 238495 134006536 4 768617 691946137 18 537125 233835973 2 584327 1011754800 2 460415 1011754800 2 701739 1011754800 2 321821 1011754800 3 168496 485383365 20 21593 396687980
output:
790558667
result:
ok 1 number(s): "790558667"
Test #114:
score: 0
Accepted
time: 1272ms
memory: 149472kb
input:
1 952414649 12 493991 642637 798174221
output:
493991
result:
ok 1 number(s): "493991"
Test #115:
score: 0
Accepted
time: 2577ms
memory: 8348kb
input:
3 996787007 12 67 388369 991505886 83 593046 106506264 89 765490 171907274
output:
646679314
result:
ok 1 number(s): "646679314"
Test #116:
score: 0
Accepted
time: 1880ms
memory: 8564kb
input:
2 1039371559 12 79 92678 336932966 6283 314443 261579480
output:
989406346
result:
ok 1 number(s): "989406346"
Test #117:
score: 0
Accepted
time: 2595ms
memory: 6360kb
input:
3 918529841 12 79 65267 903684432 71 677401 582535550 89 398315 541715787
output:
573181569
result:
ok 1 number(s): "573181569"
Test #118:
score: 0
Accepted
time: 1126ms
memory: 6528kb
input:
3 952251301 12 2310 73753 701445334 6 476123 663720703 26 61857 617439077
output:
287332583
result:
ok 1 number(s): "287332583"
Test #119:
score: 0
Accepted
time: 1610ms
memory: 7568kb
input:
4 928675441 12 132 498937 723714791 10 155140 688217707 2 183844 928675440 147 172893 735125766
output:
578553575
result:
ok 1 number(s): "578553575"
Test #120:
score: 0
Accepted
time: 1276ms
memory: 7612kb
input:
4 1035609121 12 6 768099 265932961 30 116268 505398613 182 612149 528298388 12 713349 392936811
output:
56807518
result:
ok 1 number(s): "56807518"
Test #121:
score: 0
Accepted
time: 1438ms
memory: 7772kb
input:
4 941579101 12 21 528779 473778183 225 928653 422638104 44 458686 687559060 2 886515 941579100
output:
752918048
result:
ok 1 number(s): "752918048"
Test #122:
score: 0
Accepted
time: 1145ms
memory: 7884kb
input:
5 923130601 12 2 45235 923130600 17 848848 239357641 30 973849 407373432 14 114480 423445517 30 324043 215683557
output:
484086499
result:
ok 1 number(s): "484086499"
Test #123:
score: 0
Accepted
time: 1410ms
memory: 8120kb
input:
6 1017989281 12 2 172394 1017989280 7 616861 1017508889 8 147746 183941737 66 2325 40564271 3 663516 74086722 20 473402 886782526
output:
557292174
result:
ok 1 number(s): "557292174"
Test #124:
score: 0
Accepted
time: 1514ms
memory: 8020kb
input:
5 997926931 12 42 90388 302627328 2 426939 997926930 10 118325 842908340 90 257428 556605406 6 975615 937490888
output:
777574268
result:
ok 1 number(s): "777574268"
Test #125:
score: 0
Accepted
time: 1644ms
memory: 6088kb
input:
6 914700151 12 65 842507 424930724 49 62967 642752500 6 137236 603809437 2 635830 914700150 2 808357 914700150 6 832292 310890715
output:
166163595
result:
ok 1 number(s): "166163595"
Test #126:
score: 0
Accepted
time: 1442ms
memory: 6656kb
input:
4 950019841 12 12 64558 109760691 15 667317 675243511 2 978550 950019840 1309 969513 640374249
output:
11564562
result:
ok 1 number(s): "11564562"
Test #127:
score: 0
Accepted
time: 1296ms
memory: 6092kb
input:
6 1017992641 12 38 934427 757399582 12 521945 68515975 3 770385 377978918 35 726573 606684726 5 639006 825344673 2 768656 1017992640
output:
793025770
result:
ok 1 number(s): "793025770"
Test #128:
score: 0
Accepted
time: 1704ms
memory: 6456kb
input:
4 1032431401 12 10 773519 634237118 2 473563 1032431400 546 391665 196833300 44 990054 519575415
output:
638516534
result:
ok 1 number(s): "638516534"
Test #129:
score: 0
Accepted
time: 1156ms
memory: 6332kb
input:
7 1038557521 12 5 556284 591278962 39 904101 1028030401 3 532965 165612271 6 825185 872945250 5 301722 956190774 2 256370 1038557520 14 618680 158028144
output:
486790345
result:
ok 1 number(s): "486790345"
Test #130:
score: 0
Accepted
time: 1270ms
memory: 6300kb
input:
7 907137001 12 6 380959 117708860 6 608834 789428142 3 633154 117708859 4 568352 850222375 55 970552 433791124 3 469231 789428141 7 953744 470478510
output:
627924542
result:
ok 1 number(s): "627924542"
Extra Test:
score: 0
Extra Test Passed