Submission #19912

#	Time	Username	Problem	Language	Result	Execution time	Memory
19912		xhae	괄호 (kriii4_R)	C++14	100 / 100	715 ms	13440 KiB

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 / 8
• Subtask 2: 92 / 92