QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#62151#5031. 核Appleblue1760 670ms64376kbC++141.5kb2022-11-17 16:00:022022-11-17 16:00:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-17 16:00:02]
  • 评测
  • 测评结果:60
  • 用时:670ms
  • 内存:64376kb
  • [2022-11-17 16:00:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n,q,mod,ans;
int ksm(int a,long long x,int p=mod){
	int tot=1;
	while(x){
		if(x & 1ll) tot=1ll*tot*a%p;
		a=1ll*a*a%p;
		x>>=1ll;
	}
	return tot;
}
int pw[N],ipw[N],PW[N],mul[N],inv[N];
int pw_nk[N],ipw_knk[N],pw_nnkk[N];
void init(int lim){
	int invq=ksm(q,mod-2);
	
	pw[0]=ipw[0]=1;
	for(int i=1;i<=lim;i++) pw[i]=1ll*pw[i-1]*q%mod;
	for(int i=1;i<=lim;i++) ipw[i]=1ll*ipw[i-1]*invq%mod;
	
	int pwn=ksm(q,n,mod-1);
	pw_nk[0]=1;
	for(int i=1;i<=lim;i++) pw_nk[i]=1ll*pw_nk[i-1]*pwn%(mod-1);
	
	ipw_knk[0]=1;
	for(int i=1;i<=lim;i++) ipw_knk[i]=1ll*ipw_knk[i-1]*ipw[n]%mod*pw[i-1]%mod*pw[i-1]%mod;
	
	pw_nnkk[0]=ksm(q,1ll*n*(n-1)/2%(mod-1));
	for(int i=1;i<=lim;i++) pw_nnkk[i]=1ll*pw_nnkk[i-1]*ipw[i-1]%mod;
	
	
	for(int i=1;i<=lim;i++) PW[i]=(1+mod-pw[i])%mod;
	
	mul[0]=inv[0]=1;
	for(int i=1;i<=lim;i++) mul[i]=1ll*mul[i-1]*PW[i]%mod;
	inv[lim]=ksm(mul[lim],mod-2);
	for(int i=lim-1;i>=1;i--) inv[i]=1ll*inv[i+1]*PW[i+1]%mod;
	
}
int C(int m,int n){
	if(m<0 || n<0 || m<n) return 0;
	return 1ll*mul[m]*inv[n]%mod*inv[m-n]%mod;
}
int ID(int x){
	return (x & 1ll)?mod-1:1;
}

int f[N],g[N];

int main(){
	cin>>n>>q>>mod;
	init(n);
	
	g[0]=1;
	for(int k=1;k<=n;k++){
		g[k]=(1ll*g[k-1]*(1+mod-ipw[n-k+1])%mod+1ll*ipw_knk[k]*inv[k]%mod)%mod;
	}
	
	for(int k=0;k<=n;k++){
		f[k]=1ll*g[n-k]*ID(n-k)%mod*mul[n-k]%mod*C(n,k)%mod*pw_nnkk[k]%mod;
	}
	for(int i=0;i<=n;i++) ans=(ans+1ll*f[i]*ksm(3,pw_nk[i])%mod)%mod;
	cout<<ans;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 21656kb

input:

1 2 540053233

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 6ms
memory: 21800kb

input:

2 2 156542707

output:

43046970

result:

ok 1 number(s): "43046970"

Test #3:

score: 0
Accepted
time: 2ms
memory: 21672kb

input:

1 2 186225229

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 2ms
memory: 21672kb

input:

3 3 109884329

output:

100602209

result:

ok 1 number(s): "100602209"

Test #5:

score: 0
Accepted
time: 2ms
memory: 21900kb

input:

1 2 144802297

output:

9

result:

ok 1 number(s): "9"

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 20
Accepted
time: 0ms
memory: 21644kb

input:

20 21992843 328859143

output:

110137213

result:

ok 1 number(s): "110137213"

Test #7:

score: 0
Accepted
time: 1ms
memory: 21820kb

input:

22 332524739 654888401

output:

410922781

result:

ok 1 number(s): "410922781"

Test #8:

score: 0
Accepted
time: 2ms
memory: 21668kb

input:

26 302215049 566649113

output:

221720840

result:

ok 1 number(s): "221720840"

Test #9:

score: 0
Accepted
time: 2ms
memory: 21824kb

input:

15 111009527 722130737

output:

648834664

result:

ok 1 number(s): "648834664"

Test #10:

score: 0
Accepted
time: 2ms
memory: 21828kb

input:

82 110032063 394529383

output:

111730592

result:

ok 1 number(s): "111730592"

Test #11:

score: 0
Accepted
time: 2ms
memory: 21644kb

input:

9 11172911 259650437

output:

68381774

result:

ok 1 number(s): "68381774"

Test #12:

score: 0
Accepted
time: 0ms
memory: 21672kb

input:

86 12016027 354886243

output:

263687778

result:

ok 1 number(s): "263687778"

Test #13:

score: 0
Accepted
time: 3ms
memory: 21732kb

input:

91 273689959 454097881

output:

114436127

result:

ok 1 number(s): "114436127"

Test #14:

score: 0
Accepted
time: 2ms
memory: 21744kb

input:

73 148878967 694206977

output:

176215101

result:

ok 1 number(s): "176215101"

Test #15:

score: 0
Accepted
time: 2ms
memory: 21792kb

input:

45 205982233 227598247

output:

156769598

result:

ok 1 number(s): "156769598"

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #16:

score: 10
Accepted
time: 4ms
memory: 21756kb

input:

2778 122825869 147297463

output:

43419574

result:

ok 1 number(s): "43419574"

Test #17:

score: 0
Accepted
time: 2ms
memory: 21812kb

input:

289 7729669 589652893

output:

552952137

result:

ok 1 number(s): "552952137"

Test #18:

score: 0
Accepted
time: 2ms
memory: 21904kb

input:

2281 35651417 203950963

output:

21659018

result:

ok 1 number(s): "21659018"

Test #19:

score: 0
Accepted
time: 2ms
memory: 21816kb

input:

1684 258745639 373223677

output:

355596229

result:

ok 1 number(s): "355596229"

Test #20:

score: 0
Accepted
time: 2ms
memory: 21668kb

input:

2107 86850989 455823859

output:

245960059

result:

ok 1 number(s): "245960059"

Test #21:

score: 0
Accepted
time: 2ms
memory: 21676kb

input:

1323 43290799 791120419

output:

509649562

result:

ok 1 number(s): "509649562"

Test #22:

score: 0
Accepted
time: 2ms
memory: 21664kb

input:

2401 34064903 185314627

output:

70571452

result:

ok 1 number(s): "70571452"

Test #23:

score: 0
Accepted
time: 2ms
memory: 21816kb

input:

1073 82288187 564447959

output:

168200843

result:

ok 1 number(s): "168200843"

Test #24:

score: 0
Accepted
time: 8ms
memory: 21744kb

input:

1926 29995039 129122281

output:

60921463

result:

ok 1 number(s): "60921463"

Test #25:

score: 0
Accepted
time: 2ms
memory: 21824kb

input:

3000 66915659 765705179

output:

222619979

result:

ok 1 number(s): "222619979"

Subtask #4:

score: 20
Accepted

Test #26:

score: 20
Accepted
time: 670ms
memory: 59104kb

input:

998818 198334853 998244353

output:

153251445

result:

ok 1 number(s): "153251445"

Test #27:

score: 0
Accepted
time: 626ms
memory: 60272kb

input:

914379 128814383 998244353

output:

477606145

result:

ok 1 number(s): "477606145"

Test #28:

score: 0
Accepted
time: 624ms
memory: 57232kb

input:

944474 478445339 998244353

output:

174204073

result:

ok 1 number(s): "174204073"

Test #29:

score: 0
Accepted
time: 650ms
memory: 64340kb

input:

948637 711592127 998244353

output:

178256114

result:

ok 1 number(s): "178256114"

Test #30:

score: 0
Accepted
time: 614ms
memory: 59816kb

input:

927564 14465663 998244353

output:

315244613

result:

ok 1 number(s): "315244613"

Test #31:

score: 0
Accepted
time: 623ms
memory: 57476kb

input:

934615 392799073 998244353

output:

892700270

result:

ok 1 number(s): "892700270"

Test #32:

score: 0
Accepted
time: 601ms
memory: 57560kb

input:

917196 124972031 998244353

output:

782017412

result:

ok 1 number(s): "782017412"

Test #33:

score: 0
Accepted
time: 647ms
memory: 57580kb

input:

957149 392606173 998244353

output:

159348443

result:

ok 1 number(s): "159348443"

Test #34:

score: 0
Accepted
time: 670ms
memory: 64376kb

input:

997042 184649453 998244353

output:

464643024

result:

ok 1 number(s): "464643024"

Test #35:

score: 0
Accepted
time: 639ms
memory: 59780kb

input:

953353 14071961 998244353

output:

391688875

result:

ok 1 number(s): "391688875"

Subtask #5:

score: 0
Time Limit Exceeded

Test #36:

score: 0
Time Limit Exceeded

input:

9909956 720431399 720431401

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

0%