QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#85781	#5099. 朝圣道	321625	30	5115ms	19000kb	C++14	1.3kb	2023-03-08 15:20:03	2023-03-08 15:20:05

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-08 15:20:05]
评测

测评结果：30
用时：5115ms
内存：19000kb

查看

[2023-03-08 15:20:03]
提交

answer

#include "pilgrimage.h"
typedef long long ll;
int p[8],pk[8],rel[8],ps,P;
int bf[8][1000007],inv4;
void exgcd(int a,int b,int&x,int&y)
{
	if(!b){x=1;y=0;return;}
	exgcd(b,a%b,y,x);y-=a/b*x;
}
int inv(int x,int p){int res;exgcd(x,p,res,x);return (res+p)%p;}
ll qpow(ll x,ll y,ll p){ll r=1;for(;y;x=x*x%p,y>>=1)if(y&1)r=r*x%p;return r;}
void init(int,int pr)
{
	inv4=inv(4,P=pr);
	for(int i=2;i*i<=P;++i) 
		if(!(pr%i))
	{
		p[++ps]=i;pk[ps]=1;
		while(!(pr%i))pr/=i,pk[ps]*=i;
	}
	if(pr!=1)p[++ps]=pr,pk[ps]=pr;
	for(int i=1;i<=ps;++i)
	{
		exgcd((P/pk[i])%pk[i],pk[i],rel[i],pr);
		if(rel[i]<0)rel[i]+=pk[i];
	}
	for(int i=1;i<=ps;++i)
	{
		bf[i][0]=1;
		for(int j=1;j<pk[i];++j)
			bf[i][j]=(ll)bf[i][j-1]*(j%p[i]?j:1)%pk[i];
	}
}
ll cf(int p,ll n){ll ans=0;while(n)ans+=(n/=p);return ans;}
int fl(int id,ll n){return n?fl(id,n/p[id])*qpow(bf[id][pk[id]-1],n/p[id],pk[id])%pk[id]*bf[id][n%pk[id]]%pk[id]:1;}
int cal(int id,ll n,ll m)
{
	ll z=cf(p[id],n)-cf(p[id],n-m)-cf(p[id],m);int ans=1;while(z--&&ans)ans*=p[id];
	return ans?((ll)ans*fl(id,n)%pk[id]*inv(fl(id,m),pk[id])%pk[id]*inv(fl(id,n-m),pk[id])%pk[id]):0;
}
int C(ll n,ll m)
{
	int ans=0;
	for(int i=1;i<=ps;++i)
		ans=(ans+(ll)rel[i]*cal(i,n,m))%P;
	return ans;
}
int ask(ll n){return qpow(inv4,n,P)*(n%P)%P*C(n+n,n)%P;}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 4

Accepted

time: 420ms

memory: 11808kb

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:

result:

ok 910276 numbers

Test #2:

score: -4

Wrong Answer

time: 1809ms

memory: 19000kb

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:

result:

wrong answer 1st numbers differ - expected: '117936', found: '265783'

Subtask #2:

score: 0

Skipped

Dependency #1:

Subtask #3:

score: 12

Accepted

Test #5:

score: 12

Accepted

time: 8ms

memory: 11516kb

input:

3 1 334547
8234

output:

result:

ok 1 number(s): "179079"

Subtask #4:

score: 18

Accepted

Dependency #3:

100%

Accepted

Test #6:

score: 18

Accepted

time: 867ms

memory: 13280kb

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:

result:

ok 1000000 numbers

Subtask #5:

score: 0

Wrong Answer

Dependency #4:

100%

Accepted

Test #7:

score: 0

Wrong Answer

time: 5115ms

memory: 13660kb

input:

5 1000000 840643
596357868225427095
792903040511847841
549819683428503148
982786835970534376
855138540813992974
101968907510306081
885121351101383723
127972727417081251
728407510651610501
998897446686193527
889398142082696651
17276066104970301
87773104284997915
716559595019194816
538865162230963483
...

output:

result:

wrong output format Expected integer, but "

Subtask #6:

score: 0

Time Limit Exceeded

Test #8:

score: 0

Time Limit Exceeded

input:

6 958477 522361
280121915553826833
734266539148641647
72849162479700582
274266741463686096
60278972064195458
828423669427600612
571432949203039978
518511460268700898
486268614705621285
19216283231217074
611458416727512530
175147354285288662
799769622289998997
400123443628688299
145546980862133838
40...

output:

Unauthorized output

result:

Subtask #7:

score: 0

Wrong Answer

Dependency #3:

100%

Accepted

Test #13:

score: 0

Wrong Answer

time: 1ms

memory: 11512kb

input:

7 1 731039
314313205082038759

output:

result:

wrong output format Expected integer, but "

Subtask #8:

score: 0

Wrong Answer

Test #33:

score: 0

Wrong Answer

time: 117ms

memory: 9492kb

input:

8 9963 251
831797004675585320
494759973681332858
701341496127272302
252910460485222469
250965009655458584
366193481309061299
633134388675839346
791999098066205672
196620805863610860
363773642045280947
466508590762410710
407790578717064135
181590911404670570
570642047249889864
70138464625729452
23634...

output:

0
<

result:

wrong output format Expected integer, but "<" found

Subtask #9:

score: 0

Skipped