Submission #19756

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19756	2016-02-25T05:18:09 Z	cki86201	괄호 (kriii4_R)	C++14	100 / 100	608 ms	32972 KB

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.0 / 8.0

#	Verdict	Execution time	Memory	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

Subtask #2

92.0 / 92.0

#	Verdict	Execution time	Memory	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