Submission #685059

#	Time	Username	Problem	Language	Result	Execution time	Memory
685059		peijar	Asceticism (JOI18_asceticism)	C++17	49 / 100	9 ms	1896 KiB

asceticism

#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 = N - 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 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 51