Submission #933781

#	Time	Username	Problem	Language	Result	Execution time	Memory
933781		alexander707070	Asceticism (JOI18_asceticism)	C++14	100 / 100	31 ms	2680 KiB

asceticism

#include<bits/stdc++.h>
#define MAXN 3007
using namespace std;

const long long mod=1e9+7;

int n,k,nn,kk;
long long dp[MAXN][MAXN],ans;
bool li[MAXN][MAXN];

long long fact[MAXN],invfact[MAXN];

long long power(long long a,long long b){
    if(b==0)return 1;
    if(b==1)return a;
    if(b==2)return (a*a)%mod;
    if(b%2==0)return power(power(a,b/2),2);
    return (power(power(a,b/2),2)*a)%mod;
}

long long comb(long long k,long long n){
    return (((fact[n]*invfact[k])%mod)*invfact[n-k])%mod;
}

int main(){

    cin>>n>>k;

    fact[0]=invfact[0]=1;
    for(long long i=1;i<=n+1;i++){
        fact[i]=(fact[i-1]*i)%mod;
        invfact[i]=power(fact[i],mod-2);
    }

    for(int i=0;i<=k-1;i++){
        if(i%2==0) ans+=(comb(i,n+1)*power(k-i,n))%mod;
        else ans-=(comb(i,n+1)*power(k-i,n))%mod;

        ans=(ans+mod)%mod;
    }

    cout<<ans<<"\n";

    return 0;
}

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