QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#179860#384. 泳池hos_lyric#100 ✓142ms7764kbC++145.6kb2023-09-15 11:04:522023-09-15 11:04:52

Judging History

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

  • [2023-09-15 11:04:52]
  • 评测
  • 测评结果:100
  • 用时:142ms
  • 内存:7764kb
  • [2023-09-15 11:04:52]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;



Mint Q;
Mint QQ[1010];

Mint dp[1010][1010];

int D;
vector<Mint> C;
// x^e mod C
vector<Mint> power(int e) {
  if (e == 0) {
    vector<Mint> ret(D, 0);
    ret[0] = 1;
    return ret;
  } else if (e & 1) {
    auto ret = power(e - 1);
    ret.insert(ret.begin(), 0);
    for (int j = 1; j <= D; ++j) {
      ret[D - j] -= C[j] * ret[D];
    }
    ret.resize(D);
    return ret;
  } else {
    const auto res = power(e >> 1);
    vector<Mint> ret(2*D, 0);
    for (int i = 0; i < D; ++i) for (int j = 0; j < D; ++j) {
      ret[i + j] += res[i] * res[j];
    }
    for (int i = 2*D; --i >= D; ) {
      for (int j = 1; j <= D; ++j) {
        ret[i - j] -= C[j] * ret[i];
      }
    }
    ret.resize(D);
    return ret;
  }
}

Mint solve(int N, int K) {
  memset(dp, 0, sizeof(dp));
  for (int h = K; h >= 0; --h) {
    const int lim = h ? (K / h) : K;
    const int lim1 = K / (h + 1);
    dp[h][0] = 1;
    for (int n = 1; n <= lim; ++n) {
      for (int m = 1; m <= lim1 && m < n; ++m) {
        dp[h][n] += dp[h][n - m - 1] * QQ[m] * (1 - Q) * dp[h + 1][m];
      }
      if (n <= lim1) {
        dp[h][n] += dp[h][0] * QQ[n] * dp[h + 1][n];
      }
      dp[h][n] += dp[h][n - 1] * (1 - Q);
    }
  }
  D = K + 1;
  C.assign(D + 1, 0);
  for (int m = 1; m <= K; ++m) {
    C[m + 1] -= QQ[m] * (1 - Q) * dp[1][m];
  }
  C[1] -= (1 - Q);
  C[0] = 1;
  const auto res = power(N);
  Mint ans = 0;
  for (int i = 0; i < D; ++i) {
    ans += dp[0][i] * res[i];
  }
  return ans;
}

int main() {
  int N, K;
  Mint X, Y;
  for (; ~scanf("%d%d%u%u", &N, &K, &X.x, &Y.x); ) {
    Q = X / Y;
    QQ[0] = 1;
    for (int i = 1; i <= K; ++i) {
      QQ[i] = QQ[i - 1] * Q;
    }
    Mint ans = 0;
    ans += solve(N, K);
    ans -= solve(N, K - 1);
    printf("%u\n", ans.x);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 7ms
memory: 7724kb

input:

1 949 139078994 990651604

output:

330219622

result:

ok single line: '330219622'

Test #2:

score: 5
Accepted
time: 7ms
memory: 7680kb

input:

1 944 145496294 755116222

output:

930631836

result:

ok single line: '930631836'

Test #3:

score: 5
Accepted
time: 3ms
memory: 7660kb

input:

10 8 144842939 146358488

output:

375036401

result:

ok single line: '375036401'

Test #4:

score: 5
Accepted
time: 1ms
memory: 7672kb

input:

10 9 147875518 748368567

output:

709619968

result:

ok single line: '709619968'

Test #5:

score: 5
Accepted
time: 2ms
memory: 7696kb

input:

10 10 149567138 375202482

output:

38319127

result:

ok single line: '38319127'

Test #6:

score: 5
Accepted
time: 1ms
memory: 7716kb

input:

947 7 151913594 368520363

output:

141204133

result:

ok single line: '141204133'

Test #7:

score: 5
Accepted
time: 0ms
memory: 7740kb

input:

987 8 153223269 950558887

output:

846391446

result:

ok single line: '846391446'

Test #8:

score: 5
Accepted
time: 2ms
memory: 7764kb

input:

970 9 154292819 361838243

output:

181568951

result:

ok single line: '181568951'

Test #9:

score: 5
Accepted
time: 1ms
memory: 7668kb

input:

980 97 156846631 527638170

output:

20802473

result:

ok single line: '20802473'

Test #10:

score: 5
Accepted
time: 1ms
memory: 7668kb

input:

966 98 157883413 937194648

output:

179742710

result:

ok single line: '179742710'

Test #11:

score: 5
Accepted
time: 1ms
memory: 7672kb

input:

967 99 159400444 542443155

output:

238231981

result:

ok single line: '238231981'

Test #12:

score: 5
Accepted
time: 46ms
memory: 7736kb

input:

989 948 161746901 535761035

output:

876635506

result:

ok single line: '876635506'

Test #13:

score: 5
Accepted
time: 52ms
memory: 7672kb

input:

942 978 162609094 923732105

output:

236028500

result:

ok single line: '236028500'

Test #14:

score: 5
Accepted
time: 44ms
memory: 7688kb

input:

982 942 141042310 163263932

output:

741489934

result:

ok single line: '741489934'

Test #15:

score: 5
Accepted
time: 2ms
memory: 7728kb

input:

999971965 10 166090637 328362110

output:

412492049

result:

ok single line: '412492049'

Test #16:

score: 5
Accepted
time: 2ms
memory: 7672kb

input:

999975613 10 167334775 910367865

output:

8045707

result:

ok single line: '8045707'

Test #17:

score: 5
Accepted
time: 1ms
memory: 7720kb

input:

999975485 96 168371557 321679990

output:

549861210

result:

ok single line: '549861210'

Test #18:

score: 5
Accepted
time: 2ms
memory: 7684kb

input:

999980766 100 77923439 169888588

output:

278412314

result:

ok single line: '278412314'

Test #19:

score: 5
Accepted
time: 142ms
memory: 7692kb

input:

999993900 993 170990906 487479917

output:

265726301

result:

ok single line: '265726301'

Test #20:

score: 5
Accepted
time: 137ms
memory: 7696kb

input:

999974266 969 172060456 897003626

output:

219439784

result:

ok single line: '219439784'

Extra Test:

score: 0
Extra Test Passed