Submission #19868

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19868	2016-02-25T06:24:41 Z	yongwhan	괄호 (kriii4_R)	C++14	100 / 100	912 ms	17336 KB

R

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
const int mx=1e6+5;
typedef long long ll;

ll fact[mx], f[mx];

ll exp(ll a, ll b, ll m) {
  ll r=1;
  while(b) {
    if(b%2) r=(r*a)%m;
    a=(a*a)%m;
    b/=2;
  }
  return r;
}

ll inv(ll a, ll m) {
  return exp(a,m-2,m);
}

int binom(int n, int m, int mod) {
  ll a=fact[n], b=fact[m], c=fact[n-m];
  ll ret=a*inv(b,mod);
  ret%=mod;
  ret*=inv(c,mod);
  ret%=mod;
  return ret;
}

ll catalan(int n, int mod) {
  ll a=fact[2*n], b=fact[n+1], c=fact[n];
  ll ret=a*inv(b,mod);
  ret%=mod;
  ret*=inv(c,mod);
  ret%=mod;
  return ret;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fact[0]=1;
  for (int i=1; i<mx; i++)
    fact[i]=(fact[i-1]*i)%mod;

  ll n,k; cin>>n>>k;
  f[0]=1;
  for (int i=1; i<=n; i++) {
    if(i%2==0) f[i]=f[i-1]*(k+1)%mod;
    else {
      f[i]=(f[i-1]*(k+1))%mod;
      ll add=(exp(k,i/2,mod)*catalan(i/2,mod))%mod;
      f[i]=(f[i]+(mod-add))%mod;
    }
  }
  cout << f[n] << endl;
  return 0;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	280 ms	17336 KB	Output is correct
2	Correct	60 ms	17336 KB	Output is correct
3	Correct	673 ms	17336 KB	Output is correct
4	Correct	746 ms	17336 KB	Output is correct
5	Correct	763 ms	17336 KB	Output is correct
6	Correct	423 ms	17336 KB	Output is correct
7	Correct	476 ms	17336 KB	Output is correct
8	Correct	324 ms	17336 KB	Output is correct
9	Correct	138 ms	17336 KB	Output is correct
10	Correct	40 ms	17336 KB	Output is correct
11	Correct	35 ms	17336 KB	Output is correct
12	Correct	687 ms	17336 KB	Output is correct
13	Correct	648 ms	17336 KB	Output is correct
14	Correct	286 ms	17336 KB	Output is correct
15	Correct	307 ms	17336 KB	Output is correct
16	Correct	278 ms	17336 KB	Output is correct
17	Correct	832 ms	17336 KB	Output is correct
18	Correct	858 ms	17336 KB	Output is correct
19	Correct	903 ms	17336 KB	Output is correct
20	Correct	910 ms	17336 KB	Output is correct

Subtask #2

92.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	254 ms	17336 KB	Output is correct
2	Correct	84 ms	17336 KB	Output is correct
3	Correct	170 ms	17336 KB	Output is correct
4	Correct	824 ms	17336 KB	Output is correct
5	Correct	515 ms	17336 KB	Output is correct
6	Correct	636 ms	17336 KB	Output is correct
7	Correct	441 ms	17336 KB	Output is correct
8	Correct	255 ms	17336 KB	Output is correct
9	Correct	434 ms	17336 KB	Output is correct
10	Correct	61 ms	17336 KB	Output is correct
11	Correct	715 ms	17336 KB	Output is correct
12	Correct	752 ms	17336 KB	Output is correct
13	Correct	702 ms	17336 KB	Output is correct
14	Correct	340 ms	17336 KB	Output is correct
15	Correct	419 ms	17336 KB	Output is correct
16	Correct	418 ms	17336 KB	Output is correct
17	Correct	77 ms	17336 KB	Output is correct
18	Correct	907 ms	17336 KB	Output is correct
19	Correct	912 ms	17336 KB	Output is correct
20	Correct	907 ms	17336 KB	Output is correct