Submission #218490

#	Time	Username	Problem	Language	Result	Execution time	Memory
218490		extraterrestrial	Asceticism (JOI18_asceticism)	C++14	100 / 100	37 ms	1976 KiB

asceticism

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

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

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

int b_pow(int a, int b) {
  if (!b) {
    return 1;
  }
  if (b & 1) {
    return mult(a, b_pow(a, b - 1));
  }
  return b_pow(mult(a, a), b >> 1);
}

int f[N], rf[N];

int C(int n, int k) {
  if (k < 0 || k > n) {
    return 0;
  }  
  return mult(f[n], mult(rf[k], rf[n - k]));
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
	int n, m;
  cin >> n >> m;
  m = n - m;  
  f[0] = rf[0] = 1;
  for (int i = 1; i <= n + 1; i++) {
    f[i] = mult(f[i - 1], i);
    rf[i] = b_pow(f[i], MOD - 2);
  }
  int ans = 0;
  for (int k = 0; k <= m; k++) {
    int vl = mult(C(n + 1, k), b_pow(m + 1 - k, n));
    if (k & 1) {
      vl = MOD - vl;
    }
    add(ans, vl);
  }
  cout << ans << '\n';
} 

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