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
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;
}
详细
Test #1:
score: 5
Accepted
time: 0ms
memory: 3884kb
input:
5 5 1004326439
output:
1281
result:
ok 1 number(s): "1281"
Test #2:
score: 5
Accepted
time: 1ms
memory: 3864kb
input:
5 4 1002682123
output:
649
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:
1045902
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"