답안 #19756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19756 2016-02-25T05:18:09 Z cki86201 괄호 (kriii4_R) C++14
100 / 100
608 ms 32972 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 540 ms 32972 KB Output is correct
2 Correct 510 ms 32972 KB Output is correct
3 Correct 577 ms 32972 KB Output is correct
4 Correct 593 ms 32972 KB Output is correct
5 Correct 593 ms 32972 KB Output is correct
6 Correct 550 ms 32972 KB Output is correct
7 Correct 560 ms 32972 KB Output is correct
8 Correct 543 ms 32972 KB Output is correct
9 Correct 526 ms 32972 KB Output is correct
10 Correct 504 ms 32972 KB Output is correct
11 Correct 511 ms 32972 KB Output is correct
12 Correct 583 ms 32972 KB Output is correct
13 Correct 571 ms 32972 KB Output is correct
14 Correct 540 ms 32972 KB Output is correct
15 Correct 541 ms 32972 KB Output is correct
16 Correct 534 ms 32972 KB Output is correct
17 Correct 599 ms 32972 KB Output is correct
18 Correct 594 ms 32972 KB Output is correct
19 Correct 603 ms 32972 KB Output is correct
20 Correct 603 ms 32972 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 528 ms 32972 KB Output is correct
2 Correct 508 ms 32972 KB Output is correct
3 Correct 515 ms 32972 KB Output is correct
4 Correct 597 ms 32972 KB Output is correct
5 Correct 568 ms 32972 KB Output is correct
6 Correct 581 ms 32972 KB Output is correct
7 Correct 558 ms 32972 KB Output is correct
8 Correct 536 ms 32972 KB Output is correct
9 Correct 556 ms 32972 KB Output is correct
10 Correct 522 ms 32972 KB Output is correct
11 Correct 588 ms 32972 KB Output is correct
12 Correct 586 ms 32972 KB Output is correct
13 Correct 588 ms 32972 KB Output is correct
14 Correct 546 ms 32972 KB Output is correct
15 Correct 549 ms 32972 KB Output is correct
16 Correct 554 ms 32972 KB Output is correct
17 Correct 519 ms 32972 KB Output is correct
18 Correct 608 ms 32972 KB Output is correct
19 Correct 607 ms 32972 KB Output is correct
20 Correct 601 ms 32972 KB Output is correct