Submission #1039162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039162		juicy	Asceticism (JOI18_asceticism)	C++17	100 / 100	10 ms	1368 KiB

asceticism

// https://en.wikipedia.org/wiki/Eulerian_number not very nice tbh :()

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, MD = 1e9 + 7;

int bpow(int a, int b = MD - 2) {
  int res = 1;
  for (; b; a = (long long) a * a % MD, b /= 2) {
    if (b & 1) {
      res = (long long) res * a % MD;
    }
  }
  return res;
}

int n, k;
int fact[N], ifact[N];

int C(int k, int n) {
  return (long long) fact[n] * ifact[k] % MD * ifact[n - k] % MD;
}

void add(int &x, int y) {
  if ((x += y) >= MD) {
    x -= MD;
  }
  if (x < 0) {
    x += MD;
  }
} 

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k; --k;
  fact[0] = 1;
  for (int i = 1; i <= n + 1; ++i) {
    fact[i] = (long long) fact[i - 1] * i % MD;
  }
  ifact[n + 1] = bpow(fact[n + 1]);
  for (int i = n; i >= 0; --i) {
    ifact[i] = (long long) ifact[i + 1] * (i + 1) % MD;
  }
  int res = 0;
  for (int i = 0; i <= k; ++i) {
    add(res, (long long) (i & 1 ? -1 : 1) * C(i, n + 1) * bpow(k + 1 - i, n) % MD);
  }
  cout << res;
  return 0;
}

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