oj.uz

Submission #1039162

# Submission time Handle Problem Language Result Execution time Memory
1039162 2024-07-30T13:55:35 Z juicy Asceticism (JOI18_asceticism) C++17
100 / 100
 10 ms 1368 KB 
// 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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 464 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 464 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 464 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 2 ms 1112 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 2 ms 1140 KB Output is correct
34 Correct 3 ms 1368 KB Output is correct
35 Correct 9 ms 1244 KB Output is correct
36 Correct 10 ms 1240 KB Output is correct
37 Correct 10 ms 1244 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 4 ms 1036 KB Output is correct
40 Correct 5 ms 1116 KB Output is correct