QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#308078	#8015. 鸡	by_chance	100 ✓	81ms	3676kb	C++14	1012b	2024-01-19 15:23:30	2024-01-19 15:23:32

Judging History

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

[2024-01-19 15:23:32]
评测

测评结果：100
用时：81ms
内存：3676kb

查看

[2024-01-19 15:23:30]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,m,P,f[N],f1[N],g[N],h[N],x[N],tot,cnt,ans;
int main(){
    cin>>n>>m>>P;f[0]=cnt=1;
    for(int i=1;i<=n;i++)f[i]=(f[i-1]+1ll*f[max(i-2,0)]*m)%P;
    for(int i=2;i<n;i++)tot=(tot+1ll*f[i-2]*f[n-i-1])%P;
    tot=(tot+2ll*f[n-2])%P;ans=1ll*m*(m-1)/2*tot%P;
    for(int i=0;i<=n;i++)f1[i]=f[max(i-1,0)];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n-i;j++)
            g[i+j]=(g[i+j]+1ll*f1[i]*f1[j])%P,
            h[i+j]=(h[i+j]+1ll*f[i]*f[j])%P;
    for(int i=1;i<m;i++){
        tot=0;
        for(int j=1;j<=n;j+=2){
            if(j==n){++tot;break;}
            if(j+2<=n)tot=(tot+2ll*f1[n-j-2]*(m-i))%P;
            if(j+4<=n)tot=(tot+1ll*g[n-j-4]*(m-i)*(m-i))%P;
        }
        ans=(ans+P-1ll*tot*(m-i)%P)%P;
    }
    for(int i=4;i<=n;i++)cnt=(cnt+1ll*(P+(i&1?-1:1))*h[n-i])%P;
    for(int i=3;i<n;i+=2)cnt=(cnt+2ll*f1[n-i-1]*m)%P;
    ans=(ans+f[n]+1ll*cnt*m)%P;
    cout<<ans<<endl;
    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 5

Accepted

time: 0ms

memory: 3664kb

input:

5 5 1004326439

output:

result:

ok 1 number(s): "1281"

Test #2:

score: 5

Accepted

time: 0ms

memory: 3656kb

input:

5 4 1002682123

output:

result:

ok 1 number(s): "649"

Test #3:

score: 5

Accepted

time: 1ms

memory: 3496kb

input:

287 1 1003060133

output:

328406329

result:

ok 1 number(s): "328406329"

Test #4:

score: 5

Accepted

time: 1ms

memory: 3536kb

input:

279 1 1004432189

output:

222258837

result:

ok 1 number(s): "222258837"

Test #5:

score: 5

Accepted

time: 1ms

memory: 3616kb

input:

300 1 1005912203

output:

707086810

result:

ok 1 number(s): "707086810"

Test #6:

score: 5

Accepted

time: 1ms

memory: 3524kb

input:

288 5 1003307827

output:

964512417

result:

ok 1 number(s): "964512417"

Test #7:

score: 5

Accepted

time: 1ms

memory: 3676kb

input:

281 5 1008854383

output:

755282155

result:

ok 1 number(s): "755282155"

Test #8:

score: 5

Accepted

time: 1ms

memory: 3604kb

input:

270 5 1007619367

output:

431828317

result:

ok 1 number(s): "431828317"

Test #9:

score: 5

Accepted

time: 1ms

memory: 3664kb

input:

292 5 1002449813

output:

183613546

result:

ok 1 number(s): "183613546"

Test #10:

score: 5

Accepted

time: 1ms

memory: 3592kb

input:

300 5 1005897091

output:

915308166

result:

ok 1 number(s): "915308166"

Test #11:

score: 5

Accepted

time: 0ms

memory: 3608kb

input:

45 50 1009100993

output:

940158800

result:

ok 1 number(s): "940158800"

Test #12:

score: 5

Accepted

time: 0ms

memory: 3576kb

input:

49 50 1001428049

output:

result:

ok 1 number(s): "1045902"

Test #13:

score: 5

Accepted

time: 0ms

memory: 3660kb

input:

49 50 1007851073

output:

922264698

result:

ok 1 number(s): "922264698"

Test #14:

score: 5

Accepted

time: 0ms

memory: 3584kb

input:

50 50 1005625571

output:

442192770

result:

ok 1 number(s): "442192770"

Test #15:

score: 5

Accepted

time: 1ms

memory: 3528kb

input:

290 300 1005068699

output:

484359497

result:

ok 1 number(s): "484359497"

Test #16:

score: 5

Accepted

time: 1ms

memory: 3500kb

input:

270 300 1003440637

output:

899894137

result:

ok 1 number(s): "899894137"

Test #17:

score: 5

Accepted

time: 1ms

memory: 3612kb

input:

300 300 1008561979

output:

33407754

result:

ok 1 number(s): "33407754"

Test #18:

score: 5

Accepted

time: 80ms

memory: 3560kb

input:

2991 3000 1004658859

output:

167444547

result:

ok 1 number(s): "167444547"

Test #19:

score: 5

Accepted

time: 76ms

memory: 3552kb

input:

2870 3000 1004054173

output:

860666062

result:

ok 1 number(s): "860666062"

Test #20:

score: 5

Accepted

time: 81ms

memory: 3556kb

input:

3000 3000 1009539589

output:

696222334

result:

ok 1 number(s): "696222334"