Submission #1240250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240250		duckindog	Asceticism (JOI18_asceticism)	C++20	100 / 100	10 ms	1864 KiB

asceticism

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10,
            M = 1'000'000'007;
int n, k;

inline int powder(int a, int b) { 
    int ret = 1;
    for (; b; b /= 2, a = 1ll * a * a % M) { 
        if (b & 1) ret = 1ll * ret * a % M;
    }
    return ret;
}

int fac[N], ifac[N];
inline int C(int n, int k) { return 1ll * fac[n] * ifac[n - k] % M * ifac[k] % M; }

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    { // init
        fac[0] = 1;
        for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % M;
        ifac[N - 1] = powder(fac[N - 1], M - 2);
        for (int i = N - 1; i >= 1; --i) ifac[i - 1] = 1ll * ifac[i] * i % M; 
    }

    cin >> n >> k;

    int answer = 0;
    for (int i = 0; i < k; ++i) { 
        int cnt = 1ll * C(n + 1, i) * powder(k - i, n) % M; 
        if (i & 1) answer = (answer + M - cnt) % M;
        else answer = (answer + cnt) % M;
    }

    cout << answer << "\n";
}

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