Submission #724912

#	Time	Username	Problem	Language	Result	Execution time	Memory
724912		fatemetmhr	Asceticism (JOI18_asceticism)	C++17	100 / 100	31 ms	8152 KiB

asceticism

// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

ll fact[maxn];

inline void fix(int &a){
    if(a < 0)
        a += mod;
    if(a >= mod)
        a -= mod;
}

inline ll pw(ll a, ll b){
    ll ret = 1;
    for(; b; b >>= 1, a = a * a % mod)
        if(b & 1) ret = ret * a % mod;
    return ret;
}

inline ll ent(int n, int r){
    return fact[n] * pw(fact[r] * fact[n - r] % mod, mod - 2) % mod;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    fact[0] = 1;
    for(int i = 1; i < maxn; i++)
        fact[i] = i * fact[i - 1] % mod;

    int n, k; cin >> n >> k;
    int ans = 0;
    for(int i = 0; i < k; i++){
        fix(ans += pw(k - i, n) * ent(n + 1, i) % mod * (i % 2 ? -1 : 1));
    }
    cout << ans << endl;
} 

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