Submission #19758

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19758	2016-02-25T05:20:01 Z	tonyjjw	괄호 (kriii4_R)	C++14	100 / 100	765 ms	17348 KB

R

#include <algorithm>
#include <assert.h>
#include <complex>
#include <ctype.h>
#include <functional>
#include <iostream>
#include <limits.h>
#include <locale.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <vector>
#include <unordered_set>
#include <unordered_map>

#pragma warning(disable:4996)
using namespace std;

#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <ldb, ldb> pdd;

int IT_MAX = 131072;
const ll MOD = 1000000007;
const int INF = 1034567891;
const ll LL_INF = 2234567890123456789ll;
const db PI = 3.141592653589793238;
const ldb ERR = 1E-10;

ll mul_inv(ll a, ll b)
{
	ll b0 = b, t, q;
	ll x0 = 0, x1 = 1;
	if (b == 1) return 1;
	while (a > 1) {
		q = a / b;
		t = b, b = a % b, a = t;
		t = x0, x0 = x1 - q * x0, x1 = t;
	}
	if (x1 < 0) x1 += b0;
	return x1;
}

ll F[1000050];
ll powK[1000050];
ll C(int i, int j) {
	ll rv = F[i];
	rv = (rv * mul_inv(F[j], MOD)) % MOD;
	rv = (rv * mul_inv(F[i - j], MOD)) % MOD;
	return rv;
}

int main() {
	int N, K, i;
	scanf("%d %d", &N, &K);
	
	F[0] = 1, powK[0] = 1;
	for (i = 1; i <= N; i++) F[i] = (F[i - 1] * i) % MOD;
	for (i = 1; i <= N; i++) powK[i] = (powK[i - 1] * K) % MOD;

	ll ans = powK[N];
	for (i = 1; i <= N / 2; i++) {
		ll t = (C(N, i) - C(N, i - 1) + MOD) % MOD;
		ans = (ans + t * powK[N - i]) % MOD;
	}
	printf("%lld\n", ans);
	return 0;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	232 ms	17348 KB	Output is correct
2	Correct	47 ms	17348 KB	Output is correct
3	Correct	565 ms	17348 KB	Output is correct
4	Correct	628 ms	17348 KB	Output is correct
5	Correct	641 ms	17348 KB	Output is correct
6	Correct	356 ms	17348 KB	Output is correct
7	Correct	399 ms	17348 KB	Output is correct
8	Correct	267 ms	17348 KB	Output is correct
9	Correct	107 ms	17348 KB	Output is correct
10	Correct	27 ms	17348 KB	Output is correct
11	Correct	29 ms	17348 KB	Output is correct
12	Correct	574 ms	17348 KB	Output is correct
13	Correct	541 ms	17348 KB	Output is correct
14	Correct	233 ms	17348 KB	Output is correct
15	Correct	254 ms	17348 KB	Output is correct
16	Correct	231 ms	17348 KB	Output is correct
17	Correct	700 ms	17348 KB	Output is correct
18	Correct	716 ms	17348 KB	Output is correct
19	Correct	755 ms	17348 KB	Output is correct
20	Correct	765 ms	17348 KB	Output is correct

Subtask #2

92.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	205 ms	17348 KB	Output is correct
2	Correct	63 ms	17348 KB	Output is correct
3	Correct	134 ms	17348 KB	Output is correct
4	Correct	691 ms	17348 KB	Output is correct
5	Correct	435 ms	17348 KB	Output is correct
6	Correct	530 ms	17348 KB	Output is correct
7	Correct	370 ms	17348 KB	Output is correct
8	Correct	210 ms	17348 KB	Output is correct
9	Correct	364 ms	17348 KB	Output is correct
10	Correct	45 ms	17348 KB	Output is correct
11	Correct	597 ms	17348 KB	Output is correct
12	Correct	628 ms	17348 KB	Output is correct
13	Correct	595 ms	17348 KB	Output is correct
14	Correct	278 ms	17348 KB	Output is correct
15	Correct	348 ms	17348 KB	Output is correct
16	Correct	352 ms	17348 KB	Output is correct
17	Correct	55 ms	17348 KB	Output is correct
18	Correct	760 ms	17348 KB	Output is correct
19	Correct	760 ms	17348 KB	Output is correct
20	Correct	763 ms	17348 KB	Output is correct