Submission #19843

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19843	2016-02-25T06:11:37 Z	yukariko	괄호 (kriii4_R)	C++14	8 / 100	1536 ms	19300 KB

R

#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;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	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

Subtask #2

0.0 / 92.0

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