Submission #1164181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164181		fryingduc	Asceticism (JOI18_asceticism)	C++20	100 / 100	9 ms	1288 KiB

asceticism

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int n, k;
int fact[maxn], inv[maxn];

int C(int n, int k) {
  if (n < k) return 0;
  return 1ll * fact[n] * inv[k] % mod * inv[n - k] % mod;
}

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

int power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return res;
}

void solve() {
  cin >> n >> k; --k;
  int res = 0;
  for (int i = 0; i <= k; ++i) {
    int cur = 1ll * C(n + 1, i) * power(k - i + 1, n) % mod;
    res = add(res, cur * (i & 1 ? -1 : 1));
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  fact[0] = inv[0] = 1;
  for (int i = 1; i < maxn; ++i) {
    fact[i] = 1ll * fact[i - 1] * i % mod;
  }
  inv[maxn - 1] = 931791584;
  debug(inv[maxn - 1]);
  for (int i = maxn - 2; i; --i) {
    inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
  }

  solve();

  return 0;
}

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