oj.uz

Submission #19716

# Submission time Handle Problem Language Result Execution time Memory
19716 2016-02-25T04:56:06 Z sujin 괄호 (kriii4_R) C++14
0 / 100
 163 ms 2268 KB 
#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.0 / 8.0

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

Subtask #2
0.0 / 92.0

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