NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#173450	#37. 染色	Athene	100	2852ms	313764kb	C++	596b	2023-07-18 16:16:53	2023-07-18 16:16:54

answer

#include<bits/stdc++.h>
typedef long long ll;
using std::min;
const int N=5000+15;
int n,m;
ll p;
ll dp[N][N],sum[N][N];
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=min(i,m-1);j++)
        {
            (dp[i][j]+=dp[i-1][j-1]*(m-(j-1))%p)%=p;
            (dp[i][j]+=sum[i-1][j])%=p;
        }
        for(int j=m-1;j>=1;j--)
        {
            sum[i][j]=sum[i][j+1]+dp[i][j]%p;
        }
    }
    ll ans=0;
    for(int i=1;i<m;i++)(ans+=dp[n][i])%=p;
    printf("%lld\n",ans);
    return 0;
}

源文件, 语言: C++

详细

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

Test #1:

score: 5

Accepted

time: 0ms

memory: 1240kb

input:

5 2 6

output:

result:

ok 1 number(s): "2"

Test #2:

score: 5

Accepted

time: 0ms

memory: 1260kb

input:

8 8 562455908

output:

16736896

result:

ok 1 number(s): "16736896"

Test #3:

score: 5

Accepted

time: 4ms

memory: 16892kb

input:

1942 7 873185963

output:

41441893

result:

ok 1 number(s): "41441893"

Test #4:

score: 5

Accepted

time: 0ms

memory: 17696kb

input:

2030 10 187301366

output:

171496026

result:

ok 1 number(s): "171496026"

Test #5:

score: 5

Accepted

time: 8ms

memory: 38848kb

input:

4643 9 998244353

output:

583546139

result:

ok 1 number(s): "583546139"

Test #6:

score: 5

Accepted

time: 86ms

memory: 65792kb

input:

1447 3969 998244353

output:

669602806

result:

ok 1 number(s): "669602806"

Test #7:

score: 5

Accepted

time: 0ms

memory: 3580kb

input:

226 212 998244352

output:

503316480

result:

ok 1 number(s): "503316480"

Test #8:

score: 5

Accepted

time: 5ms

memory: 4628kb

input:

300 292 779230672

output:

95153840

result:

ok 1 number(s): "95153840"

Test #9:

score: 5

Accepted

time: 0ms

memory: 4104kb

input:

269 228 479932618

output:

244481530

result:

ok 1 number(s): "244481530"

Test #10:

score: 5

Accepted

time: 0ms

memory: 3252kb

input:

216 112 207794912

output:

145540448

result:

ok 1 number(s): "145540448"

Test #11:

score: 5

Accepted

time: 0ms

memory: 4456kb

input:

291 261 37264436

output:

28883269

result:

ok 1 number(s): "28883269"

Test #12:

score: 5

Accepted

time: 4ms

memory: 4132kb

input:

273 218 960539553

output:

718739009

result:

ok 1 number(s): "718739009"

Test #13:

score: 5

Accepted

time: 209ms

memory: 112400kb

input:

2991 2318 704783019

output:

517763339

result:

ok 1 number(s): "517763339"

Test #14:

score: 5

Accepted

time: 133ms

memory: 88408kb

input:

4413 790 693631006

output:

634441922

result:

ok 1 number(s): "634441922"

Test #15:

score: 5

Accepted

time: 615ms

memory: 296988kb

input:

4786 4581 2

output:

result:

ok 1 number(s): "1"

Test #16:

score: 5

Accepted

time: 651ms

memory: 306636kb

input:

4953 4424 876277826

output:

746769658

result:

ok 1 number(s): "746769658"

Test #17:

score: 5

Accepted

time: 12ms

memory: 43272kb

input:

4921 37 699201223

output:

206663263

result:

ok 1 number(s): "206663263"

Test #18:

score: 5

Accepted

time: 187ms

memory: 114648kb

input:

4991 994 533908193

output:

86765287

result:

ok 1 number(s): "86765287"

Test #19:

score: 5

Accepted

time: 710ms

memory: 313764kb

input:

5000 5000 640462742

output:

518214138

result:

ok 1 number(s): "518214138"

Test #20:

score: 5

Accepted

time: 228ms

memory: 114096kb

input:

4935 1005 961254358

output:

202283451

result:

ok 1 number(s): "202283451"

Extra Test:

score: 0

Extra Test Passed