Submission #20108

#	Time	Username	Problem	Language	Result	Execution time	Memory
20108		kk1401	괄호 (kriii4_R)	C++98	0 / 100	390 ms	32332 KiB

R

#include<stdio.h>
#define M 1000001
#define T 1000000007ll

long long power[M],k,fact[M],d[M],f[M];
int n;

long long Pow(long long a)
{
	long long i,t=1ll,ans=1ll;
	int c=0;
	
	f[0] = a;
	for(i=1; ; i++){
		f[i] = (f[i-1] * f[i-1]) % T;
		t*=2ll;
		if(t>=T) break;
	}
	
	for(t = T-2;;){
		if(t&1ll) ans = (ans * f[c]) % T;
		c++; t/=2ll;
		if(t==0) break;
	}
	return ans;
}

long long catalan(int a)
{
	return (((Pow(a+1)*Pow(fact[a]))%T) * ((Pow(fact[a])*fact[2*a])%T))%T;
}

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

	power[0] = fact[0] = 1ll; 
	for(i=1; i<=n; i++) power[i] = (power[i-1] * k) % T;
	for(i=1; i<=2*n; i++) fact[i] = (fact[i-1] * i) % T;
	
	d[1] = k;
	
	for(i=2; i<=n; i++){
		if(i%2 == 0) d[i] = (d[i-1] * (k + 1ll)) % T;
		else d[i] = ((d[i-1] * (k+1)) % T - (power[(i-1)/2] * catalan((i-1)/2)) % T + T) % T;
	}
	
	printf("%lld",d[n]);
	
	return 0;
}

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