oj.uz

Submission #685060

# Submission time Handle Problem Language Result Execution time Memory
685060 2023-01-23T08:30:03 Z peijar Asceticism (JOI18_asceticism) C++17
49 / 100
 3 ms 1888 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MOD = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= MOD)
    x -= MOD;
  return x;
}

int sub(int x, int y) {
  x -= y;
  if (x < 0)
    x += MOD;
  return x;
}

int mult(int a, int b) { return a * b % MOD; }

int fastpow(int a, int b) {
  int ret = 1;
  for (; b; b /= 2, a = mult(a, a))
    if (b % 2)
      ret = mult(a, ret);
  return ret;
}

const int MAXN = 1e5 + 1;

int fact[MAXN], invFact[MAXN];

void initFact() {
  fact[0] = 1;
  for (int i = 1; i < MAXN; ++i)
    fact[i] = mult(i, fact[i - 1]);
  invFact[MAXN - 1] = fastpow(fact[MAXN - 1], MOD - 2);
  for (int i = MAXN - 1; i; --i)
    invFact[i - 1] = mult(i, invFact[i]);
}

int binom(int n, int k) {
  if (k < 0 or k > n)
    return 0;
  return mult(fact[n], mult(invFact[k], invFact[n - k]));
}

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

  initFact();
  int N, K;
  cin >> N >> K;
  K--;

  int ret = 0;

  for (int j = 0; j <= K; ++j) {
    int toAdd = mult(binom(N + 1, j), fastpow(K + 1 - j, N));
    if (j % 2)
      ret = sub(ret, toAdd);
    else
      ret = add(ret, toAdd);
  }
  cout << ret << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 2 ms 1888 KB Output is correct
7 Correct 2 ms 1888 KB Output is correct
8 Correct 2 ms 1888 KB Output is correct
9 Correct 2 ms 1884 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 2 ms 1888 KB Output is correct
7 Correct 2 ms 1888 KB Output is correct
8 Correct 2 ms 1888 KB Output is correct
9 Correct 2 ms 1884 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 3 ms 1876 KB Output is correct
13 Correct 2 ms 1876 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct
15 Correct 2 ms 1876 KB Output is correct
16 Correct 2 ms 1876 KB Output is correct
17 Correct 2 ms 1876 KB Output is correct
18 Correct 2 ms 1876 KB Output is correct
19 Correct 2 ms 1884 KB Output is correct
20 Correct 2 ms 1884 KB Output is correct
21 Correct 2 ms 1884 KB Output is correct
22 Correct 3 ms 1884 KB Output is correct
23 Correct 2 ms 1876 KB Output is correct
24 Correct 2 ms 1876 KB Output is correct
25 Correct 2 ms 1876 KB Output is correct
26 Correct 2 ms 1876 KB Output is correct
27 Correct 2 ms 1876 KB Output is correct
28 Correct 2 ms 1876 KB Output is correct
29 Correct 3 ms 1876 KB Output is correct
30 Correct 3 ms 1876 KB Output is correct
31 Incorrect 2 ms 1880 KB Output isn't correct
32 Halted 0 ms 0 KB -