QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#316250#8171. Colaucup-team1191#AC ✓872ms81268kbC++238.2kb2024-01-27 18:48:412024-01-27 18:48:42

Judging History

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

  • [2024-01-27 18:48:42]
  • 评测
  • 测评结果:AC
  • 用时:872ms
  • 内存:81268kb
  • [2024-01-27 18:48:41]
  • 提交

answer

#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T> class Modular {
public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U> Modular(const U &x) { value = normalize(x); }

  template <typename U> static Type normalize(const U &x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0)
      v += mod();
    return v;
  }

  const Type &operator()() const { return value; }
  template <typename U> explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }

  Modular &operator+=(const Modular &other) {
    if ((value += other.value) >= mod())
      value -= mod();
    return *this;
  }
  Modular &operator-=(const Modular &other) {
    if ((value -= other.value) < 0)
      value += mod();
    return *this;
  }
  template <typename U> Modular &operator+=(const U &other) {
    return *this += Modular(other);
  }
  template <typename U> Modular &operator-=(const U &other) {
    return *this -= Modular(other);
  }
  Modular &operator++() { return *this += 1; }
  Modular &operator--() { return *this -= 1; }
  Modular operator++(int) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(int) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                     Modular>::type &
  operator*=(const Modular &rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, long long>::value,
                     Modular>::type &
  operator*=(const Modular &rhs) {
    long long q = static_cast<long long>(static_cast<long double>(value) *
                                         rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type &
  operator*=(const Modular &rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }

  Modular &operator/=(const Modular &other) {
    return *this *= Modular(inverse(other.value, mod()));
  }

  friend const Type &abs(const Modular &x) { return x.value; }

  template <typename U>
  friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);

  template <typename U>
  friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);

  template <typename V, typename U>
  friend V &operator>>(V &stream, Modular<U> &number);

private:
  Type value;
};

template <typename T>
bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T> &lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) == rhs;
}

template <typename T>
bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T> &lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T> &rhs) {
  return !(lhs == rhs);
}

template <typename T>
bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) {
  return lhs.value < rhs.value;
}

template <typename T>
Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) += rhs;
}

template <typename T>
Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) -= rhs;
}

template <typename T>
Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) *= rhs;
}

template <typename T>
Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) /= rhs;
}

template <typename T, typename U>
Modular<T> power(const Modular<T> &a, const U &b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1)
      res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}

template <typename T> bool IsZero(const Modular<T> &number) {
  return number() == 0;
}

template <typename T> string to_string(const Modular<T> &number) {
  return to_string(number());
}

// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U &operator<<(U &stream, const Modular<T> &number) {
  return stream << number();
}

// U == std::istream? but done this way because of fastinput
template <typename U, typename T> U &operator>>(U &stream, Modular<T> &number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

/*
using ModType = int;

struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

/*vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);

Mint C(int n, int k) {
  if (k < 0 || k > n) {
    return 0;
  }
  while ((int) fact.size() < n + 1) {
    fact.push_back(fact.back() * (int) fact.size());
    inv_fact.push_back(1 / fact.back());
  }
  return fact[n] * inv_fact[k] * inv_fact[n - k];
}*/

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  m -= 1;
  vector<Mint> pent_coeff(m + 1);
  pent_coeff[0] = 1;
  for (int k = 1;; ++k) {
    int sign = (k & 1) ? -1 : 1;
    int t1 = k * (3 * k - 1) / 2;
    int t2 = k * (3 * k + 1) / 2;
    if (t1 > m) {
      break;
    }
    pent_coeff[t1] += sign;
    if (t2 <= m) {
      pent_coeff[t2] += sign;
    }
  }
  vector<Mint> inv(m + 1);
  inv[1] = 1;
  for (int i = 2; i <= m; ++i) {
    inv[i] = -inv[md % i] * (md / i);
  }

  int pw = -(n + 1);
  int ptr = 1;
  Mint coef = 1;
  Mint ans = 0;

  for (int i = m; i >= 0; --i) {
    ans += pent_coeff[i] * coef;
    coef *= inv[ptr++];
    coef *= pw;
    pw -= 1;
    coef *= -1;
  }

  for (int i = 0; i < n; ++i) {
    ans *= 1 / Mint(n - i);
  }
  cout << ans << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

2 1

output:

499122177

result:

ok "499122177"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

1 1

output:

1

result:

ok "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

167 91

output:

469117530

result:

ok "469117530"

Test #4:

score: 0
Accepted
time: 818ms
memory: 73376kb

input:

9806463 8975779

output:

125384417

result:

ok "125384417"

Test #5:

score: 0
Accepted
time: 756ms
memory: 71456kb

input:

9138576 8731432

output:

306972756

result:

ok "306972756"

Test #6:

score: 0
Accepted
time: 834ms
memory: 73760kb

input:

9978791 9033584

output:

932159263

result:

ok "932159263"

Test #7:

score: 0
Accepted
time: 832ms
memory: 79608kb

input:

9811954 9790000

output:

404679920

result:

ok "404679920"

Test #8:

score: 0
Accepted
time: 821ms
memory: 75520kb

input:

9685105 9276909

output:

32996715

result:

ok "32996715"

Test #9:

score: 0
Accepted
time: 857ms
memory: 81208kb

input:

10000000 10000000

output:

309225852

result:

ok "309225852"

Test #10:

score: 0
Accepted
time: 848ms
memory: 81208kb

input:

10000000 9999999

output:

635234302

result:

ok "635234302"

Test #11:

score: 0
Accepted
time: 850ms
memory: 81128kb

input:

10000000 9999998

output:

239117935

result:

ok "239117935"

Test #12:

score: 0
Accepted
time: 850ms
memory: 81116kb

input:

10000000 9999997

output:

294859983

result:

ok "294859983"

Test #13:

score: 0
Accepted
time: 848ms
memory: 81120kb

input:

9999999 9999999

output:

305530110

result:

ok "305530110"

Test #14:

score: 0
Accepted
time: 864ms
memory: 81264kb

input:

9999999 9999998

output:

164959553

result:

ok "164959553"

Test #15:

score: 0
Accepted
time: 854ms
memory: 81224kb

input:

9999999 9999997

output:

532215262

result:

ok "532215262"

Test #16:

score: 0
Accepted
time: 849ms
memory: 81208kb

input:

9999999 9999996

output:

123628609

result:

ok "123628609"

Test #17:

score: 0
Accepted
time: 853ms
memory: 81140kb

input:

9999998 9999998

output:

223852357

result:

ok "223852357"

Test #18:

score: 0
Accepted
time: 852ms
memory: 81136kb

input:

9999998 9999997

output:

75877991

result:

ok "75877991"

Test #19:

score: 0
Accepted
time: 872ms
memory: 81268kb

input:

9999998 9999996

output:

494540335

result:

ok "494540335"

Test #20:

score: 0
Accepted
time: 865ms
memory: 81124kb

input:

9999998 9999995

output:

19191738

result:

ok "19191738"

Test #21:

score: 0
Accepted
time: 859ms
memory: 81212kb

input:

9999997 9999997

output:

238385746

result:

ok "238385746"

Test #22:

score: 0
Accepted
time: 858ms
memory: 81160kb

input:

9999997 9999996

output:

138191521

result:

ok "138191521"

Test #23:

score: 0
Accepted
time: 854ms
memory: 81120kb

input:

9999997 9999995

output:

721536184

result:

ok "721536184"

Test #24:

score: 0
Accepted
time: 861ms
memory: 81164kb

input:

9999997 9999994

output:

627112720

result:

ok "627112720"

Test #25:

score: 0
Accepted
time: 559ms
memory: 17568kb

input:

8113616 1826492

output:

629546539

result:

ok "629546539"

Test #26:

score: 0
Accepted
time: 550ms
memory: 36248kb

input:

7230333 4233627

output:

870135249

result:

ok "870135249"

Test #27:

score: 0
Accepted
time: 821ms
memory: 78360kb

input:

9734872 9617286

output:

780426509

result:

ok "780426509"

Test #28:

score: 0
Accepted
time: 560ms
memory: 53048kb

input:

6780022 6393958

output:

508662111

result:

ok "508662111"

Test #29:

score: 0
Accepted
time: 353ms
memory: 17996kb

input:

4986441 1909344

output:

762587564

result:

ok "762587564"

Test #30:

score: 0
Accepted
time: 653ms
memory: 3852kb

input:

9936540 91728

output:

651924678

result:

ok "651924678"

Test #31:

score: 0
Accepted
time: 597ms
memory: 3868kb

input:

9099529 94239

output:

775532638

result:

ok "775532638"

Test #32:

score: 0
Accepted
time: 628ms
memory: 3928kb

input:

9564814 93545

output:

474538902

result:

ok "474538902"

Test #33:

score: 0
Accepted
time: 638ms
memory: 3852kb

input:

9707744 92094

output:

354024226

result:

ok "354024226"

Test #34:

score: 0
Accepted
time: 600ms
memory: 3852kb

input:

9167687 94820

output:

858989558

result:

ok "858989558"

Test #35:

score: 0
Accepted
time: 658ms
memory: 3852kb

input:

10000000 100000

output:

609345536

result:

ok "609345536"

Test #36:

score: 0
Accepted
time: 655ms
memory: 3876kb

input:

10000000 99999

output:

217258255

result:

ok "217258255"

Test #37:

score: 0
Accepted
time: 659ms
memory: 3884kb

input:

10000000 99998

output:

485057696

result:

ok "485057696"

Test #38:

score: 0
Accepted
time: 656ms
memory: 4008kb

input:

10000000 99997

output:

193579142

result:

ok "193579142"

Test #39:

score: 0
Accepted
time: 655ms
memory: 3844kb

input:

9999999 100000

output:

584105896

result:

ok "584105896"

Test #40:

score: 0
Accepted
time: 658ms
memory: 4012kb

input:

9999999 99999

output:

707014865

result:

ok "707014865"

Test #41:

score: 0
Accepted
time: 659ms
memory: 4020kb

input:

9999999 99998

output:

872987417

result:

ok "872987417"

Test #42:

score: 0
Accepted
time: 658ms
memory: 3840kb

input:

9999999 99997

output:

707304988

result:

ok "707304988"

Test #43:

score: 0
Accepted
time: 658ms
memory: 3864kb

input:

9999998 100000

output:

789028925

result:

ok "789028925"

Test #44:

score: 0
Accepted
time: 659ms
memory: 4012kb

input:

9999998 99999

output:

628266237

result:

ok "628266237"

Test #45:

score: 0
Accepted
time: 658ms
memory: 3840kb

input:

9999998 99998

output:

38358057

result:

ok "38358057"

Test #46:

score: 0
Accepted
time: 658ms
memory: 4012kb

input:

9999998 99997

output:

785931240

result:

ok "785931240"

Test #47:

score: 0
Accepted
time: 660ms
memory: 3852kb

input:

9999997 100000

output:

945452715

result:

ok "945452715"

Test #48:

score: 0
Accepted
time: 658ms
memory: 3940kb

input:

9999997 99999

output:

537126025

result:

ok "537126025"

Test #49:

score: 0
Accepted
time: 659ms
memory: 3848kb

input:

9999997 99998

output:

837196653

result:

ok "837196653"

Test #50:

score: 0
Accepted
time: 657ms
memory: 3848kb

input:

9999997 99997

output:

263045713

result:

ok "263045713"

Test #51:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

2 2

output:

1

result:

ok "1"

Test #52:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

3 3

output:

831870295

result:

ok "831870295"

Test #53:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

4 4

output:

374341633

result:

ok "374341633"

Test #54:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

3 2

output:

499122177

result:

ok "499122177"

Test #55:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

4 3

output:

623902721

result:

ok "623902721"

Test #56:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5 4

output:

890101215

result:

ok "890101215"

Test #57:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

3 1

output:

166374059

result:

ok "166374059"

Test #58:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

4 2

output:

166374059

result:

ok "166374059"

Test #59:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5 3

output:

16637406

result:

ok "16637406"

Test #60:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

6 4

output:

508827330

result:

ok "508827330"

Test #61:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

4 1

output:

291154603

result:

ok "291154603"

Test #62:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

5 2

output:

291154603

result:

ok "291154603"

Test #63:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

6 3

output:

859599304

result:

ok "859599304"

Test #64:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

7 4

output:

694809760

result:

ok "694809760"

Test #65:

score: 0
Accepted
time: 356ms
memory: 3640kb

input:

5629201 38642

output:

327294391

result:

ok "327294391"

Test #66:

score: 0
Accepted
time: 2ms
memory: 3632kb

input:

126092 74219

output:

27573951

result:

ok "27573951"

Test #67:

score: 0
Accepted
time: 560ms
memory: 3676kb

input:

8593075 8689

output:

393785113

result:

ok "393785113"

Test #68:

score: 0
Accepted
time: 60ms
memory: 3668kb

input:

1076972 58637

output:

600806929

result:

ok "600806929"

Test #69:

score: 0
Accepted
time: 27ms
memory: 3648kb

input:

463217 39187

output:

408712022

result:

ok "408712022"

Extra Test:

score: 0
Extra Test Passed