UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213781#2157. 数列N100600ms1252kbC++1.3kb2024-11-13 19:29:282024-11-13 23:02:05

answer

//
//  na 2157.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/13.
//

#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long int ll;
int n, mod;
inline int fac(int x){
    int res = 1;
    for(int i = 2; i <= x; ++i)
        res = ll(res) * i % mod;
    return res;
}
inline int qpow(int base, int exp){
    int res = 1;
    while(exp){
        if(exp & 1)
            res = ll(res) * base % mod;
        base = ll(base) * base % mod;
        exp >>= 1;
    }
    return res;
}
inline int inv(int x){
    return qpow(x, mod - 2);
}
inline int mul(int a, int b){
    return ll(a) * b % mod;
}
inline int C(int n, int k){
    return mul(mul(fac(n), inv(fac(k))), inv(fac(n - k)));
}
//int dp[55][55];
int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> mod;
    cout << mul(C(n * 2, n), inv(n + 1)) << endl;
//    n = 10;
//    dp[1][1] = 1;
//    for(int i = 2; i <= n; ++i)
//        for(int j = 1; j <= i * 2 - 3; ++j)
//            for(int k = j + 1; k <= i * 2 - 1; ++k)
//                dp[i][k] += dp[i - 1][j];
//    for(n = 1; n <= 10; ++n){
//        int ans = 0;
//        for(int i = n; i <= n * 2 - 1; ++i)
//            ans += dp[n][i];
//        cout << ans << endl;
//    }
    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 1252kb

input:

921 998054347

output:

345389219

result:

ok single line: '345389219'

Test #2:

score: 5
Accepted
time: 0ms
memory: 1252kb

input:

926 998064329

output:

458756691

result:

ok single line: '458756691'

Test #3:

score: 5
Accepted
time: 0ms
memory: 1252kb

input:

1000 998074327

output:

457273797

result:

ok single line: '457273797'

Test #4:

score: 5
Accepted
time: 0ms
memory: 1252kb

input:

952 998084303

output:

329700115

result:

ok single line: '329700115'

Test #5:

score: 5
Accepted
time: 1ms
memory: 1252kb

input:

989 998094347

output:

94788253

result:

ok single line: '94788253'

Test #6:

score: 5
Accepted
time: 0ms
memory: 1252kb

input:

902 998104313

output:

911969455

result:

ok single line: '911969455'

Test #7:

score: 5
Accepted
time: 0ms
memory: 1248kb

input:

914 998114333

output:

827812986

result:

ok single line: '827812986'

Test #8:

score: 5
Accepted
time: 0ms
memory: 1248kb

input:

986 998124313

output:

169699253

result:

ok single line: '169699253'

Test #9:

score: 5
Accepted
time: 0ms
memory: 1248kb

input:

947 998134339

output:

761932751

result:

ok single line: '761932751'

Test #10:

score: 5
Accepted
time: 0ms
memory: 1248kb

input:

934 998144339

output:

42889072

result:

ok single line: '42889072'

Test #11:

score: 5
Accepted
time: 61ms
memory: 1248kb

input:

991572 998154343

output:

277089318

result:

ok single line: '277089318'

Test #12:

score: 5
Accepted
time: 61ms
memory: 1248kb

input:

932800 998164337

output:

945072504

result:

ok single line: '945072504'

Test #13:

score: 5
Accepted
time: 55ms
memory: 1252kb

input:

903603 998174341

output:

29916736

result:

ok single line: '29916736'

Test #14:

score: 5
Accepted
time: 59ms
memory: 1252kb

input:

958646 998184331

output:

802903490

result:

ok single line: '802903490'

Test #15:

score: 5
Accepted
time: 60ms
memory: 1252kb

input:

983016 998194349

output:

802900579

result:

ok single line: '802900579'

Test #16:

score: 5
Accepted
time: 60ms
memory: 1252kb

input:

922347 998204353

output:

228575331

result:

ok single line: '228575331'

Test #17:

score: 5
Accepted
time: 64ms
memory: 1252kb

input:

976053 998214317

output:

982618317

result:

ok single line: '982618317'

Test #18:

score: 5
Accepted
time: 63ms
memory: 1252kb

input:

957300 998224351

output:

514549818

result:

ok single line: '514549818'

Test #19:

score: 5
Accepted
time: 60ms
memory: 1248kb

input:

921760 998234353

output:

470386410

result:

ok single line: '470386410'

Test #20:

score: 5
Accepted
time: 56ms
memory: 1252kb

input:

912948 998244353

output:

129235345

result:

ok single line: '129235345'