Submission #1162676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162676		Hamed_Ghaffari	Asceticism (JOI18_asceticism)	C++20	100 / 100	8 ms	1864 KiB

asceticism

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

using ll = long long;

const int MXN = 1e5+5;
const ll  MOD = 1e9+7;

ll power(ll a, ll b) {
    ll res=1;
    while(b) {
        if(b&1) (res *= a) %= MOD;
        (a *= a) %= MOD;
        b >>= 1;
    }
    return res;
}

int n, k;
ll F[MXN], I[MXN];

inline ll C(int n, int r) {
    return r<0 || r>n ? 0 : F[n]*I[r]%MOD*I[n-r]%MOD;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    F[0] = 1;
    for(int i=1; i<MXN; i++) F[i] = F[i-1]*i%MOD;
    I[0] = I[1] = 1;
    for(int i=2; i<MXN; i++) I[i] = (MOD-MOD/i)*I[MOD%i]%MOD;
    for(int i=2; i<MXN; i++) (I[i] *= I[i-1]) %= MOD;
    int n, k;
    cin >> n >> k;
    ll ans=0;
    for(int i=0; i<k; i++)
        (ans += C(n+1, i)*power(k-i, n)%MOD*(i&1 ? MOD-1 : 1)) %= MOD;
    cout << ans << '\n';
}

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