Submission #201811

#	Time	Username	Problem	Language	Result	Execution time	Memory
201811		EntityIT	Asceticism (JOI18_asceticism)	C++14	100 / 100	16 ms	1288 KiB

asceticism

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

const int mod = 1e9 + 7;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

struct Mint {
  int a;
  Mint(int _a = 0) : a(_a) {}
  friend ostream& operator << (ostream &out, const Mint &_) {
    out << _.a;
    return out;
  }

  bool operator == (const Mint &_) const { return a == _.a; }
  bool operator ! () const { return !a; }

  Mint operator + (const Mint &_) const {
    int ret = a + _.a;
    return ret < mod ? Mint(ret) : Mint(ret - mod);
  }
  Mint operator - (const Mint &_) const { return *this + Mint(mod - _.a); }
  Mint operator * (const Mint &_) const { return Mint( (int)( (LL)a * _.a % mod) ); }
  friend Mint& operator += (Mint &a, const Mint &b) { return a = a + b; }
  friend Mint& operator -= (Mint &a, const Mint &b) { return a = a - b; }
  friend Mint& operator *= (Mint &a, const Mint &b) { return a = a * b; }
  Mint& operator ++ () { return *this = *this + Mint(1); }
  Mint& operator -- () { return *this = *this - Mint(1); }

  template<class T> Mint binPow(T exp) const {
    Mint ret(1), c = *this;
    for (; exp; exp >>= 1, c *= c) if (exp & 1) ret *= c;
    return ret;
  }
};
vector<Mint> fact, invFact;
Mint binomial(int n, int k) { return fact[n] * invFact[k] * invFact[n - k]; }

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  int n, k; cin >> n >> k;

  fact.assign(n + 2, Mint() );
  fact[0] = Mint(1); for (int i = 1; i < sz(fact); ++i) fact[i] = fact[i - 1] * Mint(i);
  invFact.assign(sz(fact), Mint() );
  invFact.back() = fact.back().binPow<int>(mod - 2);
  for (int i = sz(invFact) - 2; i >= 0; --i) invFact[i] = invFact[i + 1] * Mint(i + 1);

  Mint ans;
  for (int i = 0; i < k; ++i) {
    if (i & 1) ans -= binomial(n + 1, i) * Mint(k - i).binPow<int>(n);
    else ans += binomial(n + 1, i) * Mint(k - i).binPow<int>(n);
  }

  cout << ans << '\n';

  return 0;
}

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