Submission #19716

#	Time	Username	Problem	Language	Result	Execution time	Memory
19716		sujin	괄호 (kriii4_R)	C++14	0 / 100	163 ms	2268 KiB

R

#include <cstdio>
#include <cstdlib>

#define MOD 1000000007

long long pow(long long n, long long k)
{
	if (k == 0)
		return 1;
	long long h = pow(n, k / 2);
	return h * h % MOD * ((k & 1) ? n : 1) % MOD;
}

long long mod_inverse(long long a)
{
	return pow(a, MOD - 2);
}

int main()
{
	int n, k;
	scanf("%d %d", &n, &k);

	long long *c = (long long *)calloc(n / 2 + 1, sizeof(long long));
	c[0] = 1;
	for (int i = 1; i <= n / 2; i++)
		c[i] = mod_inverse(i + 1) * (4 * i - 2) % MOD * c[i - 1] % MOD;

	long long s = 0;
	for (int l = 0; l <= n; l += 2)
		s = (s + c[l / 2] * pow(k, l / 2) % MOD * pow(k, n - l) % MOD) % MOD;

	printf("%lld\n", s);

	return 0;
}

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