Submission #916872

#	Time	Username	Problem	Language	Result	Execution time	Memory
916872		mickey080929	Asceticism (JOI18_asceticism)	C++17	100 / 100	14 ms	6748 KiB

asceticism

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll mod = 1e9 + 7;

ll modpow(ll a, ll b) {
	ll ret = 1;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}

ll fac[400010];
ll inv[400010];

ll C(ll n, ll r) {
	if (n < r) return 0;
	return fac[n] * inv[r] % mod * inv[n-r] % mod;
}

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	fac[0] = 1;
	for (ll i=1; i<=400000; i++) {
		fac[i] = fac[i-1] * i % mod;
	}
	inv[400000] = modpow(fac[400000], mod-2);
	for (ll i=399999; i>=0; i--) {
		inv[i] = inv[i+1] * (i+1) % mod;
	}

	ll n, k;
	cin >> n >> k;
	ll ans = modpow(k, n);
	for (ll i=1; i<=k-1; i++) {
		ll cur = modpow(k-i, n) * C(n+1, i) % mod;
		if (i & 1) ans = (ans - cur + mod) % mod;
		else ans = (ans + cur) % mod;
	}
	cout << ans << '\n';
}

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