Submission #105441

#	Time	Username	Problem	Language	Result	Execution time	Memory
105441		he_____he	Asceticism (JOI18_asceticism)	C++14	100 / 100	28 ms	1920 KiB

asceticism

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int cys=1000000007;
int n,k;
ll fac[100005],inv[100005];

int mod(int x){return x>=cys?x-cys:x;}

ll qpow(ll x,ll p){
	ll ret=1;
	for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
	return ret;
}

int main(){
	n=readint(); k=n-readint()+1;
	fac[0]=inv[0]=1;
	for(int i=1;i<=n+1;i++) fac[i]=fac[i-1]*i%cys,inv[i]=qpow(fac[i],cys-2);
	ll ans=0;
	for(int i=0;i<=k;i++) ans=mod(ans+((i&1)?cys-1:1)*qpow(k-i,n)%cys*fac[n+1]%cys*inv[i]%cys*inv[n-i+1]%cys);
	printf("%lld\n",ans);
	return 0;
}

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