NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#211789	#37. 染色	yiweixxs	55	2977ms	117904kb	C++	1.0kb	2024-10-03 09:45:10	2024-10-03 09:45:11

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<list>
#include<map>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
long long n,m,P;
long long f[5005][5005];//F[i][j]:f[i][j]-f[i][j-1]
int main(){
    cin>>n>>m>>P;
    f[1][1]=m,f[1][2]=-m;
    for(int i=1;i<=n;i++){
        long long sum=0;
        for(int j=1;j<min((long long)(i+1),m);j++){
            sum+=f[i][j];
            sum%=P;
            f[i][j]=sum;
        }
        for(int j=1;j<min((long long)(i+1),m);j++){
            f[i+1][1]+=f[i][j];
            f[i+1][j+1]-=f[i][j];
            f[i+1][1]%=P;
            f[i+1][j+1]%=P;
            if(j<m-1){
                f[i+1][j+1]+=f[i][j]*(m-j);
                f[i+1][j+2]-=f[i][j]*(m-j);
            }
            f[i+1][j+2]%=P;
            f[i+1][j+1]%=P;
        }
    }
    long long ans=0;
    for(int i=1;i<m;i++){
        ans+=f[n][i];
        ans%=P;
    }
    cout<<ans;
    return 0;
}

源文件, 语言: C++

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 5

Accepted

time: 1ms

memory: 1224kb

input:

5 2 6

output:

result:

ok 1 number(s): "2"

Test #2:

score: 5

Accepted

time: 0ms

memory: 1232kb

input:

8 8 562455908

output:

16736896

result:

ok 1 number(s): "16736896"

Test #3:

score: 5

Accepted

time: 0ms

memory: 9080kb

input:

1942 7 873185963

output:

41441893

result:

ok 1 number(s): "41441893"

Test #4:

score: 0

Wrong Answer

time: 0ms

memory: 9484kb

input:

2030 10 187301366

output:

-15805340

result:

wrong answer 1st numbers differ - expected: '171496026', found: '-15805340'

Test #5:

score: 5

Accepted

time: 3ms

memory: 20100kb

input:

4643 9 998244353

output:

583546139

result:

ok 1 number(s): "583546139"

Test #6:

score: 0

Wrong Answer

time: 54ms

memory: 15188kb

input:

1447 3969 998244353

output:

250121146

result:

wrong answer 1st numbers differ - expected: '669602806', found: '250121146'

Test #7:

score: 0

Wrong Answer

time: 3ms

memory: 2308kb

input:

226 212 998244352

output:

-494927872

result:

wrong answer 1st numbers differ - expected: '503316480', found: '-494927872'

Test #8:

score: 5

Accepted

time: 4ms

memory: 2756kb

input:

300 292 779230672

output:

95153840

result:

ok 1 number(s): "95153840"

Test #9:

score: 0

Wrong Answer

time: 0ms

memory: 2556kb

input:

269 228 479932618

output:

-235451088

result:

wrong answer 1st numbers differ - expected: '244481530', found: '-235451088'

Test #10:

score: 0

Wrong Answer

time: 0ms

memory: 2212kb

input:

216 112 207794912

output:

-62254464

result:

wrong answer 1st numbers differ - expected: '145540448', found: '-62254464'

Test #11:

score: 5

Accepted

time: 0ms

memory: 2700kb

input:

291 261 37264436

output:

28883269

result:

ok 1 number(s): "28883269"

Test #12:

score: 0

Wrong Answer

time: 3ms

memory: 2576kb

input:

273 218 960539553

output:

-241800544

result:

wrong answer 1st numbers differ - expected: '718739009', found: '-241800544'

Test #13:

score: 5

Accepted

time: 235ms

memory: 46364kb

input:

2991 2318 704783019

output:

517763339

result:

ok 1 number(s): "517763339"

Test #14:

score: 5

Accepted

time: 182ms

memory: 43664kb

input:

4413 790 693631006

output:

634441922

result:

ok 1 number(s): "634441922"

Test #15:

score: 5

Accepted

time: 639ms

memory: 109528kb

input:

4786 4581 2

output:

result:

ok 1 number(s): "1"

Test #16:

score: 5

Accepted

time: 667ms

memory: 115792kb

input:

4953 4424 876277826

output:

746769658

result:

ok 1 number(s): "746769658"

Test #17:

score: 0

Wrong Answer

time: 8ms

memory: 22308kb

input:

4921 37 699201223

output:

-492537960

result:

wrong answer 1st numbers differ - expected: '206663263', found: '-492537960'

Test #18:

score: 0

Wrong Answer

time: 249ms

memory: 56076kb

input:

4991 994 533908193

output:

-447142906

result:

wrong answer 1st numbers differ - expected: '86765287', found: '-447142906'

Test #19:

score: 0

Wrong Answer

time: 683ms

memory: 117904kb

input:

5000 5000 640462742

output:

-122248604

result:

wrong answer 1st numbers differ - expected: '518214138', found: '-122248604'

Test #20:

score: 5

Accepted

time: 246ms

memory: 55752kb

input:

4935 1005 961254358

output:

202283451

result:

ok 1 number(s): "202283451"