QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#430730 | #8015. 鸡 | Williamxzh# | 15 | 306ms | 55056kb | C++23 | 2.3kb | 2024-06-04 12:06:40 | 2024-06-04 12:06:40 |
Judging History
answer
#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
const int N=302;
int n,m,mod,f[N][2][N/2][N/2],ans;
il void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
il int calc(int l,int r){
r=min(r,n);
if(l>1 && r<n) return max(0,(r-l+1)/2-1);
else return max(0,(r-l)/2);
}
int a[N],b[N],g[N][2];
map<vector<int>,int> mp;
vector<int> e;
il void ck(){
e.clear();
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
g[j][0]=max(g[j-1][0],g[j-1][1]);
g[j][1]=g[j-1][0]+(i!=j)*a[j];
}e.push_back(max(g[n][0],g[n][1]));
}mp[e]=1;
}
void dfs(int x){
if(x>n){ck();return ;}
for(int i=0;i<=m;++i) a[x]=i,dfs(x+1);
}
int main(){
//freopen("c1.in","r",stdin);
scanf("%d%d%lld",&n,&m,&mod);
if(n<=6 && m<=6){
dfs(1);
printf("%d",mp.size());
exit(0);
}
ans=(n/2ll)+1ll;
f[1][0][0][0]=f[1][1][1][0]=1ll;
for(int i=2;i<=n;++i){
//case 1: a[i]=0
//(1):a[1]...a[i]=0
f[i][0][0][i/2]=1ll;
//(2) exist 1:find the last 1
for(int j=1;j<=i-1;++j)
for(int k=1;k*2<=j+1;++k)
for(int l=0;l+k<=j && l*2<=j;++l)
add(f[i][0][k][l+calc(j+1,i+1)],f[j][1][k][l]);
// if(i==4 && j==1 && k==1 && l==0) {printf("*** %lld %lld\n",f[j][1][k][l],f[i][0][k][l+calc(]);}
//case 2: a[i]=1
//(1) for all j<i j=i(mod 2),a[j]=1
f[i][1][(i+1)/2][0]=1ll;
//(2) exist j<i,j=i(mod 2) ,a[j]=0
//j:the last 1 such that (j+1) ~ i = 1010...101
for(int j=i-2;j>0;j-=2)
for(int k=0;k*2<=j;++k)
for(int l=0;l+k<=j && l*2<=j;++l)
add(f[i][1][k+(i-j)/2][l],f[j][0][k][l]);
}
for(int mi=0;mi<=(n/2);++mi)
for(int i=1;i<n && i*2<=n+1;++i){
if(i-1>mi) break;
for(int j=0;i+j<=n && j*2<=n;++j){
if(i+j<mi+1) continue;
add(ans,f[n][0][i][j]),add(ans,f[n][1][i][j]);
//printf("%d %d %d %d %lld\n",n,0,i,j,f[n][0][i][j]);
//printf("%d %d %d %d %lld\n",n,1,i,j,f[n][1][i][j]);
}
}
printf("%d",ans);
return 0;
}
/*
1,4,6,12,19,35,58,102,172,296,501
2,2,3,3,4,4,5,5,6,6
0,2,3,9,15,31,53,97,290,495
*/
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3884kb
input:
5 5 1004326439
output:
1
result:
wrong answer 1st numbers differ - expected: '1281', found: '1'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 3796kb
input:
5 4 1002682123
output:
1
result:
wrong answer 1st numbers differ - expected: '649', found: '1'
Test #3:
score: 5
Accepted
time: 250ms
memory: 51348kb
input:
287 1 1003060133
output:
328406329
result:
ok 1 number(s): "328406329"
Test #4:
score: 5
Accepted
time: 223ms
memory: 52224kb
input:
279 1 1004432189
output:
222258837
result:
ok 1 number(s): "222258837"
Test #5:
score: 5
Accepted
time: 295ms
memory: 49544kb
input:
300 1 1005912203
output:
707086810
result:
ok 1 number(s): "707086810"
Test #6:
score: 0
Wrong Answer
time: 254ms
memory: 52560kb
input:
288 5 1003307827
output:
302624836
result:
wrong answer 1st numbers differ - expected: '964512417', found: '302624836'
Test #7:
score: 0
Wrong Answer
time: 220ms
memory: 47848kb
input:
281 5 1008854383
output:
471801009
result:
wrong answer 1st numbers differ - expected: '755282155', found: '471801009'
Test #8:
score: 0
Wrong Answer
time: 201ms
memory: 52148kb
input:
270 5 1007619367
output:
330443256
result:
wrong answer 1st numbers differ - expected: '431828317', found: '330443256'
Test #9:
score: 0
Wrong Answer
time: 273ms
memory: 48800kb
input:
292 5 1002449813
output:
530615262
result:
wrong answer 1st numbers differ - expected: '183613546', found: '530615262'
Test #10:
score: 0
Wrong Answer
time: 306ms
memory: 55056kb
input:
300 5 1005897091
output:
85483324
result:
wrong answer 1st numbers differ - expected: '915308166', found: '85483324'
Test #11:
score: 0
Wrong Answer
time: 2ms
memory: 12116kb
input:
45 50 1009100993
output:
920710816
result:
wrong answer 1st numbers differ - expected: '940158800', found: '920710816'
Test #12:
score: 0
Wrong Answer
time: 2ms
memory: 10380kb
input:
49 50 1001428049
output:
395802997
result:
wrong answer 1st numbers differ - expected: '1045902', found: '395802997'
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 12068kb
input:
49 50 1007851073
output:
600776070
result:
wrong answer 1st numbers differ - expected: '922264698', found: '600776070'
Test #14:
score: 0
Wrong Answer
time: 0ms
memory: 13936kb
input:
50 50 1005625571
output:
509017421
result:
wrong answer 1st numbers differ - expected: '442192770', found: '509017421'
Test #15:
score: 0
Wrong Answer
time: 264ms
memory: 53516kb
input:
290 300 1005068699
output:
357713920
result:
wrong answer 1st numbers differ - expected: '484359497', found: '357713920'
Test #16:
score: 0
Wrong Answer
time: 193ms
memory: 52424kb
input:
270 300 1003440637
output:
827092018
result:
wrong answer 1st numbers differ - expected: '899894137', found: '827092018'
Test #17:
score: 0
Wrong Answer
time: 287ms
memory: 54528kb
input:
300 300 1008561979
output:
487732214
result:
wrong answer 1st numbers differ - expected: '33407754', found: '487732214'
Test #18:
score: 0
Runtime Error
input:
2991 3000 1004658859
output:
result:
Test #19:
score: 0
Runtime Error
input:
2870 3000 1004054173
output:
result:
Test #20:
score: 0
Runtime Error
input:
3000 3000 1009539589