NOI.AC

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#185024	#2157. 数列	snow_trace	100	763ms	1196kb	C++11	795b	2023-09-19 10:43:03	2023-09-19 12:08:34

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p,mod;
int qp(int p,int q){
	int ans = 1,pro = p;
	while(q){
		if(q&1)ans = ans*pro%mod;
		pro = pro*pro%mod;q>>=1;
	}return ans;
}
signed main(){
	cin >> n >> p;mod=  p;
	int cnt =0,now = 2*n;
	while(now){
		cnt+=now/p,now/=p;
	}now = n;
	while(now){
		cnt-=now/p,now/=p;
	}now = n+1;
	while(now){
		cnt-=now/p,now/=p;
	}if(cnt){
		cout << 0 << endl;return 0;
	}int pro1=1,pro2 = 1,pro3 = 1;
	for(int i = 1;i<=2*n;i++){
		if(i%p == 0)continue;
		pro1 = pro1*i%mod;
	}for(int i = 1;i<=n;i++){
		if(i%p == 0)continue;
		pro2 = pro2*i%mod;
	}for(int i = 1;i<=n+1;i++){
		if(i%p == 0)continue;
		pro3 = pro3*i%mod;
	}cout << pro1*qp(pro2,mod-2)%mod*qp(pro3,mod-2)%mod << endl;
	return 0;
}

Source code, Language: C++11

Details

小提示：点击横条可展开更详细的信息

Test #1:

score: 5

Accepted

time: 0ms

memory: 1192kb

input:

921 998054347

output:

345389219

result:

ok single line: '345389219'

Test #2:

score: 5

Accepted

time: 0ms

memory: 1196kb

input:

926 998064329

output:

458756691

result:

ok single line: '458756691'

Test #3:

score: 5

Accepted

time: 0ms

memory: 1196kb

input:

1000 998074327

output:

457273797

result:

ok single line: '457273797'

Test #4:

score: 5

Accepted

time: 0ms

memory: 1192kb

input:

952 998084303

output:

329700115

result:

ok single line: '329700115'

Test #5:

score: 5

Accepted

time: 1ms

memory: 1196kb

input:

989 998094347

output:

94788253

result:

ok single line: '94788253'

Test #6:

score: 5

Accepted

time: 0ms

memory: 1192kb

input:

902 998104313

output:

911969455

result:

ok single line: '911969455'

Test #7:

score: 5

Accepted

time: 0ms

memory: 1196kb

input:

914 998114333

output:

827812986

result:

ok single line: '827812986'

Test #8:

score: 5

Accepted

time: 0ms

memory: 1196kb

input:

986 998124313

output:

169699253

result:

ok single line: '169699253'

Test #9:

score: 5

Accepted

time: 1ms

memory: 1196kb

input:

947 998134339

output:

761932751

result:

ok single line: '761932751'

Test #10:

score: 5

Accepted

time: 0ms

memory: 1196kb

input:

934 998144339

output:

42889072

result:

ok single line: '42889072'

Test #11:

score: 5

Accepted

time: 74ms

memory: 1196kb

input:

991572 998154343

output:

277089318

result:

ok single line: '277089318'

Test #12:

score: 5

Accepted

time: 77ms

memory: 1196kb

input:

932800 998164337

output:

945072504

result:

ok single line: '945072504'

Test #13:

score: 5

Accepted

time: 72ms

memory: 1192kb

input:

903603 998174341

output:

29916736

result:

ok single line: '29916736'

Test #14:

score: 5

Accepted

time: 80ms

memory: 1192kb

input:

958646 998184331

output:

802903490

result:

ok single line: '802903490'

Test #15:

score: 5

Accepted

time: 78ms

memory: 1192kb

input:

983016 998194349

output:

802900579

result:

ok single line: '802900579'

Test #16:

score: 5

Accepted

time: 73ms

memory: 1196kb

input:

922347 998204353

output:

228575331

result:

ok single line: '228575331'

Test #17:

score: 5

Accepted

time: 77ms

memory: 1192kb

input:

976053 998214317

output:

982618317

result:

ok single line: '982618317'

Test #18:

score: 5

Accepted

time: 76ms

memory: 1196kb

input:

957300 998224351

output:

514549818

result:

ok single line: '514549818'

Test #19:

score: 5

Accepted

time: 77ms

memory: 1196kb

input:

921760 998234353

output:

470386410

result:

ok single line: '470386410'

Test #20:

score: 5

Accepted

time: 77ms

memory: 1192kb

input:

912948 998244353

output:

129235345

result:

ok single line: '129235345'