QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#311141	#8015. 鸡	zhouhuanyi	100 ✓	0ms	3848kb	C++14	1.7kb	2024-01-21 22:06:49	2024-01-21 22:06:51

Judging History

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

[2024-01-21 22:06:51]
评测

测评结果：100
用时：0ms
内存：3848kb

查看

[2024-01-21 22:06:49]
提交

answer

#include<iostream>
#include<cstdio>
#define N 3000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,m,inv3,inv6,inv12,mod,dp[N+1];
int fast_pow(int a,int b)
{
	int res=1,mul=a;
	while (b)
	{
		if (b&1) res=1ll*res*mul%mod;
		mul=1ll*mul*mul%mod,b>>=1;
	}
	return res;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
void Adder2(int &x,int d)
{
	x+=d;
	if (x<0) x+=mod;
	return;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
int main()
{
	n=read(),m=read(),mod=read(),inv3=fast_pow(3,mod-2),inv6=fast_pow(6,mod-2),inv12=fast_pow(12,mod-2);
	dp[2]=MD(MD(1ll*m*m%mod+2ll*m%mod)+1);
	dp[3]=MD(MD(MD(1ll*m*m%mod*m%mod*inv3%mod+2ll*m%mod*m%mod)+8ll*m%mod*inv3%mod)+1);
	dp[4]=MD(MD(MD(7ll*m%mod*m%mod*m%mod*inv3%mod+5ll*m%mod*m%mod)+11ll*m%mod*inv3%mod)+1);
	dp[5]=MD(MD(MD(MD(7ll*m%mod*m%mod*m%mod*m%mod*inv12%mod+17ll*m*m%mod*m%mod*inv3%mod)+89ll*m%mod*m%mod*inv12%mod)+13ll*m%mod*inv3%mod)+1);
	dp[6]=MD(MD(MD(MD(25ll*m%mod*m%mod*m%mod*m%mod*inv6%mod+38ll*m*m%mod*m%mod*inv3%mod)+71ll*m%mod*m%mod*inv6%mod)+16ll*m%mod*inv3%mod)+1);
	dp[7]=MD(MD(MD(MD(MD(5ll*m%mod*m%mod*m%mod*m%mod*m%mod*inv6%mod+37ll*m%mod*m%mod*m%mod*m%mod*inv3%mod)+133ll*m%mod*m%mod*m%mod*inv6%mod)+47ll*m%mod*m%mod*inv3%mod)+6ll*m%mod)+1);
	for (int i=8;i<=n;++i)
	{
		Adder(dp[i],2ll*dp[i-1]%mod);
		Adder(dp[i],2ll*m%mod*dp[i-2]%mod);
		Adder2(dp[i],-1ll*MD(2ll*m%mod+2)*dp[i-3]%mod);
		Adder2(dp[i],-1ll*MD2(1ll*(m+1)*(m+1)%mod-2)*dp[i-4]%mod);
		Adder(dp[i],2ll*m%mod*dp[i-5]%mod);
		Adder(dp[i],1ll*m*m%mod*dp[i-6]%mod);
	}
	printf("%d\n",dp[n]);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5

Accepted

time: 0ms

memory: 3736kb

input:

5 5 1004326439

output:

result:

ok 1 number(s): "1281"

Test #2:

score: 5

Accepted

time: 0ms

memory: 3776kb

input:

5 4 1002682123

output:

result:

ok 1 number(s): "649"

Test #3:

score: 5

Accepted

time: 0ms

memory: 3844kb

input:

287 1 1003060133

output:

328406329

result:

ok 1 number(s): "328406329"

Test #4:

score: 5

Accepted

time: 0ms

memory: 3788kb

input:

279 1 1004432189

output:

222258837

result:

ok 1 number(s): "222258837"

Test #5:

score: 5

Accepted

time: 0ms

memory: 3764kb

input:

300 1 1005912203

output:

707086810

result:

ok 1 number(s): "707086810"

Test #6:

score: 5

Accepted

time: 0ms

memory: 3704kb

input:

288 5 1003307827

output:

964512417

result:

ok 1 number(s): "964512417"

Test #7:

score: 5

Accepted

time: 0ms

memory: 3720kb

input:

281 5 1008854383

output:

755282155

result:

ok 1 number(s): "755282155"

Test #8:

score: 5

Accepted

time: 0ms

memory: 3704kb

input:

270 5 1007619367

output:

431828317

result:

ok 1 number(s): "431828317"

Test #9:

score: 5

Accepted

time: 0ms

memory: 3704kb

input:

292 5 1002449813

output:

183613546

result:

ok 1 number(s): "183613546"

Test #10:

score: 5

Accepted

time: 0ms

memory: 3788kb

input:

300 5 1005897091

output:

915308166

result:

ok 1 number(s): "915308166"

Test #11:

score: 5

Accepted

time: 0ms

memory: 3784kb

input:

45 50 1009100993

output:

940158800

result:

ok 1 number(s): "940158800"

Test #12:

score: 5

Accepted

time: 0ms

memory: 3768kb

input:

49 50 1001428049

output:

result:

ok 1 number(s): "1045902"

Test #13:

score: 5

Accepted

time: 0ms

memory: 3708kb

input:

49 50 1007851073

output:

922264698

result:

ok 1 number(s): "922264698"

Test #14:

score: 5

Accepted

time: 0ms

memory: 3704kb

input:

50 50 1005625571

output:

442192770

result:

ok 1 number(s): "442192770"

Test #15:

score: 5

Accepted

time: 0ms

memory: 3796kb

input:

290 300 1005068699

output:

484359497

result:

ok 1 number(s): "484359497"

Test #16:

score: 5

Accepted

time: 0ms

memory: 3788kb

input:

270 300 1003440637

output:

899894137

result:

ok 1 number(s): "899894137"

Test #17:

score: 5

Accepted

time: 0ms

memory: 3788kb

input:

300 300 1008561979

output:

33407754

result:

ok 1 number(s): "33407754"

Test #18:

score: 5

Accepted

time: 0ms

memory: 3792kb

input:

2991 3000 1004658859

output:

167444547

result:

ok 1 number(s): "167444547"

Test #19:

score: 5

Accepted

time: 0ms

memory: 3848kb

input:

2870 3000 1004054173

output:

860666062

result:

ok 1 number(s): "860666062"

Test #20:

score: 5

Accepted

time: 0ms

memory: 3760kb

input:

3000 3000 1009539589

output:

696222334

result:

ok 1 number(s): "696222334"