QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #311141 | #8015. 鸡 | zhouhuanyi | 100 ✓ | 0ms | 3848kb | C++14 | 1.7kb | 2024-01-21 22:06:49 | 2024-01-21 22:06:51 |
Judging History
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;
}
详细
Test #1:
score: 5
Accepted
time: 0ms
memory: 3736kb
input:
5 5 1004326439
output:
1281
result:
ok 1 number(s): "1281"
Test #2:
score: 5
Accepted
time: 0ms
memory: 3776kb
input:
5 4 1002682123
output:
649
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:
1045902
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"