oj.uz

Submission #19982

# Submission time Handle Problem Language Result Execution time Memory
19982 2016-02-25T08:08:25 Z rlatkddn212 괄호 (kriii4_R) C++14
0 / 100
 2000 ms 2500 KB 
#include <iostream>
#include <math.h>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <tuple>
#include <deque>
#include <sstream>
#include <array>
using namespace std;
const long long mod = 1000000007;
long long f[100001];

long long binomialCoeff(long long n, long long k)
{
	long long res = 1;

	if (k > n - k)
		k = n - k;

	for (int i = 0; i < k; ++i)
	{
		res *= (n - i);
		res /= (i + 1);
		res %=mod;
	}

	return res%mod;
}

long long catalan(long long n)
{
	long long c = binomialCoeff(2 * n, n)%mod;
	return c / (n + 1);
}

int main(){
	int n;
	cin >> n;
	int k;
	cin >> k;
	f[0] = 1;

	for (int i = 1; i < n; i++){
		f[i] = (f[i - 1] * 2)%mod;
		if (i % 2 == 0){
			f[i] -= catalan(i / 2);
		}
		f[i] %= mod;
	}
	cout << f[n - 1] % mod << endl;
	return 0;
}

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 2500 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 92.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -