제출 #114140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114140		Saboon	Asceticism (JOI18_asceticism)	C++14	100 / 100	19 ms	1152 KiB

asceticism

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int fac[maxn], revfac[maxn];

ll power(ll a, ll b){
	if (b == 0)
		return 1;
	ll ret = power(a, b / 2);
	ret = 1ll * ret * ret % mod;
	if (b & 1)
		return ret * a % mod;
	return ret;
}

ll C(int n, int r){
	return 1ll * fac[n] * revfac[r] % mod * revfac[n - r] % mod;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	m --;
	fac[0] = 1;
	for (int i = 1; i <= n + 5; i++)
		fac[i] = 1ll * fac[i - 1] * i % mod;
	revfac[n + 5] = power(fac[n + 5], mod - 2);
	for (int i = n + 4; i >= 0; i--)
		revfac[i] = 1ll * revfac[i + 1] * (i + 1) % mod;
	ll answer = 0;
	int sign = 1;
	for (int k = 0; k <= m; k++){
		ll t = 1ll * sign * C(n + 1, k) * power(m + 1 - k, n) % mod;
		answer = (answer + t + mod) % mod;
		sign *= -1;
	}
	cout << answer << endl;
}

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