QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#309241	#8015. 鸡	C1942huangjiaxu	100 ✓	70ms	3952kb	C++14	896b	2024-01-20 15:58:06	2024-01-20 15:58:06

Judging History

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

[2024-01-20 15:58:06]
评测

测评结果：100
用时：70ms
内存：3952kb

查看

[2024-01-20 15:58:06]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,m,P,f[N],F[N],g[N],ans,sum;
int main(){
	scanf("%d%d%d",&n,&m,&P);
	f[0]=F[0]=1,f[1]=m+1;
	for(int i=2;i<=n;++i)f[i]=(1ll*m*f[i-2]+f[i-1])%P;
	for(int i=1;i<=n;++i)F[i]=f[i-1];
	for(int i=0;i<=n;++i)for(int j=0;i+j<=n;++j)g[i+j]=(1ll*F[i]*F[j]+g[i+j])%P;
	ans=f[n],sum=2*f[n-2]%P;
	for(int i=2;i<n;++i)sum=(sum+1ll*f[i-2]*f[n-i-1])%P;
	for(int i=1;i<m;++i){
		int v=m-i,cnt=0;
		ans=(ans+1ll*v*sum)%P;
		for(int j=1;j*2-1<=n;++j){
			int u=j*2-1;
			if(u==n)++cnt;
			else{
				if(u+4<=n)cnt=(cnt+1ll*g[n-u-4]*v%P*v)%P;
				if(u+2<=n)cnt=(cnt+1ll*F[n-u-2]*v*2)%P;
			}
		}
		ans=(ans+1ll*(P-cnt)*v)%P;
	}
	sum=n/2;
	for(int i=4;i<n-1;++i)sum=(sum+1ll*(i-2)/2*g[n-i-2]%P*m%P*m)%P;
	for(int i=3;i<n;++i)sum=(sum+1ll*(i-1)/2*F[n-i-1]*m*2)%P;
	ans=(ans+1ll*sum*m)%P;
	printf("%d\n",ans);
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 5

Accepted

time: 0ms

memory: 3884kb

input:

5 5 1004326439

output:

result:

ok 1 number(s): "1281"

Test #2:

score: 5

Accepted

time: 1ms

memory: 3864kb

input:

5 4 1002682123

output:

result:

ok 1 number(s): "649"

Test #3:

score: 5

Accepted

time: 1ms

memory: 3944kb

input:

287 1 1003060133

output:

328406329

result:

ok 1 number(s): "328406329"

Test #4:

score: 5

Accepted

time: 1ms

memory: 3884kb

input:

279 1 1004432189

output:

222258837

result:

ok 1 number(s): "222258837"

Test #5:

score: 5

Accepted

time: 1ms

memory: 3876kb

input:

300 1 1005912203

output:

707086810

result:

ok 1 number(s): "707086810"

Test #6:

score: 5

Accepted

time: 1ms

memory: 3836kb

input:

288 5 1003307827

output:

964512417

result:

ok 1 number(s): "964512417"

Test #7:

score: 5

Accepted

time: 1ms

memory: 3756kb

input:

281 5 1008854383

output:

755282155

result:

ok 1 number(s): "755282155"

Test #8:

score: 5

Accepted

time: 1ms

memory: 3876kb

input:

270 5 1007619367

output:

431828317

result:

ok 1 number(s): "431828317"

Test #9:

score: 5

Accepted

time: 1ms

memory: 3796kb

input:

292 5 1002449813

output:

183613546

result:

ok 1 number(s): "183613546"

Test #10:

score: 5

Accepted

time: 1ms

memory: 3752kb

input:

300 5 1005897091

output:

915308166

result:

ok 1 number(s): "915308166"

Test #11:

score: 5

Accepted

time: 0ms

memory: 3788kb

input:

45 50 1009100993

output:

940158800

result:

ok 1 number(s): "940158800"

Test #12:

score: 5

Accepted

time: 0ms

memory: 3800kb

input:

49 50 1001428049

output:

result:

ok 1 number(s): "1045902"

Test #13:

score: 5

Accepted

time: 0ms

memory: 3872kb

input:

49 50 1007851073

output:

922264698

result:

ok 1 number(s): "922264698"

Test #14:

score: 5

Accepted

time: 0ms

memory: 3876kb

input:

50 50 1005625571

output:

442192770

result:

ok 1 number(s): "442192770"

Test #15:

score: 5

Accepted

time: 0ms

memory: 3888kb

input:

290 300 1005068699

output:

484359497

result:

ok 1 number(s): "484359497"

Test #16:

score: 5

Accepted

time: 1ms

memory: 3796kb

input:

270 300 1003440637

output:

899894137

result:

ok 1 number(s): "899894137"

Test #17:

score: 5

Accepted

time: 1ms

memory: 3748kb

input:

300 300 1008561979

output:

33407754

result:

ok 1 number(s): "33407754"

Test #18:

score: 5

Accepted

time: 70ms

memory: 3888kb

input:

2991 3000 1004658859

output:

167444547

result:

ok 1 number(s): "167444547"

Test #19:

score: 5

Accepted

time: 62ms

memory: 3952kb

input:

2870 3000 1004054173

output:

860666062

result:

ok 1 number(s): "860666062"

Test #20:

score: 5

Accepted

time: 70ms

memory: 3816kb

input:

3000 3000 1009539589

output:

696222334

result:

ok 1 number(s): "696222334"