QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#62148#5031. 核Appleblue1730 1751ms328504kbC++141.5kb2022-11-17 15:57:582022-11-17 15:58:01

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 15:58:01]
  • 评测
  • 测评结果:30
  • 用时:1751ms
  • 内存:328504kb
  • [2022-11-17 15:57:58]
  • 提交

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-5);
	
	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: 1174ms
memory: 318060kb

input:

1 2 540053233

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 1199ms
memory: 319256kb

input:

2 2 156542707

output:

43046970

result:

ok 1 number(s): "43046970"

Test #3:

score: 0
Accepted
time: 1176ms
memory: 318568kb

input:

1 2 186225229

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 1181ms
memory: 319004kb

input:

3 3 109884329

output:

100602209

result:

ok 1 number(s): "100602209"

Test #5:

score: 0
Accepted
time: 1171ms
memory: 318076kb

input:

1 2 144802297

output:

9

result:

ok 1 number(s): "9"

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #6:

score: 20
Accepted
time: 1167ms
memory: 318944kb

input:

20 21992843 328859143

output:

110137213

result:

ok 1 number(s): "110137213"

Test #7:

score: 0
Accepted
time: 1189ms
memory: 319432kb

input:

22 332524739 654888401

output:

410922781

result:

ok 1 number(s): "410922781"

Test #8:

score: 0
Accepted
time: 1200ms
memory: 319044kb

input:

26 302215049 566649113

output:

221720840

result:

ok 1 number(s): "221720840"

Test #9:

score: 0
Accepted
time: 1202ms
memory: 317948kb

input:

15 111009527 722130737

output:

648834664

result:

ok 1 number(s): "648834664"

Test #10:

score: 0
Accepted
time: 1184ms
memory: 319656kb

input:

82 110032063 394529383

output:

111730592

result:

ok 1 number(s): "111730592"

Test #11:

score: 0
Accepted
time: 1187ms
memory: 319224kb

input:

9 11172911 259650437

output:

68381774

result:

ok 1 number(s): "68381774"

Test #12:

score: 0
Accepted
time: 1176ms
memory: 318620kb

input:

86 12016027 354886243

output:

263687778

result:

ok 1 number(s): "263687778"

Test #13:

score: -20
Wrong Answer
time: 1191ms
memory: 319608kb

input:

91 273689959 454097881

output:

0

result:

wrong answer 1st numbers differ - expected: '114436127', found: '0'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 20
Accepted

Test #26:

score: 20
Accepted
time: 1751ms
memory: 328476kb

input:

998818 198334853 998244353

output:

153251445

result:

ok 1 number(s): "153251445"

Test #27:

score: 0
Accepted
time: 1701ms
memory: 324292kb

input:

914379 128814383 998244353

output:

477606145

result:

ok 1 number(s): "477606145"

Test #28:

score: 0
Accepted
time: 1706ms
memory: 324364kb

input:

944474 478445339 998244353

output:

174204073

result:

ok 1 number(s): "174204073"

Test #29:

score: 0
Accepted
time: 1730ms
memory: 328464kb

input:

948637 711592127 998244353

output:

178256114

result:

ok 1 number(s): "178256114"

Test #30:

score: 0
Accepted
time: 1674ms
memory: 328504kb

input:

927564 14465663 998244353

output:

315244613

result:

ok 1 number(s): "315244613"

Test #31:

score: 0
Accepted
time: 1695ms
memory: 328472kb

input:

934615 392799073 998244353

output:

892700270

result:

ok 1 number(s): "892700270"

Test #32:

score: 0
Accepted
time: 1676ms
memory: 324452kb

input:

917196 124972031 998244353

output:

782017412

result:

ok 1 number(s): "782017412"

Test #33:

score: 0
Accepted
time: 1704ms
memory: 328324kb

input:

957149 392606173 998244353

output:

159348443

result:

ok 1 number(s): "159348443"

Test #34:

score: 0
Accepted
time: 1727ms
memory: 328384kb

input:

997042 184649453 998244353

output:

464643024

result:

ok 1 number(s): "464643024"

Test #35:

score: 0
Accepted
time: 1705ms
memory: 328452kb

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:

0%