QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#430758#8015. 鸡Williamxzh15 280ms55792kbC++232.3kb2024-06-04 13:58:222024-06-04 13:58:23

Judging History

你现在查看的是最新测评结果

  • [2024-06-04 13:58:23]
  • 评测
  • 测评结果:15
  • 用时:280ms
  • 内存:55792kb
  • [2024-06-04 13:58:22]
  • 提交

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: 0ms
memory: 3800kb

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: 4064kb

input:

5 4 1002682123

output:

1

result:

wrong answer 1st numbers differ - expected: '649', found: '1'

Test #3:

score: 5
Accepted
time: 227ms
memory: 51108kb

input:

287 1 1003060133

output:

328406329

result:

ok 1 number(s): "328406329"

Test #4:

score: 5
Accepted
time: 214ms
memory: 46060kb

input:

279 1 1004432189

output:

222258837

result:

ok 1 number(s): "222258837"

Test #5:

score: 5
Accepted
time: 274ms
memory: 55792kb

input:

300 1 1005912203

output:

707086810

result:

ok 1 number(s): "707086810"

Test #6:

score: 0
Wrong Answer
time: 244ms
memory: 50060kb

input:

288 5 1003307827

output:

302624836

result:

wrong answer 1st numbers differ - expected: '964512417', found: '302624836'

Test #7:

score: 0
Wrong Answer
time: 207ms
memory: 51584kb

input:

281 5 1008854383

output:

471801009

result:

wrong answer 1st numbers differ - expected: '755282155', found: '471801009'

Test #8:

score: 0
Wrong Answer
time: 186ms
memory: 45732kb

input:

270 5 1007619367

output:

330443256

result:

wrong answer 1st numbers differ - expected: '431828317', found: '330443256'

Test #9:

score: 0
Wrong Answer
time: 250ms
memory: 47456kb

input:

292 5 1002449813

output:

530615262

result:

wrong answer 1st numbers differ - expected: '183613546', found: '530615262'

Test #10:

score: 0
Wrong Answer
time: 280ms
memory: 50972kb

input:

300 5 1005897091

output:

85483324

result:

wrong answer 1st numbers differ - expected: '915308166', found: '85483324'

Test #11:

score: 0
Wrong Answer
time: 0ms
memory: 12020kb

input:

45 50 1009100993

output:

920710816

result:

wrong answer 1st numbers differ - expected: '940158800', found: '920710816'

Test #12:

score: 0
Wrong Answer
time: 0ms
memory: 10552kb

input:

49 50 1001428049

output:

395802997

result:

wrong answer 1st numbers differ - expected: '1045902', found: '395802997'

Test #13:

score: 0
Wrong Answer
time: 2ms
memory: 14044kb

input:

49 50 1007851073

output:

600776070

result:

wrong answer 1st numbers differ - expected: '922264698', found: '600776070'

Test #14:

score: 0
Wrong Answer
time: 2ms
memory: 14008kb

input:

50 50 1005625571

output:

509017421

result:

wrong answer 1st numbers differ - expected: '442192770', found: '509017421'

Test #15:

score: 0
Wrong Answer
time: 251ms
memory: 53212kb

input:

290 300 1005068699

output:

357713920

result:

wrong answer 1st numbers differ - expected: '484359497', found: '357713920'

Test #16:

score: 0
Wrong Answer
time: 186ms
memory: 47404kb

input:

270 300 1003440637

output:

827092018

result:

wrong answer 1st numbers differ - expected: '899894137', found: '827092018'

Test #17:

score: 0
Wrong Answer
time: 276ms
memory: 55232kb

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

output:


result: