Submission #764162

#	Time	Username	Problem	Language	Result	Execution time	Memory
764162		minhcool	Asceticism (JOI18_asceticism)	C++17	100 / 100	30 ms	3564 KiB

asceticism

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

#ifdef local

int n, k;

int fac[N], invfac[N];

int c(int n, int k){
	int temp = (fac[n] * invfac[k]) % mod;
	//cout << temp << "\n";
	temp = (temp * invfac[n - k]) % mod;
	//cout << temp << "\n";
	return temp;
}

int binpw(int base, int pw){
	int ans = 1;
	while(pw){
		if(pw & 1) ans = (ans * base) % mod;
		base = (base * base) % mod;
		pw >>= 1;
	}
	return ans;
}

void process(){
	cin >> n >> k;
	//dp[1][1] = 1;
	fac[0] = invfac[0] = 1;
	for(int i = 1; i <= 200000; i++){
		fac[i] = (fac[i - 1] * i) % mod;
		invfac[i] = (invfac[i - 1] * binpw(i, mod - 2)) % mod;
		//cout << fac[i] << " " << invfac[i] << "\n";
	}
	int answer = 0;
	k--;
	for(int i = 0; i <= k + 1; i++){
		int sig = (i & 1 ? -1 : 1);
		sig = sig * c(n + 1, i) * binpw(k - i + 1, n);
		//cout << c(n + 1, i) << " " << binpw(k - i + 1, n) << "\n";
		//cout << sig << "\n";
		sig = ((sig % mod) + mod) % mod;
		answer = (answer + sig) % mod;
	}
	cout << answer << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

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