Submission #1235431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235431		Bahamin	Asceticism (JOI18_asceticism)	C++20	100 / 100	10 ms	4936 KiB

asceticism

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

const int h = MAX_N, w = MAX_N;
vector<ll> inv(h+w+1);
vector<ll> fact(h+w+1);
vector<ll> fact_inv(h+w+1);

inline int md(ll x) {x %= MOD; return x + (x < 0 ? MOD : 0);}
inline int ADD(ll a, ll b) { return md(a+b); }
inline int SUB(ll a, ll b) { return md(a-b); }
inline int MUL(ll a, ll b) { return md(1ll*a*b); }
inline int POW(ll a, ll b) { int res=1;while(b){if(b&1)res=MUL(res,a);a=MUL(a,a);b>>=1;}return res; }
inline int DIV(ll a, ll b) { return MUL(a, POW(b, MOD-2)); }

inline int comb(int n, int k){
    if (n<0 || k<0) return 0LL;
    if (n < k) return 0LL;
    return fact[n] * fact_inv[n - k] % MOD * fact_inv[k] % MOD;
};

void init()
{
    inv[1] = 1;
    for(int i=2; i<h+w+1; i++){
        inv[i] = MOD - (MOD/i) * inv[MOD%i] % MOD;
    }
    fact[0] = 1; 
    fact_inv[0] = 1; 
    for(int i=1; i<h+w+1; i++){
        fact[i] = fact[i-1] * i % MOD;
        fact_inv[i] = fact_inv[i-1] * inv[i] % MOD;
    }
}


void solve() {
    init();
    int n, k;
    cin >> n >> k;
    int ans = 0;
    for (int i = 0; i < k; i++) ans = ADD(ans, MUL((i % 2 ? -1 : 1), MUL(comb(n + 1, i), POW(k - i, n))));
    cout << ans << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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