Submission #815719

#	Time	Username	Problem	Language	Result	Execution time	Memory
815719		LucaIlie	Asceticism (JOI18_asceticism)	C++17	100 / 100	12 ms	1088 KiB

asceticism

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int MOD = 1e9 + 7;

int fact[MAX_N], invfact[MAX_N];

int comb( int n, int k ) {
    return (long long)fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
}

int lgpow ( int a, int n ) {
    if ( n == 0 )
        return 1;

    int p = lgpow( a, n / 2 );
    p = (long long)p * p % MOD;
    if ( n % 2 == 1 )
        p = (long long)p * a % MOD;

    return p;
}

int main() {
    int n, k;

    cin >> n >> k;

    fact[0] = 1;
    for ( int i = 1; i <= n + 1; i++ )
        fact[i] = (long long)fact[i - 1] * i % MOD;
    invfact[n + 1] = lgpow( fact[n + 1], MOD - 2 );
    for ( int i = n; i >= 0; i-- )
        invfact[i] = (long long)invfact[i + 1] * (i + 1) % MOD;

    int ans = 0;
    for ( int i = 0; i < k; i++ )
        ans = (ans + (long long)comb( n + 1, i ) * lgpow( k - i, n ) * (i % 2 == 0 ? 1 : -1) + MOD) % MOD;
    cout << ans;

    return 0;
}

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