Submission #19756

#	Time	Username	Problem	Language	Result	Execution time	Memory
19756		cki86201	괄호 (kriii4_R)	C++14	100 / 100	608 ms	32972 KiB

R

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

const ll MOD = 1e9 + 7;

ll F[2000010], iF[2000020];

ll pw(ll x, ll y){
	ll res = 1;
	while(y){
		if(y & 1)res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}

ll nCr(int x, int y){
	return F[x] * iF[y] % MOD * iF[x-y] % MOD;
}

int main(){
	F[0] = 1;
	for(int i=1;i<2000010;i++)F[i] = i * F[i-1] % MOD;
	iF[0] = 1;
	for(int i=1;i<2000010;i++)iF[i] = pw(F[i], MOD-2);
	int N, K;
	scanf("%d%d", &N, &K);
	ll ans = 0;
	for(int i=(N&1);i<=N;i+=2){
		int a = (N-i)/2;
		int b = (N+i)/2;
		//printf("%d %d\n", a, b);
		ll g;
		if(a > 0)g = (nCr(a+b, b) - nCr(a+b, b+1) + MOD) % MOD;
		else g = 1;
		ans = (ans + pw(K, b) * g) % MOD;
	}
	printf("%lld", ans);
	
	return 0;
}

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