Submission #1149898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149898		12345678	Asceticism (JOI18_asceticism)	C++20	100 / 100	40 ms	1220 KiB

asceticism

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll mod=1e9+7, nx=1e5+5;

ll n, k, res, f[nx];

ll binpow(ll a, ll b)
{
    if (b==0) return 1;
    ll tmp=binpow(a, b/2);
    if (b%2) return (((tmp*tmp)%mod)*a)%mod;
    else return (tmp*tmp)%mod;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    f[0]=1;
    for (int i=1; i<=n+1; i++) f[i]=(f[i-1]*i)%mod;
    //cout<<"debug "<<(f[4]*binpow(f[4], mod-2))%mod<<'\n';
    k=n-k;
    for (int i=0; i<=k; i++)
    {
        ll tmp=(((((binpow(k+1-i, n)*f[n+1])%mod)*binpow(f[i], mod-2))%mod)*binpow(f[n+1-i], mod-2)%mod);
        if (i%2) tmp=((-tmp)+mod)%mod;
        res=(res+tmp)%mod;
    }
    cout<<res;
}

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