Submission #1094543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094543		DobromirAngelov	Asceticism (JOI18_asceticism)	C++14	100 / 100	19 ms	1248 KiB

asceticism

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN=1e5+5;
const int MOD=1e9+7;

int n,k;
int fact[MAXN];
int invFact[MAXN];

int fastPow(long long x,int pwr)
{
    long long ret=1;
    while(pwr>0)
    {
        if(pwr&1) ret=ret*x%MOD;
        pwr/=2;
        x=x*x%MOD;
    }
    return ret;
}

void precomp()
{
    fact[0]=1;
    for(int i=1;i<=n+1;i++) fact[i]=1LL*fact[i-1]*i%MOD;
    invFact[0]=1;
    for(int i=1;i<=n+1;i++) invFact[i]=fastPow(fact[i], MOD-2);
}

int comb(int n,int k)
{
    return 1LL*fact[n]*invFact[n-k]%MOD*invFact[k]%MOD;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>k;
    k--;

    precomp();

    long long ans=0;
    for(int i=0;i<=k;i++)
    {
        long long cur=1LL*comb(n+1,i)*fastPow(k+1-i,n)%MOD;
        if(i%2==0) ans=(ans+cur)%MOD;
        else ans=(ans-cur+MOD)%MOD;
    }

    cout<<ans<<endl;

    return 0;
}

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