| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 20109 |
2016-02-25T13:58:05 Z |
kk1401 |
괄호 (kriii4_R) |
C++ |
|
386 ms |
32332 KB |
#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-2ll;;){
if(t&1ll) ans = (ans * f[c]) % T;
c++; t/=2ll;
if(t==0) break;
}
return ans;
}
long long catalan(int a)
{
return (((Pow((long long)(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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
32332 KB |
Output is correct |
| 2 |
Correct |
34 ms |
32332 KB |
Output is correct |
| 3 |
Incorrect |
386 ms |
32332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
