QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#655809#9476. 012 Griducup-team3931#RE 216ms27148kbC++2012.6kb2024-10-19 09:46:032024-10-19 09:46:03

Judging History

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

  • [2024-10-19 09:46:03]
  • 评测
  • 测评结果:RE
  • 用时:216ms
  • 内存:27148kb
  • [2024-10-19 09:46:03]
  • 提交

answer

#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

namespace Math {
  constexpr int P = 998244353;
  constexpr int G = 3;

  #ifdef _WIN32
  using uint = uint32_t;
  #endif
  using ull = uint64_t;
  
  using cint = const int;

  template<class T>
  IL void qm (T &x) {
    x += (x >> 31) & P; 
  }
  template<class T>
  IL T nor (const T &x) { 
    return x + ((x >> 31) & P); 
  }
  template<class T>
  IL T fix (T x) { 
    return nor(x %= P); 
  }

  IL int qpow (int b, int k) {
    int r = 1;
    for (; k; k >>= 1, b = (ull)b * b % P) if (k & 1) r = (ull)r * b % P;
    return r;
  }

  namespace FFT {
    constexpr int N = 1 << 20;
    int n, lg, root[N];
    
    IL void init (cint z) {
      n = 1, lg = 0;
      while (n <= z) {
        n <<= 1;
        ++lg;
      }
      assert(n <= N);
      ull w = qpow(G, (P - 1) / n);
      root[0] = 1;
      for (int i = 1; i < n; ++i) {
        root[i] = root[i - 1] * w % P;
      }
    }

    template<typename T>
    IL void DIF (T *a) {
      static int *i, *j;
      for (int l = n; l > 1; l >>= 1) {
        cint m = l >> 1;
        for (i = a; i != a + n; i += l) {
          int *w = root;
          for (j = i; j != i + m; ++j, w += n / l) {
            T t = nor(*j + j[m] - P);
            j[m] = (ull)*w * (*j - j[m] + P) % P;
            *j = t;
          }
        }
      }
    }

    template<typename T>
    IL void DIT (T *a) {
      static int *i, *j;
      for (int l = 2; l <= n; l <<= 1) {
        cint m = l >> 1;
        for (i = a; i != a + n; i += l) {
          int *w = root;
          for (j = i; j != i + m; ++j, w += n / l) {
            T t = (ull)*w * j[m] % P;
            qm(j[m] = *j - t);
            qm(*j += t - P);
          }
        }
      }
      T iv = P - (P - 1) / n;
      reverse(a + 1, a + n);
      for (int i = 0; i < n; i++) {
        a[i] = (ull)a[i] * iv % P;
      }
    }
  }

  using FFT::init;
  using FFT::DIF;
  using FFT::DIT;

  struct Poly {
    vector<int> a;

    Poly () : a(1) {}

    Poly (int v) { fix(v); a = {v}; }

    Poly (vector<int> &a) : a(a) {}
    Poly (initializer_list<int> a) : a(a) {}

    int operator [] (uint p) const {
      return p < a.size() ? a[p] : 0;
    }
    int& operator [] (uint p) {
      return p < a.size() ? a[p] : (a.resize(p + 1), a[p]);
    }

    const size_t deg () const { return a.size() - 1; }
    const size_t size () const { return a.size(); }
    int *base () { return a.data(); }
    cint *base () const { return a.data(); }
    void redeg (size_t d) { a.resize(d + 1); }
    void resize (size_t sz) { a.resize(sz); }

    Poly slice (int d) const {
      if (d < (int)(a.size())) {
        vector<int> r(a.begin(), a.begin() + d);
        return r;
      }
      vector<int> r(a);
      r.resize(d);
      return r;
    }

    Poly operator + (const Poly &z) const {
      vector<int> r(max(a.size(), z.a.size()));
      for (int i = 0; i < (int)(r.size()); i++) {
        qm(r[i] = operator[](i) + z[i] - P);
      }
      return r;
    }

    Poly operator - (const Poly &z) const {
      vector<int> r(max(a.size(), z.a.size()));
      for (int i = 0; i < (int)(r.size()); i++) {
        qm(r[i] = operator[](i) - z[i]);
      }
      return r;
    }

    Poly operator - () const {
      vector<int> r(a);
      for (auto &v : r) {
        if (v) {
          v = P - v;
        }
      }
      return r;
    }

    Poly deriv () const {
      int _n = deg();
      if (!_n) {
        return 0;
      } else {
        vector<int> r(_n);
        for (int i = 0; i < _n; i++) {
          r[i] = (ull)a[i + 1] * (i + 1) % P;
        }
        return r;
      }
    }

    Poly integ () const {
      static vector<int> iv{0, 1};
      int _n = size();
      if (_n >= (int)(iv.size())) {
        int _m = iv.size();
        iv.resize(_n + 1);
        for (int i = _m; i <= _n; i++) {
          iv[i] = (ull)iv[P % i] * (P - P / i) % P;
        }
      }
      vector<int> r(_n + 1);
      for (int i = 1; i <= _n; i++) {
        r[i] = (ull)a[i - 1] * iv[i] % P;
      }
      return r;
    }

    Poly T () const {
      Poly z = *this;
      reverse(z.a.begin(), z.a.end());
      return z;
    }

    Poly operator * (const Poly &z) const;

    Poly inv () const;

    Poly operator / (const Poly &z) const {
      size_t n = deg(), m = z.deg();
      if (n < m) {
        return Poly();
      }
      Poly F = T(), G = z.T();
      F.redeg(n - m), G.redeg(n - m);
      Poly Q = F * G.inv();
      Q.redeg(n - m);
      return Q.T();
    }

    Poly operator % (const Poly &z) const {
      Poly R = *this - *this / z * z;
      R.resize(z.deg());
      return R;
    }
    
    Poly& operator += (const Poly &z) { (*this) = (*this) + z; return *this; }
    Poly& operator -= (const Poly &z) { (*this) = (*this) - z; return *this; }
    Poly& operator *= (const Poly &z) { (*this) = (*this) * z; return *this; }
    Poly& operator /= (const Poly &z) { (*this) = (*this) / z; return *this; }
    Poly& operator %= (const Poly &z) { (*this) = (*this) % z; return *this; }

    Poly ln () const;
    Poly exp () const;
    Poly sqrt () const;

    Poly pow (int k) const {
      Poly b = *this, r = 1;
      for (; k; k >>= 1, b *= b) if (k & 1) r *= b;
      return r;
    }
  };

  IL Poly _bfmul (const Poly &a, const Poly &b) {
    int n = a.size(), m = b.size();
    vector<int> c(n + m - 1);
    for (int i = 0; i < n; i++) {
      if (a[i]) {
        for (int j = 0; j < m; j++) {
          c[i + j] = (c[i + j] + (ull)a[i] * b[j]) % P;
        }
      }
    }
    return c;
  }

  IL Poly _mul (Poly a, Poly b) {
    int n = a.size() + b.size() - 1;
    FFT::init(n);
    int _n = FFT::n;
    a.resize(_n);
    b.resize(_n);
    DIF(a.base());
    DIF(b.base());
    Poly c(a);
    for (int i = 0; i < _n; i++) {
      c[i] = (ull)c[i] * b[i] % P;
    }
    DIT(c.base());
    c.resize(n);
    return c;
  }

  Poly Poly::operator* (const Poly &z) const {
    int n = a.size(), m = z.size();
    if (n <= 32 || m <= 32) {
      return _bfmul(*this, z);
    } else {
      return _mul(*this, z);
    }
  }

  namespace internal {
    namespace Cipolla {
      int w;
      struct Complex {
        int r, i;
        Complex (int r = 0, int i = 0) : r(r), i(i) {}
        Complex operator * (const Complex &rhs) const {
          return Complex(((LL)r * rhs.r + (LL)i * rhs.i % P * w) % P, 
            ((LL)r * rhs.i + (LL)i * rhs.r) % P);
        }
        Complex pow (int k) const {
          Complex r(1, 0), b(*this);
          for (; k; k >>= 1, b = b * b) if (k & 1) r = r * b;
          return r;
        }
      };

      mt19937 rng(random_device{}());

      int Cipolla (int a) {
        int b;
        do {
          b = rng() % P;
          w = ((LL)b * b + P - a) % P;
        } while (b == 0 || qpow(w, (P - 1) / 2) == 1);
        int z = Complex(b, 1).pow((P + 1) / 2).r;
        return min(z, P - z);
      }
    }
  }

  namespace Newton {
    using FFT::init;
    using FFT::DIF;
    using FFT::DIT;

    IL void inv (const Poly &f, Poly &g, cint l) {
      if (l == 1) {
        g = qpow(f[0], P - 2);
        return;
      }
      inv(f, g, (l + 1) >> 1);
      init(l << 1);
      int _n = FFT::n;
      Poly a = f.slice(l), b = g.slice(l);
      a.resize(_n);
      b.resize(_n);
      DIF(a.base());
      DIF(b.base());
      vector<int> c(_n);
      for (int i = 0; i < _n; i++) {
        qm(c[i] = (int)((2 - (LL)a[i] * b[i]) % P * b[i] % P));
      }
      DIT(c.data());
      g = Poly(c).slice(l);
    }
    
    IL void exp (const Poly &f, Poly &g, cint l) {
      if (l == 1) {
        assert(f[0] == 0);
        g = 1;
        return;
      }
      exp(f, g, (l + 1) >> 1);
      Poly a = f.slice(l), b = g.slice(l);
      Poly c = b * (Poly(1) - b.ln() + a);
      g = c.slice(l);
    }

    IL void sqrt (const Poly &f, Poly &g, cint l) {
      if (l == 1) {
        g = internal::Cipolla::Cipolla(f[0]);
        return;
      }
      sqrt(f, g, (l + 1) >> 1);
      Poly a = f.slice(l), b = g.slice(l);
      Poly c = (a + b * b) * (b * 2).inv();
      g = c.slice(l);
    }
  }

  Poly Poly::inv () const {
    Poly s;
    Newton::inv(*this, s, size());
    return s;
  }

  Poly Poly::ln () const {
    assert(a[0] == 1);
    Poly s = (deriv() * inv()).integ();
    s.redeg(deg());
    return s;
  }

  Poly Poly::exp () const {
    Poly s;
    Newton::exp(*this, s, size());
    return s;
  }

  Poly Poly::sqrt() const {
    assert(qpow(a[0], (P - 1) / 2) == 1);
    Poly s;
    Newton::sqrt(*this, s, size());
    return s;
  }

  namespace Ext {
    vector<int> _eval (const Poly &f, const vector<int> &a, cint &n) {
      static Poly t[1 << 20];
      
      auto mul = [] (Poly a, Poly b) {
        int n = a.size(), m = b.size();
        reverse(b.a.begin(), b.a.end());
        b *= a;
        for (int i = 0; i < n; ++i) {
          a[i] = b[m + i - 1];
        }
        return a;
      };

      auto dfs = [&] (auto self, int l, int r, int p) -> void {
        if (r - l == 1) {
          t[p] = {1, P - a[l]};
          return;
        }
        int m = (l + r) >> 1;
        self(self, l, m, p << 1);
        self(self, m, r, p << 1 | 1);
        t[p] = t[p << 1] * t[p << 1 | 1];
      };
      dfs(dfs, 0, n, 1);

      vector<int> b(n);
      auto conq = [&] (auto self, int l, int r, int p) -> void {
        t[p].resize(r - l);
        if (r - l == 1) {
          b[l] = t[p][0];
          return;
        }
        int m = (l + r) >> 1;
        tie(t[p << 1], t[p << 1 | 1]) = 
          make_pair(mul(t[p], t[p << 1 | 1]), mul(t[p], t[p << 1]));
        t[p] = Poly();
        self(self, l, m, p << 1);
        self(self, m, r, p << 1 | 1);
      };
      t[1] = mul(f, t[1].inv());
      conq(conq, 0, n, 1);

      return b;
    }

    vector<int> eval (const Poly &f, const vector<int> &a) {
      int n = f.size(), m = a.size();
      auto tf = f;
      auto ta = a;
      n = max(n, m);
      tf.resize(n);
      ta.resize(n);
      auto b = _eval(tf, ta, n);
      b.resize(m);
      return b;
    }
  }
}

using Math::Poly;

constexpr int P = 998244353;

IL constexpr int qpow (int b, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, b = (LL)b * b % P) if (k & 1) r = (LL)r * b % P;
  return r;
}

constexpr int N = 2e5 + 9;
int n, m;

int fc[N << 2], ifc[N << 2];

void init (int Z) {
  fc[0] = 1;
  L (i, 1, Z) {
    fc[i] = (LL)fc[i - 1] * i % P;
  }
  ifc[Z] = qpow(fc[Z]);
  R (i, Z - 1, 0) {
    ifc[i] = (LL)ifc[i + 1] * (i + 1) % P;
  }
}

int C (int n, int m) {
  return n < m || m < 0 ? 0 : (LL)fc[n] * ifc[m] % P * ifc[n - m] % P;
}

int F (int n, int m) {
  return C(n + m, n);
}

int G (int n, int m) {
  return (F(n - 1, m - 1) * (LL)F(n - 1, m - 1) + (P - F(n - 2, m)) * (LL)F(n, m - 2)) % P;
}

int calc (int n) {
  return n < 0 ? 0 : (C(2 * n, n) + P - C(2 * n, n - 2)) % P;
}

Poly A, B;

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  init((n + m) << 1);
  LL ns = 0;
  L (i, 0, n - 2) {
    A[i] = (LL)ifc[i] * ifc[i] % P;
  }
  L (i, 0, m - 2) {
    B[i] = (LL)ifc[i] * ifc[i] % P;
  }
  A *= B;
  L (i, 0, n + m - 4) {
    ns = (ns + 2LL * A[i] * fc[i] % P * fc[i]) % P;
  }
  A.redeg(n - 2);
  B.redeg(m - 2);
  L (i, 0, n - 2) {
    A[i] = i ? (LL)ifc[i - 1] * ifc[i + 1] % P : 0;
  }
  L (i, 0, m - 2) {
    B[i] = i ? (LL)ifc[i - 1] * ifc[i + 1] % P : 0;
  }
  A *= B;
  L (i, 2, n + m - 4) {
    ns = (ns + (P - 2LL) * A[i] % P * fc[i] % P * fc[i]) % P;
  }
  A.redeg(n - 1);
  B.redeg(m - 1);
  L (i, 0, n - 1) {
    A[i] = !!i;
  }
  L (i, 0, m - 1) {
    B[i] = !!i;
  }
  A *= A;
  B *= B;
  L (i, 2, 2 * n - 2) {
    ns = (ns + (LL)A[i] * G(n - i, m)) % P;
  }
  L (i, 2, 2 * m - 2) {
    ns = (ns + (LL)B[i] * G(n, m - i)) % P;
  }
  L (i, 1, n - 1) {
    ns = (ns + 2LL * G(n - i, m)) % P;
  }
  L (i, 1, m - 1) {
    ns = (ns + 2LL * G(n, m - i)) % P;
  }
  ns = (ns + G(n, m)) % P;
  cout << (ns + 2) % P << '\n';
}
// I love WHQ!

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7680kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

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

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 202ms
memory: 24452kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 1ms
memory: 7680kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7956kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

score: 0
Accepted
time: 1ms
memory: 7732kb

input:

3 3

output:

64

result:

ok "64"

Test #7:

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

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 1ms
memory: 9688kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

score: 0
Accepted
time: 1ms
memory: 9684kb

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

score: 0
Accepted
time: 1ms
memory: 9768kb

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 1ms
memory: 10016kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 1ms
memory: 7932kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

score: 0
Accepted
time: 1ms
memory: 7964kb

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 4ms
memory: 12272kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

score: 0
Accepted
time: 3ms
memory: 10004kb

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

score: 0
Accepted
time: 6ms
memory: 12248kb

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 6ms
memory: 9908kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 3ms
memory: 10008kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

score: 0
Accepted
time: 3ms
memory: 12016kb

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

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

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

score: 0
Accepted
time: 4ms
memory: 10024kb

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 8ms
memory: 10176kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

score: 0
Accepted
time: 8ms
memory: 10084kb

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 199ms
memory: 26064kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 97ms
memory: 18644kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 80ms
memory: 18420kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 53ms
memory: 18552kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 204ms
memory: 27148kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 112ms
memory: 22768kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 107ms
memory: 22828kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 75ms
memory: 18116kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 75ms
memory: 19656kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 114ms
memory: 24204kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 207ms
memory: 25636kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 211ms
memory: 26964kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 216ms
memory: 26512kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

score: -100
Runtime Error

input:

1 1

output:


result: