Submission #865663

#	Time	Username	Problem	Language	Result	Execution time	Memory
865663		jk410	Asceticism (JOI18_asceticism)	C++17	100 / 100	8 ms	2016 KiB

asceticism

#include <iostream>
#define MOD 1000000007
using namespace std;
typedef long long ll;
int N,K;
ll Fact[100002],InvFact[100002];
ll myPow(ll a,ll b){
    ll ret=1;
    while (b){
        if (b&1)
            ret=ret*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ret;
}
ll comb(int n,int r){
    return Fact[n]*InvFact[r]%MOD*InvFact[n-r]%MOD;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>K;
    Fact[0]=1;
    for (int i=1; i<=N+1; i++)
        Fact[i]=Fact[i-1]*i%MOD;
    InvFact[N+1]=myPow(Fact[N+1],MOD-2);
    for (int i=N+1; i; i--)
        InvFact[i-1]=InvFact[i]*i%MOD;
    ll ans=0;
    for (int i=0; i<=K; i++)
        ans=(ans+comb(N+1,i)*myPow(K-i,N)%MOD*(i%2?-1:1)+MOD)%MOD;
    cout<<ans;
    return 0;
}

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