Submission #100570

#	Time	Username	Problem	Language	Result	Execution time	Memory
100570		JPN20	Asceticism (JOI18_asceticism)	C++17	100 / 100	199 ms	3672 KiB

asceticism

#include <bits/stdc++.h>
using namespace std;

long long fact[200009], inv[200009], mod = 1000000007;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 32; i++) {
		if ((b & (1LL << i)) != 0) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

void init() {
	fact[0] = 1; for (int i = 1; i <= 200000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
	for (int i = 0; i <= 200000; i++) inv[i] = modpow(fact[i], mod - 2, mod);
}

long long ncr(long long n, long long r) {
	if (r < 0 || n < r) return 0;
	return (fact[n] * inv[r] % mod) * inv[n - r] % mod;
}

long long solve(long long A, long long B) {
	long long sum = 0, c = 1;
	for (int i = A; i >= 1; i--) {
		long long V1 = modpow(i, A + B, mod);
		long long V2 = ncr(A + B + 1, A - i);
		sum += c * V1 * V2; sum += mod * mod; sum %= mod;
		c *= -1;
	}
	return sum;
}

int main() {
	init();
	long long N, K; cin >> N >> K;
	cout << solve(K, N - K) << endl;
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 51 / 51