QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#430728	#8015. 鸡	Williamxzh^#	15	683ms	271292kb	C++23	1.8kb	2024-06-04 11:59:02	2024-06-04 11:59:02

Judging History

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

[2024-06-04 11:59:02]
评测

测评结果：15
用时：683ms
内存：271292kb

查看

[2024-06-04 11:59:02]
提交

answer

#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
const int N=301;
int n,m,a[N];ll mod,f[N][2][N][N],ans;
il void add(ll &x,ll 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 main(){
    scanf("%d%d%lld",&n,&m,&mod);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<=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<=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){
            if(i-1>mi) break;
            for(int j=0;j<=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("%lld",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
*/

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0

Wrong Answer

time: 2ms

memory: 10064kb

input:

5 5 1004326439

output:

result:

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

Test #2:

score: 0

Wrong Answer

time: 0ms

memory: 9944kb

input:

5 4 1002682123

output:

result:

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

Test #3:

score: 5

Accepted

time: 585ms

memory: 215920kb

input:

287 1 1003060133

output:

328406329

result:

ok 1 number(s): "328406329"

Test #4:

score: 5

Accepted

time: 514ms

memory: 238644kb

input:

279 1 1004432189

output:

222258837

result:

ok 1 number(s): "222258837"

Test #5:

score: 5

Accepted

time: 668ms

memory: 267704kb

input:

300 1 1005912203

output:

707086810

result:

ok 1 number(s): "707086810"

Test #6:

score: 0

Wrong Answer

time: 582ms

memory: 258472kb

input:

288 5 1003307827

output:

302624836

result:

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

Test #7:

score: 0

Wrong Answer

time: 510ms

memory: 251556kb

input:

281 5 1008854383

output:

471801009

result:

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

Test #8:

score: 0

Wrong Answer

time: 456ms

memory: 247936kb

input:

270 5 1007619367

output:

330443256

result:

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

Test #9:

score: 0

Wrong Answer

time: 594ms

memory: 264592kb

input:

292 5 1002449813

output:

530615262

result:

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

Test #10:

score: 0

Wrong Answer

time: 683ms

memory: 271292kb

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

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

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

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

input:

50 50 1005625571

output:

509017421

result:

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

Test #15:

score: 0

Wrong Answer

time: 577ms

memory: 261240kb

input:

290 300 1005068699

output:

357713920

result:

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

Test #16:

score: 0

Wrong Answer

time: 426ms

memory: 246216kb

input:

270 300 1003440637

output:

827092018

result:

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

Test #17:

score: 0

Wrong Answer

time: 663ms

memory: 266844kb

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