Submission #624212

#	Time	Username	Problem	Language	Result	Execution time	Memory
624212		iomoon191	Asceticism (JOI18_asceticism)	C++17	100 / 100	22 ms	1888 KiB

asceticism

#include <bits/stdc++.h>
using ll = long long;
#define int ll
using namespace std;

#define sz(x) (int)(x).size()
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define mod 1000000007

#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"
using vi = vector<int>;
using pi = pair<int, int>;

const ll N = 100005;
const ll inf = 1e18;

int n, k, f[N], g[N];

int ipow(int x, int p){
	int res = 1, piv = x;
	while(p){
		if(p & 1) res = res * piv % mod;
		piv = piv * piv % mod;
		p >>= 1;
	}
	return res;
}

void solve(){
	cin >> n >> k;
	f[0] = g[0] = 1;
	foru(i, 1, n + 1){
		f[i] = f[i - 1] * i % mod;
		g[i] = ipow(f[i], mod - 2);
	}
	int res = 0;
	foru(i, 0, k - 1){
		res += ((i & 1) ? -1 : 1) * (f[n + 1] * (g[i] * g[n + 1 - i] % mod) % mod) * ipow(k - i, n) % mod;;
	}
	res = (res % mod + mod) % mod;
	cout << res;
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t = 1; // cin >> t;
	while(t--){
		solve();
	}
}

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