oj.uz

Submission #20106

# Submission time Handle Problem Language Result Execution time Memory
20106 2016-02-25T13:42:08 Z kk1401 괄호 (kriii4_R) C++
0 / 100
 390 ms 32332 KB 
#include<stdio.h>
#define M 1000001
#define T 1000000007

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&1) 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 32332 KB Output is correct
2 Correct 34 ms 32332 KB Output is correct
3 Incorrect 390 ms 32332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 92.0

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