Submission #19776

#	Time	Username	Problem	Language	Result	Execution time	Memory
19776		gs13068	괄호 (kriii4_R)	C++98	100 / 100	596 ms	8896 KiB

R

#include <cstdio>

const int p = 1000000007;

int pw(int x, int y)
{
	return y & 1 ? (long long)pw(x, y ^ 1)*x%p : y ? pw((long long)x*x%p, y >> 1) : 1;
}

int fac[2000002];

int calc(int i, int j)
{
	if (i < j) return 0;
	if (i + j & 1) return 0;
	int r = j + 1;
	if (i & 1)
	{
		r = (long long)r * fac[i] % p;
		r = (long long)r * pw(fac[(i + j) / 2 + 1], p - 2) % p;
		r = (long long)r * pw(fac[(i - j) / 2], p - 2) % p;
	}
	else
	{
		r = (long long)r * fac[i] % p;
		r = (long long)r * pw(fac[(i + j) / 2 + 1], p - 2) % p;
		r = (long long)r * pw(fac[(i - j) / 2], p - 2) % p;
	}
	return r;
}

int main()
{
	int i, n, m, r = 0;
	fac[0] = 1;
	for (i = 1; i <= 2000000; i++) fac[i] = (long long)fac[i - 1] * i % p;
	scanf("%d%d", &n, &m);
	for (i = 0; i <= n; i++) r = (r + (long long)calc(n, i)*pw(m, n + i >> 1)) % p;
	printf("%d", r);
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92