UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#156553#37. 染色The_Nobody1002832ms216120kbC++1.3kb2022-08-08 07:47:572022-08-08 07:47:57

answer

#include<bits/stdc++.h>
#define ll long long
#define Il inline
#define mem(u,v) memset(u,v,sizeof(u))
#define rep(i,a,b) for(int i=(a),KKK##i=(b);i<=KKK##i;i++)
#define drep(i,a,b) for(int i=(a),KKK##i=(b);i>=KKK##i;i--)
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define _go(u) for(int i=Head[u],v=E[i].to;i;i=E[i].nxt,v=E[i].to)
#define writesp(x) write(x),putchar(' ')
#define writeln(x) write(x),puts("")
//#define getchar nc
inline char nc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
using namespace std;
Il ll read(){ll sum=0,f=0;char ch=getchar();for(;!isdigit(ch);ch=getchar())f|=(ch=='-');for(;isdigit(ch);ch=getchar())sum=((sum<<1)+(sum<<3)+(ch^48));return f?-sum:sum;}
void write(const ll x){if(x<0){putchar('-');write(-x);return;}if(x>9)write(x/10);putchar(x%10+'0');}
char getc(){char ch=getchar();while(ch!='0'&&ch!='1')ch=getchar();return ch^48;}
#define N 5500
ll n,m,p,f[N][N],sum[N],ans;
void inc(ll &a,ll b){a+=b;if(a>=p)a-=p;}
int main(){
	n=read();m=read();p=read();
	f[0][0]=1;
	rep(i,1,n){
		rep(j,1,m-1)f[i][j]=f[i-1][j-1]*(m-j+1)%p,inc(f[i][j],sum[j]);
		drep(j,m-1,1)sum[j]=(sum[j+1]+f[i][j])%p;
	}
	rep(j,1,m-1)inc(ans,f[n][j]);
	writeln(ans);
}

详细

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

Test #1:

score: 5
Accepted
time: 0ms
memory: 1156kb

input:

5 2 6

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 5
Accepted
time: 0ms
memory: 1164kb

input:

8 8 562455908

output:

16736896

result:

ok 1 number(s): "16736896"

Test #3:

score: 5
Accepted
time: 3ms
memory: 83244kb

input:

1942 7 873185963

output:

41441893

result:

ok 1 number(s): "41441893"

Test #4:

score: 5
Accepted
time: 0ms
memory: 87340kb

input:

2030 10 187301366

output:

171496026

result:

ok 1 number(s): "171496026"

Test #5:

score: 5
Accepted
time: 0ms
memory: 199984kb

input:

4643 9 998244353

output:

583546139

result:

ok 1 number(s): "583546139"

Test #6:

score: 5
Accepted
time: 163ms
memory: 64208kb

input:

1447 3969 998244353

output:

669602806

result:

ok 1 number(s): "669602806"

Test #7:

score: 5
Accepted
time: 0ms
memory: 9588kb

input:

226 212 998244352

output:

503316480

result:

ok 1 number(s): "503316480"

Test #8:

score: 5
Accepted
time: 0ms
memory: 13720kb

input:

300 292 779230672

output:

95153840

result:

ok 1 number(s): "95153840"

Test #9:

score: 5
Accepted
time: 3ms
memory: 11636kb

input:

269 228 479932618

output:

244481530

result:

ok 1 number(s): "244481530"

Test #10:

score: 5
Accepted
time: 0ms
memory: 9548kb

input:

216 112 207794912

output:

145540448

result:

ok 1 number(s): "145540448"

Test #11:

score: 5
Accepted
time: 2ms
memory: 13700kb

input:

291 261 37264436

output:

28883269

result:

ok 1 number(s): "28883269"

Test #12:

score: 5
Accepted
time: 0ms
memory: 11632kb

input:

273 218 960539553

output:

718739009

result:

ok 1 number(s): "718739009"

Test #13:

score: 5
Accepted
time: 213ms
memory: 129148kb

input:

2991 2318 704783019

output:

517763339

result:

ok 1 number(s): "517763339"

Test #14:

score: 5
Accepted
time: 113ms
memory: 190028kb

input:

4413 790 693631006

output:

634441922

result:

ok 1 number(s): "634441922"

Test #15:

score: 5
Accepted
time: 573ms
memory: 207788kb

input:

4786 4581 2

output:

1

result:

ok 1 number(s): "1"

Test #16:

score: 5
Accepted
time: 682ms
memory: 213872kb

input:

4953 4424 876277826

output:

746769658

result:

ok 1 number(s): "746769658"

Test #17:

score: 5
Accepted
time: 8ms
memory: 212284kb

input:

4921 37 699201223

output:

206663263

result:

ok 1 number(s): "206663263"

Test #18:

score: 5
Accepted
time: 186ms
memory: 214672kb

input:

4991 994 533908193

output:

86765287

result:

ok 1 number(s): "86765287"

Test #19:

score: 5
Accepted
time: 728ms
memory: 216120kb

input:

5000 5000 640462742

output:

518214138

result:

ok 1 number(s): "518214138"

Test #20:

score: 5
Accepted
time: 158ms
memory: 212632kb

input:

4935 1005 961254358

output:

202283451

result:

ok 1 number(s): "202283451"

Extra Test:

score: 0
Extra Test Passed