ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#156553 | #37. 染色 | The_Nobody | 100 | 2832ms | 216120kb | C++ | 1.3kb | 2022-08-08 07:47:57 | 2022-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