Submission #220626

#	Time	Username	Problem	Language	Result	Execution time	Memory
220626		rama_pang	Asceticism (JOI18_asceticism)	C++14	100 / 100	51 ms	1152 KiB

asceticism

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

void RADD(int &a, int b) {
  if ((a += b) >= MOD) a -= MOD;
  if (a < 0) a += MOD;
}

int MUL(int a, int b) {
  return 1ll * a * b % MOD;
}

int PushDP(int N, int K) { // O(N^2) DP solution
  vector<vector<int>> dp(N + 1, vector<int>(K + 2, 0));
  dp[0][0] = 1; // dp[i][j] = answer for N = i and K = j
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= K; j++) {
      // There are j positions where we insert at back, K doesn't increase
      RADD(dp[i + 1][j], MUL(dp[i][j], j)); 

      // Among i+1 possible places to be inserted, inserting other than the back increases K, 
      // of which there are (i + 1 - j) positions.
      RADD(dp[i + 1][j + 1], MUL(dp[i][j], i + 1 - j)); 
    }
  }
  return dp[N][K];
}

int PullDP(int N, int K) { // O(N^2) DP solution
  vector<vector<int>> dp(N + 1, vector<int>(K + 2, 0));
  dp[0][0] = 1; // dp[i][j] = answer for N = i and K = j
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= K; j++) {
      RADD(dp[i][j], MUL(dp[i - 1][j], j));
      RADD(dp[i][j], MUL(dp[i - 1][j - 1], i + 1 - j));
    }
  }
  return dp[N][K];
}

int Power(int n, int x) {
  if (x == 0) return 1;
  int res = Power(n, x / 2);
  res = MUL(res, res);
  if (x & 1) res = MUL(res, n);
  return res;
}

int Solve(int N, int K) { // O(N log N) combinatorial solution
  vector<int> fact(N + 2);
  vector<int> invfact(N + 2);

  invfact[0] = fact[0] = 1;
  for (int i = 1; i <= N + 1; i++) {
    fact[i] = MUL(i, fact[i - 1]);
    invfact[i] = Power(fact[i], MOD - 2); // by Fermat's Little Theorem
  }

  auto C = [&](int n, int k) { // binomial
    if (k < 0 || k > n) return 0;
    return MUL(fact[n], MUL(invfact[k], invfact[n - k]));
  };

  int ans = 0;

  // sum_{k = 0}^{K}((-1)^k * C(N + 1, k) * (K - k + 1)^N)
  for (int k = 0, sgn = 1; k < K; k++, sgn *= -1) {
    RADD(ans, sgn * MUL(C(N + 1, k), Power(K - k, N)));
  }

  return ans;
}

int main() {
  int N, K;
  cin >> N >> K;
  cout << Solve(N, K) << "\n";
  return 0;
}

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