QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#308480 | #8015. 鸡 | ucup-team1004 | 100 ✓ | 440ms | 144952kb | C++14 | 1.5kb | 2024-01-20 07:04:12 | 2024-01-20 07:04:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) (a).begin(),(a).end()
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
out<<'[';
for(T x:a)out<<x<<',';
return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int N=3e3+10;
int n,m,mod;
struct zj{
int cnt,sum;
}f[N][N],g[N][N];
#ifdef DEBUG
ostream& operator << (ostream &out,zj a){
return out<<'('<<a.cnt<<','<<a.sum<<')';
}
#endif
void add(zj &a,const zj &b,const int &w){
(a.cnt+=b.cnt)%=mod;
a.sum=(a.sum+b.sum+1ll*b.cnt*w)%mod;
}
int main(){
cin>>n>>m>>mod;
for(int i=0;i<=m;i++)f[0][i]={1,1};
for(int i=0;i<n;i++){
zj t={0,0};
for(int j=m;j>=1;j--){
add(t,f[i][j],m-j);
add(t,g[i][j],0);
add(f[i+2][j-1],t,0);
}
t={0,0};
for(int j=1;j<m;j++){
add(t,f[i][j],0);
add(t,g[i][j],0);
add(g[i+2][j+1],t,m-j-1);
}
for(int j=1;j<=m;j++){
add(f[i+2][j],f[i][j],m-j);
add(g[i+2][j],g[i][j],m-j);
}
for(int j=0;j<=m;j++){
add(g[i+1][j],f[i][0],m-j);
}
for(int j=1;j<=m;j++){
add(g[i+2][j],f[i][0],m-j);
}
add(f[i+1][0],g[i][0],0);
}
zj ans={0,0};
for(int i=1;i<=m;i++){
add(ans,f[n-1][i],0);
add(ans,g[n-1][i],0);
}
add(ans,f[n][0],0);
add(ans,f[n-1][0],0);
cout<<ans.sum<<endl;
return 0;
}
详细
Test #1:
score: 5
Accepted
time: 1ms
memory: 5660kb
input:
5 5 1004326439
output:
1281
result:
ok 1 number(s): "1281"
Test #2:
score: 5
Accepted
time: 1ms
memory: 5668kb
input:
5 4 1002682123
output:
649
result:
ok 1 number(s): "649"
Test #3:
score: 5
Accepted
time: 2ms
memory: 7772kb
input:
287 1 1003060133
output:
328406329
result:
ok 1 number(s): "328406329"
Test #4:
score: 5
Accepted
time: 0ms
memory: 7880kb
input:
279 1 1004432189
output:
222258837
result:
ok 1 number(s): "222258837"
Test #5:
score: 5
Accepted
time: 0ms
memory: 7852kb
input:
300 1 1005912203
output:
707086810
result:
ok 1 number(s): "707086810"
Test #6:
score: 5
Accepted
time: 0ms
memory: 8032kb
input:
288 5 1003307827
output:
964512417
result:
ok 1 number(s): "964512417"
Test #7:
score: 5
Accepted
time: 1ms
memory: 7680kb
input:
281 5 1008854383
output:
755282155
result:
ok 1 number(s): "755282155"
Test #8:
score: 5
Accepted
time: 0ms
memory: 7664kb
input:
270 5 1007619367
output:
431828317
result:
ok 1 number(s): "431828317"
Test #9:
score: 5
Accepted
time: 0ms
memory: 7900kb
input:
292 5 1002449813
output:
183613546
result:
ok 1 number(s): "183613546"
Test #10:
score: 5
Accepted
time: 2ms
memory: 8128kb
input:
300 5 1005897091
output:
915308166
result:
ok 1 number(s): "915308166"
Test #11:
score: 5
Accepted
time: 1ms
memory: 5860kb
input:
45 50 1009100993
output:
940158800
result:
ok 1 number(s): "940158800"
Test #12:
score: 5
Accepted
time: 1ms
memory: 5956kb
input:
49 50 1001428049
output:
1045902
result:
ok 1 number(s): "1045902"
Test #13:
score: 5
Accepted
time: 1ms
memory: 5780kb
input:
49 50 1007851073
output:
922264698
result:
ok 1 number(s): "922264698"
Test #14:
score: 5
Accepted
time: 1ms
memory: 5820kb
input:
50 50 1005625571
output:
442192770
result:
ok 1 number(s): "442192770"
Test #15:
score: 5
Accepted
time: 0ms
memory: 9032kb
input:
290 300 1005068699
output:
484359497
result:
ok 1 number(s): "484359497"
Test #16:
score: 5
Accepted
time: 0ms
memory: 8736kb
input:
270 300 1003440637
output:
899894137
result:
ok 1 number(s): "899894137"
Test #17:
score: 5
Accepted
time: 7ms
memory: 9416kb
input:
300 300 1008561979
output:
33407754
result:
ok 1 number(s): "33407754"
Test #18:
score: 5
Accepted
time: 440ms
memory: 144668kb
input:
2991 3000 1004658859
output:
167444547
result:
ok 1 number(s): "167444547"
Test #19:
score: 5
Accepted
time: 435ms
memory: 139600kb
input:
2870 3000 1004054173
output:
860666062
result:
ok 1 number(s): "860666062"
Test #20:
score: 5
Accepted
time: 437ms
memory: 144952kb
input:
3000 3000 1009539589
output:
696222334
result:
ok 1 number(s): "696222334"