QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75581#4910. Numbers4182_543_731100 ✓2595ms149472kbC++3.2kb2023-02-05 20:48:192023-02-05 20:48:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 20:48:22]
  • 评测
  • 测评结果:100
  • 用时:2595ms
  • 内存:149472kb
  • [2023-02-05 20:48:19]
  • 提交

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