답안 #19843

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19843 2016-02-25T06:11:37 Z yukariko 괄호 (kriii4_R) C++14
8 / 100
1536 ms 19300 KB
#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

int N, M;

long long cache[2000001];
char res[2000001];

long long mod_exp(long long a,long long b,long long c)
{
	a%=c;
	if(b==0)return 1;
	if(b==1)return a;
	if(b&1) return (a*mod_exp((a*a)%c,(b-1)/2,c))%c;
	return mod_exp((a*a)%c,b/2,c);
}

long long mod_div(long long a, long long b)
{
	return (a * mod_exp(b, MOD-2, MOD)) % MOD;
}

long long solve(int pos)
{
	if(pos > 2 * N)
		return 0;
	if(pos == 2 * N)
	{
		puts(res);
		return 1;
	}

	long long& ans = cache[pos];
	//if(ans != -1)
	//	return ans;

	res[pos / 2] = '(';
	res[2 * N - (pos / 2) - 1] = ')';
	ans = (solve(pos + 2) * M) % MOD;
	res[pos / 2 + 1] = ')';
	res[2 * N - (pos / 2) - 2] = '(';
	ans = (ans + solve(pos + 4) * M) % MOD;
	return ans;
}


int main()
{
	memset(cache, -1, sizeof(cache));
	scanf("%d%d", &N, &M);

	cache[0] = M;
	cache[1] = M;
	for(int i=2; i <= N; i++)
	{
		cache[i] = (cache[i-1] * 2 + cache[i-2] * 4 * (i - 1)) % MOD;
		cache[i] = mod_div(cache[i], i+1);
	}

	printf("%lld\n", cache[N]);
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 468 ms 19300 KB Output is correct
2 Correct 94 ms 19300 KB Output is correct
3 Correct 1130 ms 19300 KB Output is correct
4 Correct 1260 ms 19300 KB Output is correct
5 Correct 1291 ms 19300 KB Output is correct
6 Correct 718 ms 19300 KB Output is correct
7 Correct 798 ms 19300 KB Output is correct
8 Correct 536 ms 19300 KB Output is correct
9 Correct 220 ms 19300 KB Output is correct
10 Correct 56 ms 19300 KB Output is correct
11 Correct 59 ms 19300 KB Output is correct
12 Correct 1157 ms 19300 KB Output is correct
13 Correct 1096 ms 19300 KB Output is correct
14 Correct 477 ms 19300 KB Output is correct
15 Correct 509 ms 19300 KB Output is correct
16 Correct 462 ms 19300 KB Output is correct
17 Correct 1403 ms 19300 KB Output is correct
18 Correct 1446 ms 19300 KB Output is correct
19 Correct 1536 ms 19300 KB Output is correct
20 Correct 1531 ms 19300 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 418 ms 19300 KB Output isn't correct
2 Halted 0 ms 0 KB -