Submission #19009

#	Time	Username	Problem	Language	Result	Execution time	Memory
19009		kriii	괄호 (kriii4_R)	C++14	100 / 100	38 ms	8896 KiB

R

#include <stdio.h>

const long long mod = 1000000007;

long long inv[500002],cat[500001];

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

	inv[1] = 1;
	for (int i=2;i<=n/2+1;i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;

	cat[0] = 1;
	for (int i=1;i<=n/2;i++) cat[i] = (4 * i - 2) * inv[i+1] % mod * cat[i-1] % mod;

	long long u = 1;
	for (int i=1;i<=n/2;i++){
		u = u * k % mod;
		cat[i] = cat[i] * u % mod;
	}

	long long ans = 1;
	for (int i=0;i<n;i++){
		ans = ans * (k + 1) % mod;
		if (i % 2 == 0) ans = (ans + mod - cat[i/2]) % mod;
	}
	printf ("%lld\n",ans);

	return 0;
}

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