Submission #478331

#	Time	Username	Problem	Language	Result	Execution time	Memory
478331		Mike4235	Asceticism (JOI18_asceticism)	C++17	100 / 100	40 ms	1104 KiB

asceticism

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

int power(int x, int n) {
    int res = 1;
    while (n) {
        if (n & 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

int n, k, res, fact[100005];

int nCk(int n, int k) {
    return fact[n] * power(fact[k], MOD - 2) % MOD * power(fact[n - k], MOD - 2) % MOD;
}

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> k;

    fact[0] = 1;
    for1(i,1,n + 1) fact[i] = fact[i - 1] * i % MOD;

    for1(i,0,k) {
        int x = power(k - i, n) * nCk(n + 1, i);
        if (i & 1) res = (res - x + MOD) % MOD;
        else res = (res + x) % MOD;
    }

    cout << res;
    
}

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