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
#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;
}
# 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
# 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