QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415177#7632. Balanced ArrayscaijianhongTL 18ms19248kbC++142.8kb2024-05-20 15:15:412024-05-20 15:15:41

Judging History

你现在查看的是最新测评结果

  • [2024-05-20 15:15:41]
  • 评测
  • 测评结果:TL
  • 用时:18ms
  • 内存:19248kb
  • [2024-05-20 15:15:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
template <class T>
using must_int = enable_if_t<is_integral<T>::value, int>;
template <unsigned umod>
struct modint { /*{{{*/
  static constexpr int mod = umod;
  unsigned v;
  modint() : v(0) {}
  template <class T, must_int<T> = 0>
  modint(T x) {
    x %= mod;
    v = x < 0 ? x + mod : x;
  }
  modint operator+() const { return *this; }
  modint operator-() const { return modint() - *this; }
  friend int raw(const modint &self) { return self.v; }
  friend ostream &operator<<(ostream &os, const modint &self) {
    return os << raw(self);
  }
  modint &operator+=(const modint &rhs) {
    v += rhs.v;
    if (v >= umod) v -= umod;
    return *this;
  }
  modint &operator-=(const modint &rhs) {
    v -= rhs.v;
    if (v >= umod) v += umod;
    return *this;
  }
  modint &operator*=(const modint &rhs) {
    v = 1ull * v * rhs.v % umod;
    return *this;
  }
  modint &operator/=(const modint &rhs) {
    assert(rhs.v);
    return *this *= qpow(rhs, mod - 2);
  }
  template <class T, must_int<T> = 0>
  friend modint qpow(modint a, T b) {
    modint r = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) r *= a;
    return r;
  }
  friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
  friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
  friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
  friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
  bool operator==(const modint &rhs) const { return v == rhs.v; }
  bool operator!=(const modint &rhs) const { return v != rhs.v; }
}; /*}}}*/
typedef modint<998244353> mint;
template <int N>
struct C_prime { /*{{{*/
  mint fac[N + 10], ifac[N + 10];
  C_prime() {
    for (int i = raw(fac[0] = 1); i <= N; i++) fac[i] = fac[i - 1] * i;
    ifac[N] = 1 / fac[N];
    for (int i = N; i >= 1; i--) ifac[i - 1] = ifac[i] * i;
  }
  mint operator()(int n, int m) {
    return n >= m ? fac[n] * ifac[m] * ifac[n - m] : 0;
  }
}; /*}}}*/
int n, m;
C_prime<2000010> binom;
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n >> m;
  mint ans = 1;
  for (int i = 1; i <= m; i++) {
    for (int k = 1; k <= i; k++) {
      ans += binom(i - 1, k - 1) * binom(i, k - 1) *
             binom(n - 2 * k + 2 * i + 1, 2 * i) * binom.ifac[k] * binom.fac[k - 1];
      debug("i = %d, k = %d, p1 = %d / %d, p2 = %d\n", i, k, raw(binom(i - 1, k - 1) * binom(i, k - 1)), k, raw(binom(n - 2 * k + 2 * i +1, 2 * i )));
    }
  }
  cout << ans << endl;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 18ms
memory: 19248kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: -100
Time Limit Exceeded

input:

500000 500000

output:


result: