Submission #797845

#	Time	Username	Problem	Language	Result	Execution time	Memory
797845		vjudge1	Asceticism (JOI18_asceticism)	C++17	100 / 100	10 ms	3460 KiB

asceticism

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,abm,bmi2")
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define int long long
//#define ld long double
using namespace std;
using ll=long long;
const int inf = 2e18;
const int MN = 2e5+5;
const int mod=1e9+7;
int n,k;
int binpow(int x, int y) {
	int res=1;
	while(y) {
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
int fact[MN],invfact[MN];
void preprocess() {
	fact[0]=invfact[0]=1;
	for (int i=1; i<MN; i++) {
		fact[i]=fact[i-1]*i%mod;
	}
	invfact[MN-1]=binpow(fact[MN-1],mod-2);
	for (int i=MN-2; i>=1; i--) {
		invfact[i]=invfact[i+1]*(i+1)%mod;
	}
}
int C(int n, int k) {
	return fact[n]*invfact[k]%mod*invfact[n-k]%mod;
}
inline void solve() {
	cin>>n>>k;
	int ans=0;
	for (int i=0; i<=k; i++) {
		int cur=C(n+1,i)*binpow(k-i,n)%mod;
		if(i&1) ans=(ans+mod-cur)%mod;
		else ans=(ans+cur)%mod;
	}
	cout<<ans;
}	
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	preprocess();
//	cin>>t;
	while(t--) {
		solve();
	}	
}

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