Submission #94594

#	Time	Username	Problem	Language	Result	Execution time	Memory
94594		aminra	Asceticism (JOI18_asceticism)	C++14	100 / 100	41 ms	2040 KiB

asceticism

//Smaug never desolated!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e5 + 7;
const int infint = (int)1e8 + 3;
const int MOD = (int)1e9 + 7;
const ll inf = (ll)1e18;
ll fact[MAXN], facrev[MAXN], n, k;
ll pwr(ll a, ll b)
{
	if(b == 0)
		return 1;
	if(b == 1)
		return a;
	ll c = pwr(a, b / 2);
	c = (c * c) % MOD;
	if(b % 2)
		c = (c * a) % MOD;
	return c;
}
ll inv(ll p)
{
	return pwr(p, MOD - 2);
}
ll C(ll n, ll k)
{
	ll mul = fact[n];
	mul = (mul * facrev[k]) % MOD;
	mul = (mul * facrev[n - k]) % MOD;
	return mul;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	fact[0] = 1;
	for (int i = 1; i < MAXN; i++)
		fact[i] = (fact[i - 1] * i) % MOD;
	for (int i = MAXN - 1; i >= 0; i--)
		facrev[i] = inv(fact[i]);
	ll ans = 0;
	for (int j = 0; j <= k; j++)
	{
		ll cur = pwr(k - j, n) * C(n + 1, j) % MOD;
		if(j % 2 == 0)
			ans = (ans + cur) % MOD;
		else
			ans = (ans - cur + MOD) % MOD;
	}
	cout << ans;
}

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