Submission #1174836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174836		betvoi	Asceticism (JOI18_asceticism)	C++20	49 / 100	12 ms	1864 KiB

asceticism

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=1e5+3,MOD=1e9+7;

int n,k;
ll fact[N],inv[N],ans=0;
ll binpow(ll x,ll y) {
    x%=MOD;
    ll res=1;
    while(y>0) {
        if (y%2) res=res*x%MOD;
        x=x*x%MOD;
        y/=2;	
    } 
    return res;
}
ll ncr(ll x, ll y) {
    if (y>x) return 0;
    ll res=fact[x]*inv[y]%MOD;
    res=res*inv[x-y]%MOD;
    return res;
}
void pre(int mx) {
    fact[0]=inv[0]=1;
    For(i,1,mx) {
        fact[i]=fact[i-1]*i%MOD;
        inv[i]=binpow(fact[i],MOD-2);
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    pre(100000);
    For(i,0,k) {
        ll haha=(i%2?MOD-1:1);
        ans=(ans+haha*binpow((k-i+MOD)%MOD,n)%MOD*ncr(n+1,i))%MOD;
    }
    cout << ans;
    return 0;
}

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