Submission #20174

#	Time	Username	Problem	Language	Result	Execution time	Memory
20174		sui	괄호 (kriii4_R)	C++14	100 / 100	129 ms	48604 KiB

R

#define _CRT_SECURE_NO_WARNINGS // scanf(), gets() (needed for Visual C++)

//#define NDEBUG
#include <cassert>

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>

#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <deque>


using namespace std;

#define MEMSET(x, WITH) memset(x, (WITH), sizeof(x))
#define FOR(i, E) for(int i=0; i<(E); i++)
#define REP(i, LO, HI) for(int i=(LO); i<=(HI); i++)

#define GETINT(x) scanf("%d", &x)
#define GETDBL(x) scanf("%lf", &x)
#define GETSTR(x) scanf("%s", x)
#define NEWINT(x) int x; scanf("%d", &x)
#define NEWDBL(x) double x; scanf("%lf", &x)
#define NEWLN putchar('\n')

typedef long long ll;

const ll MOD = 1000000007;
//const double PI = atan(1) * 4;

#ifdef _WIN32
#define popcnt __popcnt
#else
#define popcnt __builtin_popcount
#endif





const int SZ = 2000333;

ll inv[SZ];
ll fac[SZ];
ll invfac[SZ];

void precalc() {
	inv[1] = 1;
	for (int x=2; x<SZ; x++) {
		ll q = MOD / x;
		ll r = MOD % x;

		q = MOD - q;
		inv[x] = q * inv[r] % MOD;
	}

	fac[0] = 1;
	for (int x=1; x<SZ; x++) fac[x] = fac[x-1] * x % MOD;

	invfac[0] = 1;
	for (int x=1; x<SZ; x++) invfac[x] = invfac[x-1] * inv[x] % MOD;
}

ll getCatalanNumber(int n) {
	return fac[2*n] * invfac[n] % MOD * invfac[n+1] % MOD;
}







int main() {
	precalc();

	int N;
	ll K;
	cin >> N >> K;



	ll sum = K;
	ll a = K;
	ll k = K*K%MOD;

	for (int i=2; i<=N; i++) {
		if (i&1) {
			sum = (sum*K%MOD + sum - a + MOD) % MOD;
			a = getCatalanNumber(i/2 + 1) * k % MOD;
			k = k * K % MOD;
		} 
		else {
			sum = (sum*K%MOD + sum) % MOD;
		}
	}


	cout << sum << endl;


	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92