Submission #19912

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19912	2016-02-25T07:01:01 Z	xhae	괄호 (kriii4_R)	C++14	100 / 100	715 ms	13440 KB

R

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

const int mmod = 1000000007;

	int inv_mod(int a, int b) {
		if (a == 1) return b;
		int div = mmod / a + 1;
		return inv_mod((a * (long long)div) % mmod, (b * (long long)div) % mmod);
	}

int pw(int a, int b) {
  if (!b) return 1;
  int c = pw(a, b/2);
  c = (c * 1LL * c) % mmod;
  if (b % 2) c = (c * 1LL * a) % mmod;
  return c;
}

int mult(int a, int b, int c) {
  int d = (a * 1LL * b) % mmod;
  d = (d * 1LL * c) % mmod;
  return d;
}

vector<int> fac;

int catalan(int n) {
  int res = mult(fac[2*n], inv_mod(fac[n+1], 1), inv_mod(fac[n], 1));
  return res;
}

int main()
{
  int n, k;
  cin >> n >> k;

  fac.resize(3*n+1);
  fac[0] = 1;
  for (int i=1; i<=3*n; i++)
    fac[i] = (fac[i-1] * 1LL * i) % mmod;

  int res = pw(k+1, n);
  for (int i=0; 2*i+1<=n; i++) {
    res = (res - mult(catalan(i), pw(k, i), pw(k+1, n-2*i-1))) % mmod;
    res = (res + mmod) % mmod;
  }
  printf("%d\n", res);
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	206 ms	5272 KB	Output is correct
2	Correct	36 ms	2440 KB	Output is correct
3	Correct	521 ms	10364 KB	Output is correct
4	Correct	578 ms	11364 KB	Output is correct
5	Correct	588 ms	11560 KB	Output is correct
6	Correct	325 ms	7176 KB	Output is correct
7	Correct	362 ms	7856 KB	Output is correct
8	Correct	239 ms	5824 KB	Output is correct
9	Correct	97 ms	3408 KB	Output is correct
10	Correct	22 ms	2128 KB	Output is correct
11	Correct	25 ms	2168 KB	Output is correct
12	Correct	530 ms	10544 KB	Output is correct
13	Correct	499 ms	10076 KB	Output is correct
14	Correct	209 ms	5340 KB	Output is correct
15	Correct	227 ms	5616 KB	Output is correct
16	Correct	208 ms	5252 KB	Output is correct
17	Correct	651 ms	12476 KB	Output is correct
18	Correct	664 ms	12788 KB	Output is correct
19	Correct	709 ms	13440 KB	Output is correct
20	Correct	713 ms	13440 KB	Output is correct

Subtask #2

92.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	187 ms	4916 KB	Output is correct
2	Correct	58 ms	2748 KB	Output is correct
3	Correct	123 ms	3824 KB	Output is correct
4	Correct	643 ms	12328 KB	Output is correct
5	Correct	393 ms	8364 KB	Output is correct
6	Correct	492 ms	9916 KB	Output is correct
7	Correct	336 ms	7396 KB	Output is correct
8	Correct	186 ms	4944 KB	Output is correct
9	Correct	330 ms	7308 KB	Output is correct
10	Correct	41 ms	2456 KB	Output is correct
11	Correct	555 ms	10960 KB	Output is correct
12	Correct	582 ms	11368 KB	Output is correct
13	Correct	548 ms	10868 KB	Output is correct
14	Correct	256 ms	6040 KB	Output is correct
15	Correct	317 ms	7068 KB	Output is correct
16	Correct	316 ms	7112 KB	Output is correct
17	Correct	50 ms	2608 KB	Output is correct
18	Correct	712 ms	13440 KB	Output is correct
19	Correct	715 ms	13440 KB	Output is correct
20	Correct	711 ms	13440 KB	Output is correct