QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#412093	#4163. 地精部落	x-camp	80	23ms	102056kb	C++17	933b	2024-05-16 04:46:14	2024-05-16 04:46:14

Judging History

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

[2024-05-16 04:46:14]
评测

测评结果：80
用时：23ms
内存：102056kb

查看

[2024-05-16 04:46:14]
提交

answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <fstream>
#include <cstring>

using namespace std;

int N, P;
#define NMAX 5000
long long dp[NMAX];
long long bi[NMAX][NMAX];

int main() {
 //   freopen("goblin.in","r",stdin);
 //   freopen("goblin.out","w",stdout);
    cin >> N >> P;
    for (int i=0; i<N; i++) {
        bi[i][0] = 1;
        bi[i][i] = 1;
    }
    for (int i=1; i<N; i++) {
        for (int j=1; j<=i; j++) {
            bi[i][j] = (bi[i-1][j-1] + bi[i-1][j]) %P;
        }
    }
    // up pattern first
    dp[2] = 1; dp[1] = 1; dp[0] = 1;
    for (int i=3; i<=N; i++) {
        for (int j=2; j<=i; j += 2 ) {
            long long tmp = dp[j-1]*bi[i-1][j-1] %P;
            tmp = tmp *  dp[i-j] %P;
            dp[i] = (dp[i] + tmp) % P;
        }
    }
    if (N == 1) cout << 1;
    else cout << 2*dp[N] %P;
    return 0;
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 10

Accepted

time: 0ms

memory: 3636kb

input:

9 2811

output:

result:

ok single line: '1817'

Test #2:

score: 10

Accepted

time: 0ms

memory: 3776kb

input:

10 12929

output:

result:

ok single line: '10539'

Test #3:

score: 10

Accepted

time: 1ms

memory: 5796kb

input:

17 21929121

output:

result:

ok single line: '7310012'

Test #4:

score: 10

Accepted

time: 1ms

memory: 5748kb

input:

18 29121

output:

result:

ok single line: '15047'

Test #5:

score: 10

Accepted

time: 1ms

memory: 11956kb

input:

200 123849291

output:

88055017

result:

ok single line: '88055017'

Test #6:

score: 10

Accepted

time: 0ms

memory: 22268kb

input:

500 182739417

output:

182278339

result:

ok single line: '182278339'

Test #7:

score: 10

Accepted

time: 0ms

memory: 26292kb

input:

550 281321834

output:

25165060

result:

ok single line: '25165060'

Test #8:

score: 10

Accepted

time: 23ms

memory: 102056kb

input:

2500 18239314

output:

16654836

result:

ok single line: '16654836'

Test #9:

score: 0

Memory Limit Exceeded

input:

4000 129394123

output:

59559500

result:

Test #10:

score: 0

Memory Limit Exceeded

input:

4200 192340123

output:

81768678