Submission #1284056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284056		Icelast	Asceticism (JOI18_asceticism)	C++20	100 / 100	15 ms	3404 KiB

asceticism

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9, mod = 1e9+7;
vector<ll> fact, invfact;
ll binpow(ll a, ll b){
    ll res = 1;
    while(b > 0){
        if(b&1){
            res*=a;
            res%=mod;
        }
        a*=a;
        a%=mod;
        b/=2;
    }
    return res;
}
ll modinv(ll x){
    return binpow(x, mod-2);
}
void calcfact(int n){
    fact.resize(n+1, 0);
    invfact.resize(n+1, 0);

    fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = fact[i-1]*i;
        fact[i]%=mod;
    }
    invfact[n] = modinv(fact[n]);
    for(int i = n-1; i >= 0; i--){
        invfact[i] = invfact[i+1]*(i+1)%mod;
    }
}
ll nCk(ll n, ll k){
    if(k < 0 || k > n) return 0;
    return fact[n]*(invfact[k]*invfact[n-k]%mod)%mod;
}
ll distributing_apples(ll n, ll m){ // number of people, apple
    return nCk(m+n-1, n-1);
}
void solve(){
    calcfact(2e5);
    int n, k;
    cin >> n >> k;
    k--;
    ll ans = 0;
    for(int i = 0; i <= k; i++){
        ans += (binpow(-1, i) * nCk(n+1, i) + mod) % mod * (binpow(k+1-i, n) + mod) % mod;
    }
    ans %= mod;
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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