답안 #19688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19688	2016-02-25T04:34:21 Z	Namnamseo	괄호 (kriii4_R)	C++14	100 / 100	419 ms	32332 KB

R

#include <cstdio>

typedef long long ll;
const ll M=int(1e9)+7;

ll catalan[1000010];
ll fact[2000010];
ll kpow[1000010];

ll pow(ll a,ll b){
    if(b==0) return 1;
    ll ret=pow(a,b/2);
    ret=(ret*ret)%M;
    if(b&1) ret=(ret*a)%M;
    return ret;
}

int main()
{
    int n,k;
    int i;
    scanf("%d%d",&n,&k);
    
    fact[0]=1;
    kpow[0]=1;
    for(i=1; i<=2*n; ++i) fact[i]=(fact[i-1]*i)%M;
    catalan[0]=1;
    for(i=1; i<=n; ++i){
        catalan[i] = fact[2*i] * pow( fact[i+1]*fact[i]%M, M-2 ) %M;
        kpow[i] = (kpow[i-1]*k)%M;
    }

    ll cur=1;
    
    for(i=1; i<=n; ++i){
        cur=cur*(k+1)%M;
        if(i%2 == 1){ // can perfectly match
            //printf("i %d; perfect match %I64d\n",i,catalan[(i-1)/2]*kpow[(i-1)/2]%M);
            cur -= catalan[(i-1)/2]*kpow[(i-1)/2]%M;
            cur = (cur+M)%M;
        }
        //printf("i %d : %I64d\n",i,cur);
    }
    printf("%d\n",int(cur));
    return 0;
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	32332 KB	Output is correct
2	Correct	27 ms	32332 KB	Output is correct
3	Correct	308 ms	32332 KB	Output is correct
4	Correct	343 ms	32332 KB	Output is correct
5	Correct	354 ms	32332 KB	Output is correct
6	Correct	197 ms	32332 KB	Output is correct
7	Correct	217 ms	32332 KB	Output is correct
8	Correct	148 ms	32332 KB	Output is correct
9	Correct	57 ms	32332 KB	Output is correct
10	Correct	15 ms	32332 KB	Output is correct
11	Correct	17 ms	32332 KB	Output is correct
12	Correct	314 ms	32332 KB	Output is correct
13	Correct	302 ms	32332 KB	Output is correct
14	Correct	131 ms	32332 KB	Output is correct
15	Correct	141 ms	32332 KB	Output is correct
16	Correct	128 ms	32332 KB	Output is correct
17	Correct	380 ms	32332 KB	Output is correct
18	Correct	391 ms	32332 KB	Output is correct
19	Correct	410 ms	32332 KB	Output is correct
20	Correct	416 ms	32332 KB	Output is correct

Subtask #2

92.0 / 92.0

#	결과	실행 시간	메모리	Grader output
1	Correct	116 ms	32332 KB	Output is correct
2	Correct	38 ms	32332 KB	Output is correct
3	Correct	77 ms	32332 KB	Output is correct
4	Correct	382 ms	32332 KB	Output is correct
5	Correct	239 ms	32332 KB	Output is correct
6	Correct	296 ms	32332 KB	Output is correct
7	Correct	201 ms	32332 KB	Output is correct
8	Correct	113 ms	32332 KB	Output is correct
9	Correct	198 ms	32332 KB	Output is correct
10	Correct	27 ms	32332 KB	Output is correct
11	Correct	333 ms	32332 KB	Output is correct
12	Correct	347 ms	32332 KB	Output is correct
13	Correct	330 ms	32332 KB	Output is correct
14	Correct	153 ms	32332 KB	Output is correct
15	Correct	189 ms	32332 KB	Output is correct
16	Correct	191 ms	32332 KB	Output is correct
17	Correct	29 ms	32332 KB	Output is correct
18	Correct	415 ms	32332 KB	Output is correct
19	Correct	410 ms	32332 KB	Output is correct
20	Correct	419 ms	32332 KB	Output is correct