Submission #56855

#	Time	Username	Problem	Language	Result	Execution time	Memory
56855		ksun48	Asceticism (JOI18_asceticism)	C++14	100 / 100	60 ms	2448 KiB

asceticism

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

const LL MOD = 1000000007;

LL powmod(LL a, LL n){
	if(n == 0) return 1;
	if(n % 2) return (a * powmod(a, n-1)) % MOD;
	LL c = powmod(a, n/2);
	return (c * c) % MOD;
}

LL inv(LL a){
	return powmod(a, MOD-2);
}
LL fact[110000];
LL invfact[110000];

int main(){
	fact[0] = invfact[0] = 1;
	for(LL i = 1; i < 110000; i++){
		fact[i] = (i * fact[i-1]) % MOD;
		invfact[i] = inv(fact[i]);
	}
	LL n, k;
	cin >> n >> k;
	k--;
	LL ans = 0;
	for(LL i = 0; i <= k; i++){
		LL cur = powmod(k+1-i,n);
		cur = (cur * fact[n+1]) % MOD;
		cur = (cur * invfact[i]) % MOD;
		cur = (cur * invfact[n+1-i]) % MOD;
		if(i % 2) cur *= -1;
		ans = (ans + cur) % MOD;
	}
	ans %= MOD;
	if(ans < 0) ans += MOD;
	cout << ans << '\n';
}

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