Submission #914862

#	Time	Username	Problem	Language	Result	Execution time	Memory
914862		amirhoseinfar1385	Asceticism (JOI18_asceticism)	C++17	100 / 100	23 ms	2140 KiB

asceticism

#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
long long mod=1e9+7;
long long fact[maxn],revfact[maxn];

long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}

void aval(){
	fact[0]=1;
	for(long long i=1;i<maxn;i++){
		fact[i]=1ll*fact[i-1]*i%mod;
	}
	revfact[maxn-1]=mypow(fact[maxn-1],mod-2);
	for(long long i=maxn-2;i>=0;i--){
		revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
	}
}
long long c(long long i,long long j){
	if(i<0||j<0||i<j){
		return 0;
	}
	return 1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
}

int main(){
	aval();
	long long n,k;
	cin>>n>>k;
	long long res=0;
	for(long long i=k;i>=1;i--){
		long long fake=mypow(i,n)*c(n+1,k-i)%mod;
		if((k-i)&1){
			res-=fake;
		}
		else{
			res+=fake;
		}
		//cout<<i<<" "<<fake<<" "<<mypow(i,n)<<" "<<c(n+1,k-i)<<endl;
	}
//	cout<<res<<endl;
	res+=1000000*mod;
	res%=mod;
//	res=abs(res);
//	res%=mod;
//	res = ((res % mod) + mod) % mod;
	cout<<res<<"\n";
}

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