Submission #20082

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20082	2016-02-25T10:43:05 Z	gs14004	괄호 (kriii4_R)	C++14	8 / 100	608 ms	48596 KB

R

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint fact[2000005];
lint cat[2000005];
lint dp[2000005];

lint ipow(lint x, lint p){
    lint ret = 1, piv = x % mod;
    while(p){
        if(p&1) ret *= piv;
        piv *= piv;
        ret %= mod;
        piv %= mod;
        p >>= 1;
    }
    return ret;
}
 
int main(){
	int n, k;
	cin >> n >> k;
	fact[0] = 1;
	for(int i=1; i<=n; i++){
		fact[i] = fact[i-1] * i % mod;
	}
	for(int i=0; i<=n; i++){
		cat[i] = fact[2*i] * ipow(fact[i] * fact[i], mod - 2) % mod;
		cat[i] *= ipow(i+1, mod-2);
	}
	dp[0] = 1;
	for(int i=1; i<=n; i++){
		if(i%2 == 0){
			dp[i] = dp[i-1] * (k+1) % mod;
		}
		else{
			dp[i] = dp[i-1] * (k+1) % mod - cat[i/2] * ipow(k, i/2) % mod + mod;
			dp[i] %= mod;
		}
	}
	cout << dp[n];
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	175 ms	48596 KB	Output is correct
2	Correct	37 ms	48596 KB	Output is correct
3	Correct	444 ms	48596 KB	Output is correct
4	Correct	491 ms	48596 KB	Output is correct
5	Correct	506 ms	48596 KB	Output is correct
6	Correct	277 ms	48596 KB	Output is correct
7	Correct	312 ms	48596 KB	Output is correct
8	Correct	211 ms	48596 KB	Output is correct
9	Correct	86 ms	48596 KB	Output is correct
10	Correct	21 ms	48596 KB	Output is correct
11	Correct	23 ms	48596 KB	Output is correct
12	Correct	457 ms	48596 KB	Output is correct
13	Correct	427 ms	48596 KB	Output is correct
14	Correct	186 ms	48596 KB	Output is correct
15	Correct	201 ms	48596 KB	Output is correct
16	Correct	181 ms	48596 KB	Output is correct
17	Correct	549 ms	48596 KB	Output is correct
18	Correct	569 ms	48596 KB	Output is correct
19	Correct	608 ms	48596 KB	Output is correct
20	Correct	607 ms	48596 KB	Output is correct

Subtask #2

0.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	164 ms	48596 KB	Output isn't correct
2	Halted	0 ms	0 KB	-