QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61990#4822. Matrix Countingalpha1022AC ✓310ms21176kbC++1716.4kb2022-11-16 15:57:092022-11-16 15:57:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-16 15:57:12]
  • 评测
  • 测评结果:AC
  • 用时:310ms
  • 内存:21176kb
  • [2022-11-16 15:57:09]
  • 提交

answer

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

const int mod = 998244353, G = 3;
inline int norm(int x) {
  return x >= mod ? x - mod : x;
}
inline int reduce(int x) {
  return x < 0 ? x + mod : x;
}
inline int neg(int x) {
  return x ? mod - x : 0;
}
inline void add(int &x, int y) {
  if ((x += y - mod) < 0)
    x += mod;
}
inline void sub(int &x, int y) {
  if ((x -= y) < 0)
    x += mod;
}
inline void fam(int &x, int y, int z) {
  x = (x + (ll)y * z) % mod;
}
inline int mpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1)
    (b & 1) && (ret = (ll)ret * a % mod),
    a = (ll)a * a % mod;
  return ret;
}

const int BRUTE_N2_LIMIT = 50;

struct NumberTheory {
  typedef pair<int, int> P2_Field;
  mt19937 rng;
  NumberTheory(): rng(chrono::steady_clock::now().time_since_epoch().count()) {}
  void exGcd(int a, int b, int &x, int &y) {
    if (!b) {
      x = 1, y = 0;
      return;
    }
    exGcd(b, a % b, y, x), y -= a / b * x;
  }
  int inv(int a, int p = mod) {
    int x, y;
    exGcd(a, p, x, y);
    if (x < 0)
      x += p;
    return x;
  }
  template<class Integer>
  bool quadRes(Integer a, Integer b) {
    if (a <= 1)
      return 1;
    while (a % 4 == 0)
      a /= 4;
    if (a % 2 == 0)
      return (b % 8 == 1 || b % 8 == 7) == quadRes(a / 2, b);
    return ((a - 1) % 4 == 0 || (b - 1) % 4 == 0) == quadRes(b % a, a);
  }
  int sqrt(int x, int p = mod) {
    if (p == 2 || x <= 1)
      return x;
    int w, v, k = (p + 1) / 2;
    do
      w = rng() % p;
    while (quadRes(v = ((ll)w * w - x + p) % p, p));
    P2_Field res(1, 0), a(w, 1);
    for (; k; k >>= 1) {
      if (k & 1)
        res = P2_Field(((ll)res.first * a.first + (ll)res.second * a.second % p * v) % p, ((ll)res.first * a.second + (ll)res.second * a.first) % p);
      a = P2_Field(((ll)a.first * a.first + (ll)a.second * a.second % p * v) % p, 2LL * a.first * a.second % p);
    }
    return min(res.first, p - res.first);
  }
} nt;

namespace Simple {
  int n = 1;
  vector<int> fac({1, 1}), ifac({1, 1}), inv({0, 1});
  void build(int m) {
    n = m;
    fac.resize(n + 1), ifac.resize(n + 1), inv.resize(n + 1);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
      inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; ++i)
      fac[i] = (ll)fac[i - 1] * i % mod,
      ifac[i] = (ll)ifac[i - 1] * inv[i] % mod;
  }
  void check(int k) {
    int m = n;
    if (k > m) {
      while (k > m)
        m <<= 1;
      build(m);
    }
  }
  inline int gfac(int k) {
    check(k);
    return fac[k];
  }
  inline int gifac(int k) {
    check(k);
    return ifac[k];
  }
  inline int ginv(int k) {
    check(k);
    return inv[k];
  }
}

struct SimpleSequence {
  function<int(int)> func;
  inline SimpleSequence(const function<int(int)> &func): func(func) {}
  inline int operator[](int k) const {
    return func(k);
  }
} gfac(Simple::gfac), gifac(Simple::gifac), ginv(Simple::ginv);

inline int binom(int n, int m) {
  if (m > n || m < 0)
    return 0;
  return (ll)gfac[n] * gifac[m] % mod * gifac[n - m] % mod;
}

namespace NTT {
  int L = -1;
  vector<int> root;
  void init(int l) {
    L = l;
    root.resize((1 << L) + 1);
    int n = 1 << L, *w = root.data();
    w[0] = 1, w[1 << L] = mpow(31, 1 << (21 - L));
    for (int i = L; i; --i)
      w[1 << (i - 1)] = (ll)w[1 << i] * w[1 << i] % mod;
    for (int i = 1; i < n; ++i)
      w[i] = (ll)w[i & (i - 1)] * w[i & -i] % mod;
  }
  void DIF(int *a, int l) {
    int n = 1 << l;
    for (int len = n >> 1; len; len >>= 1)
      for (int *j = a, *o = root.data(); j != a + n; j += len << 1, ++o)
        for (int *k = j; k != j + len; ++k) {
          int r = (ll)*o * k[len] % mod;
          k[len] = reduce(*k - r), add(*k, r);
        }
  }
  void DIT(int *a, int l) {
    int n = 1 << l;
    for (int len = 1; len < n; len <<= 1)
      for (int *j = a, *o = root.data(); j != a + n; j += len << 1, ++o)
        for (int *k = j; k != j + len; ++k) {
          int r = norm(*k + k[len]);
          k[len] = (ll)*o * (*k - k[len] + mod) % mod, *k = r;
        }
  }
  void fft(int *a, int lgn, int d = 1) {
    if (L < lgn)
      init(lgn);
    int n = 1 << lgn;
    if (d == 1)
      DIF(a, lgn);
    else {
      DIT(a, lgn), reverse(a + 1, a + n);
      int nInv = mod - (mod - 1) / n;
      for (int i = 0; i < n; ++i)
        a[i] = (ll)a[i] * nInv % mod;
    }
  }
}

struct poly {
  vector<int> a;
  poly(ll v = 0): a(1) {
    if ((v %= mod) < 0)
      v += mod;
    a[0] = v;
  }
  poly(const poly &o): a(o.a) {}
  poly(const vector<int> &o): a(o) {}
  poly(initializer_list<int> o): a(o) {}
  int operator[](int k) const { return k < a.size() ? a[k] : 0; }
  int &operator[](int k) {
    if (k >= a.size())
      a.resize(k + 1);
    return a[k];
  }
  int deg() const { return (int)a.size() - 1; }
  void redeg(int d) { a.resize(d + 1); }
  int size() const {return a.size(); }
  void resize(int s) { a.resize(s); }
  poly slice(int d) const {
    if (d < a.size())
      return vector<int>(a.begin(), a.begin() + d + 1);
    vector<int> ret = a;
    ret.resize(d + 1);
    return ret;
  }
  poly shift(int k) const {
    if (size() + k <= 0)
      return 0;
    vector<int> ret(size() + k);
    for (int i = max(0, k); i < ret.size(); ++i)
      ret[i] = a[i - k];
    return ret;
  }
  int *base() { return a.data(); }
  const int *base() const { return a.data(); }
  poly println(FILE *fp = stdout) const {
    for (int i = 0; i < a.size(); ++i)
      fprintf(fp, "%d%c", a[i], " \n"[i == a.size() - 1]);
    return *this;
  }

  poly &operator+=(const poly &o) {
    if (o.size() > a.size())
      a.resize(o.size());
    for (int i = 0; i < o.size(); ++i)
      add(a[i], o[i]);
    return *this;
  }
  poly operator+(const poly &o) const { poly ret(a); ret += o; return ret; }
  poly operator-() const {
    poly ret = a;
    for (int i = 0; i < a.size(); ++i)
      ret[i] = neg(ret[i]);
    return ret;
  }
  poly &operator-=(const poly &o) { return operator+=(-o); }
  poly operator-(const poly &o) { return operator+(-o); }
  poly operator*(const poly &) const;
  poly operator/(const poly &) const;
  poly operator%(const poly &) const;
  poly &operator*=(const poly &o) { *this = operator*(o); return *this; }
  poly &operator/=(const poly &o) { *this = operator/(o); return *this; }
  poly &operator%=(const poly &o) { *this = operator%(o); return *this; }
  poly deriv() const;
  poly integ() const;
  poly inv() const;
  poly sqrt() const;
  poly ln() const;
  poly exp() const;
  poly srcExp() const;
  pair<poly, poly> sqrti() const;
  pair<poly, poly> expi() const;
  poly quo(const poly &) const;
  pair<poly, poly> iquo(const poly &) const;
  pair<poly, poly> div(const poly &) const;
  poly taylor(int k) const;
  poly pow(int k) const;
  poly exp(int k) const;
};

poly zeroes(int d) { return vector<int>(d + 1); }

namespace NTT { void fft(poly &a, int lgn, int d = 1) { fft(a.base(), lgn, d); } }

using NTT::fft;

struct Newton {
  void inv(const poly &f, const poly &dftf, poly &g, const poly &dftg, int t) {
    int n = 1 << t;
    poly prod = dftf;
    for (int i = 0; i < (n << 1); ++i)
      prod[i] = (ll)prod[i] * dftg[i] % mod;
    fft(prod, t + 1, -1);
    memset(prod.base(), 0, sizeof(int) << t);
    fft(prod, t + 1);
    for (int i = 0; i < (n << 1); ++i)
      prod[i] = (ll)prod[i] * dftg[i] % mod;
    fft(prod, t + 1, -1);
    for (int i = 0; i < n; ++i)
      prod[i] = 0;
    g -= prod;
  }
  void inv(const poly &f, const poly &dftf, poly &g, int t) {
    poly dftg(g);
    dftg.resize(2 << t);
    fft(dftg, t + 1);
    inv(f, dftf, g, dftg, t);
  }
  void inv(const poly &f, poly &g, int t) {
    poly dftf(f), dftg(g);
    dftf.resize(2 << t), dftg.resize(2 << t);
    fft(dftf, t + 1), fft(dftg, t + 1);
    inv(f, dftf, g, dftg, t);
  }
} nit;

poly poly::operator*(const poly &o) const {
  int n = deg(), m = o.deg();
  if (n <= 10 || m <= 10 || n + m <= BRUTE_N2_LIMIT) {
    poly ret = zeroes(n + m);
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= m; ++j)
        fam(ret[i + j], a[i], o[j]);
    return ret;
  }
  n += m;
  int l = 0;
  while ((1 << l) <= n)
    ++l;
  poly ret = a, tmp = o;
  ret.resize(1 << l), tmp.resize(1 << l);
  fft(ret, l), fft(tmp, l);
  for (int i = 0; i < (1 << l); ++i)
    ret[i] = (ll)ret[i] * tmp[i] % mod;
  fft(ret, l, -1);
  return ret.slice(n);
}
poly poly::inv() const {
  poly g = nt.inv(a[0]);
  for (int t = 0; (1 << t) <= deg(); ++t)
    nit.inv(slice((2 << t) - 1), g, t);
  g.redeg(deg());
  return g;
}
poly poly::deriv() const {
  if (deg() == 0)
    return 0;
  vector<int> ret(deg());
  for (int i = 0; i < deg(); ++i)
    ret[i] = (ll)a[i + 1] * (i + 1) % mod;
  return ret;
}
poly poly::quo(const poly &o) const {
  if (o.deg() == 0)
    return (ll)a[0] * nt.inv(o[0]) % mod;
  poly g = nt.inv(o[0]);
  int t = 0, n;
  for (n = 1; (n << 1) <= o.deg(); ++t, n <<= 1)
    nit.inv(o.slice((n << 1) - 1), g, t);
  poly dftg = g;
  dftg.resize(n << 1), fft(dftg, t + 1);
  poly eps1 = o;
  eps1.resize(n << 1), fft(eps1, t + 1);
  for (int i = 0; i < (n << 1); ++i)
    eps1[i] = (ll)eps1[i] * dftg[i] % mod;;
  fft(eps1, t + 1, -1);
  for (int i = 0; i < n; ++i)
    eps1[i] = eps1[i + n],
    eps1[i + n] = 0;
  fft(eps1, t + 1);
  poly h0 = slice(n - 1);
  h0.resize(n << 1), fft(h0, t + 1);
  poly h0g0 = zeroes((n << 1) - 1);
  for (int i = 0; i < (n << 1); ++i)
    h0g0[i] = (ll)h0[i] * dftg[i] % mod;
  fft(h0g0, t + 1, -1);
  poly h0eps1 = zeroes((n << 1) - 1);
  for (int i = 0; i < (n << 1); ++i)
    h0eps1[i] = (ll)h0[i] * eps1[i] % mod;
  fft(h0eps1, t + 1, -1);
  for (int i = 0; i < n; ++i)
    h0eps1[i] = reduce(operator[](i + n) - h0eps1[i]);
  memset(h0eps1.base() + n, 0, sizeof(int) << t);
  fft(h0eps1, t + 1);
  for (int i = 0; i < (n << 1); ++i)
    h0eps1[i] = (ll)h0eps1[i] * dftg[i] % mod;
  fft(h0eps1, t + 1, -1);
  for (int i = 0; i < n; ++i)
    h0eps1[i + n] = h0eps1[i],
    h0eps1[i] = 0;
  return (h0g0 + h0eps1).slice(o.deg());
}

struct RelaxedConvolution {
  static const int LG = 19;
  static const int B = 16;
  void run(int *b, const int *c0, const int *c1, int *e, const int *db, int n, const function<void(int)> &relax) {
    vector<vector<int>> saveb(LG + 1), savec0(LG + 1), savec1(LG + 1), savee(LG + 1), savedb(LG + 1);
    function<void(int, int)> divideConquer = [&](int l, int r) {
      if (r - l <= BRUTE_N2_LIMIT) {
        for (int i = l + 1; i <= r; ++i) {
          for (int j = l; j < i; ++j)
            fam(e[i], b[j], c1[i - j]),
            fam(b[i], db[j], c0[i - j]),
            fam(b[i], b[j], b[i - j]);
          if (l > 0)
            for (int j = l; j < i; ++j)
              fam(e[i], c1[j], b[i - j]),
              fam(b[i], c0[j], db[i - j]),
              fam(b[i], b[j], b[i - j]);
          relax(i);
        }
        return ;
      }
      if (l == 0) {
        int mid = ((l + r) >> 1) + 5;
        divideConquer(l, mid);
        int lgd = 0;
        while ((1 << lgd) <= r)
          ++lgd;
        vector<int> tb(1 << lgd), tc0(1 << lgd), tc1(1 << lgd), te(1 << lgd), tdb(1 << lgd);
        for (int i = 0; i < mid; ++i)
          tb[i] = b[i], tc0[i] = c0[i], tc1[i] = c1[i],
          te[i] = e[i], tdb[i] = db[i];
        fft(tb.data(), lgd), fft(tc0.data(), lgd), fft(tc1.data(), lgd),
        fft(te.data(), lgd), fft(tdb.data(), lgd);
        for (int i = 0; i < (1 << lgd); ++i)
          tc1[i] = (ll)tc1[i] * tb[i] % mod,
          tc0[i] = (ll)tc0[i] * tdb[i] % mod,
          tb[i] = (ll)tb[i] * tb[i] % mod;
        fft(tc1.data(), lgd, -1), fft(tc0.data(), lgd, -1), fft(tb.data(), lgd, -1);
        for (int i = mid + 1; i <= r; ++i)
          add(e[i], tc1[i]), add(b[i], norm(tc0[i] + tb[i]));
        divideConquer(mid, r);
        return ;
      }
      int d = (r - l) / B + 1, lgd = 0, lg;
      while ((1 << lgd) <= d * 2)
        ++lgd;
      d = (1 << (lgd - 1)) - 1, lg = (r - l + d - 1) / d;

      vector<int> dftb = saveb[lgd], dftc0 = savec0[lgd], dftc1 = savec1[lgd],
                  dfte = savee[lgd], dftdb = savedb[lgd];
      dftb.resize(lg << (lgd + 1)), dftc0.resize(lg << (lgd + 1)), dftc1.resize(lg << (lgd + 1)),
      dfte.resize(lg << (lgd + 1)), dftdb.resize(lg << (lgd + 1));
      for (int i = lg << lgd; i < (lg << (lgd + 1)); ++i)
        dftb[i] = dftc0[i] = dftc1[i] = dfte[i] = dftdb[i] = 0;
      int ef = lg;
      for (int i = 0; i < lg; ++i) {
        if ((i << lgd) < saveb[lgd].size())
          continue;
        if ((i + 2) * d >= l)
          --ef;
        for (int j = 0; j <= d * 2; ++j)
          dftb[(i << lgd) + j] = b[i * d + j],
          dftc0[(i << lgd) + j] = c0[i * d + j], dftc1[(i << lgd) + j] = c1[i * d + j],
          dfte[(i << lgd) + j] = e[i * d + j], dftdb[(i << lgd) + j] = db[i * d + j];
        fft(dftb.data() + (i << lgd), lgd),
        fft(dftc0.data() + (i << lgd), lgd), fft(dftc1.data() + (i << lgd), lgd),
        fft(dfte.data() + (i << lgd), lgd), fft(dftdb.data() + (i << lgd), lgd);
      }
      if (saveb[lgd].size() < (ef << lgd))
        saveb[lgd] = vector<int>(dftb.begin(), dftb.begin() + (ef << lgd)),
        savec0[lgd] = vector<int>(dftc0.begin(), dftc0.begin() + (ef << lgd)),
        savec1[lgd] = vector<int>(dftc1.begin(), dftc1.begin() + (ef << lgd)),
        savee[lgd] = vector<int>(dfte.begin(), dfte.begin() + (ef << lgd)),
        savedb[lgd] = vector<int>(dftdb.begin(), dftdb.begin() + (ef << lgd));
      for (int i = 0; i < lg; ++i) {
        if (i)
          fft(dftb.data() + ((lg + i) << lgd), lgd, -1),
          fft(dfte.data() + ((lg + i) << lgd), lgd, -1);
        for (int j = 1; j <= min(d, r - l - i * d); ++j)
          add(b[l + i * d + j], dftb[((lg + i) << lgd) + d + j]),
          add(e[l + i * d + j], dfte[((lg + i) << lgd) + d + j]);
        divideConquer(l + i * d, min(l + (i + 1) * d, r));
        if (i + 1 < lg) {
          for (int j = 0; j < d; ++j)
            dftb[((lg + i) << lgd) + j] = b[l + i * d + j],
            dftc0[((lg + i) << lgd) + j] = c0[l + i * d + j],
            dftc1[((lg + i) << lgd) + j] = c1[l + i * d + j],
            dfte[((lg + i) << lgd) + j] = e[l + i * d + j],
            dftdb[((lg + i) << lgd) + j] = db[l + i * d + j];
          for (int j = d; j < (1 << lgd); ++j)
            dftb[((lg + i) << lgd) + j] = dfte[((lg + i) << lgd) + j] = 0;
          fft(dftb.data() + ((lg + i) << lgd), lgd),
          fft(dftc0.data() + ((lg + i) << lgd), lgd), fft(dftc1.data() + ((lg + i) << lgd), lgd),
          fft(dfte.data() + ((lg + i) << lgd), lgd), fft(dftdb.data() + ((lg + i) << lgd), lgd);
        }
        for (int j = i + 1; j < lg; ++j)
          for (int k = 0; k < (1 << lgd); ++k)
            dfte[((lg + j) << lgd) + k] = (dfte[((lg + j) << lgd) + k] + (ll)dftb[((j - i - 1) << lgd) + k] * dftc1[((lg + i) << lgd) + k] + (ll)dftb[((lg + i) << lgd) + k] * dftc1[((j - i - 1) << lgd) + k]) % mod,
            dftb[((lg + j) << lgd) + k] = (dftb[((lg + j) << lgd) + k] + (ll)dftdb[((j - i - 1) << lgd) + k] * dftc0[((lg + i) << lgd) + k] + (ll)dftdb[((lg + i) << lgd) + k] * dftc0[((j - i - 1) << lgd) + k]) % mod,
            dftb[((lg + j) << lgd) + k] = (dftb[((lg + j) << lgd) + k] + (ll)dftb[((j - i - 1) << lgd) + k] * dftb[((lg + i) << lgd) + k] + (ll)dftb[((lg + i) << lgd) + k] * dftb[((j - i - 1) << lgd) + k]) % mod;
      }
    };
    relax(0), divideConquer(0, n);
  }
} rc;

const int N = 3e5;

int n, k, t;
poly p, h, g;
poly b, c, d;

int c0[N + 5], e[N + 5], db[N + 5];

int ans;

int main() {
  scanf("%d%d", &n, &k);
  assert(k >= 1 && k < n);
  p.redeg(n), h.redeg(n);
  for (int i = 1; i <= n; ++i)
    p[i] = gfac[i], h[i] = (i <= k) * gfac[i];
  g = p.quo(p + 1);
  for (int i = 0; i < n - k; ++i)
    g[i] = 0;
  g *= g;
  for (int i = 0; i <= n; ++i)
    fam(ans, g[i], gfac[n - i]);
  sub(ans, ((h * h).slice(n).quo(h + 1))[n]);
  ans = norm(2 * ans);
  c = h.quo(h.deriv().slice(n)), d = c + h.deriv().slice(n).inv();
  b.redeg(n), rc.run(b.base(), c0, d.base(), e, db, n, [&](int k) {
    if (k == 0) return ;
    if (k == 1) b[k] = e[k] = 1;
    else b[k] = reduce(c[k] - norm(b[k] + e[k]));
    db[k - 1] = (ll)k * b[k] % mod;
    c0[k] = reduce(norm(b[k] + e[k]) - c[k]);
  });
  sub(ans, b[n]);
  printf("%d\n", ans);
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 3772kb

input:

3 2

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

input:

4 2

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

300 20

output:

368258992

result:

ok 1 number(s): "368258992"

Test #4:

score: 0
Accepted
time: 309ms
memory: 20968kb

input:

100000 1

output:

91844344

result:

ok 1 number(s): "91844344"

Test #5:

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

input:

2 1

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

282 4

output:

563176581

result:

ok 1 number(s): "563176581"

Test #7:

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

input:

359 159

output:

903685663

result:

ok 1 number(s): "903685663"

Test #8:

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

input:

359 254

output:

470520868

result:

ok 1 number(s): "470520868"

Test #9:

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

input:

58 27

output:

436559968

result:

ok 1 number(s): "436559968"

Test #10:

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

input:

202 194

output:

16749760

result:

ok 1 number(s): "16749760"

Test #11:

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

input:

45 12

output:

296797655

result:

ok 1 number(s): "296797655"

Test #12:

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

input:

363 242

output:

13005572

result:

ok 1 number(s): "13005572"

Test #13:

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

input:

342 65

output:

923824682

result:

ok 1 number(s): "923824682"

Test #14:

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

input:

207 190

output:

369707039

result:

ok 1 number(s): "369707039"

Test #15:

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

input:

367 37

output:

467362142

result:

ok 1 number(s): "467362142"

Test #16:

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

input:

130 18

output:

188514783

result:

ok 1 number(s): "188514783"

Test #17:

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

input:

362 6

output:

563842262

result:

ok 1 number(s): "563842262"

Test #18:

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

input:

296 93

output:

826385279

result:

ok 1 number(s): "826385279"

Test #19:

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

input:

66 56

output:

510485158

result:

ok 1 number(s): "510485158"

Test #20:

score: 0
Accepted
time: 128ms
memory: 10272kb

input:

35567 25153

output:

370961506

result:

ok 1 number(s): "370961506"

Test #21:

score: 0
Accepted
time: 283ms
memory: 19096kb

input:

87796 51661

output:

486383441

result:

ok 1 number(s): "486383441"

Test #22:

score: 0
Accepted
time: 140ms
memory: 11732kb

input:

46775 17243

output:

84820979

result:

ok 1 number(s): "84820979"

Test #23:

score: 0
Accepted
time: 69ms
memory: 7452kb

input:

23118 14043

output:

768845693

result:

ok 1 number(s): "768845693"

Test #24:

score: 0
Accepted
time: 129ms
memory: 10244kb

input:

34630 30168

output:

163030696

result:

ok 1 number(s): "163030696"

Test #25:

score: 0
Accepted
time: 14ms
memory: 4600kb

input:

7355 6036

output:

721628072

result:

ok 1 number(s): "721628072"

Test #26:

score: 0
Accepted
time: 280ms
memory: 17940kb

input:

76991 35145

output:

741290476

result:

ok 1 number(s): "741290476"

Test #27:

score: 0
Accepted
time: 264ms
memory: 16900kb

input:

65607 31472

output:

120005728

result:

ok 1 number(s): "120005728"

Test #28:

score: 0
Accepted
time: 162ms
memory: 13612kb

input:

63045 5458

output:

568942298

result:

ok 1 number(s): "568942298"

Test #29:

score: 0
Accepted
time: 273ms
memory: 16968kb

input:

70632 20910

output:

870416132

result:

ok 1 number(s): "870416132"

Test #30:

score: 0
Accepted
time: 23ms
memory: 5452kb

input:

12184 4852

output:

887796493

result:

ok 1 number(s): "887796493"

Test #31:

score: 0
Accepted
time: 284ms
memory: 20100kb

input:

90205 3600

output:

431001694

result:

ok 1 number(s): "431001694"

Test #32:

score: 0
Accepted
time: 287ms
memory: 19732kb

input:

90932 33329

output:

600549935

result:

ok 1 number(s): "600549935"

Test #33:

score: 0
Accepted
time: 146ms
memory: 12880kb

input:

53902 13766

output:

415161256

result:

ok 1 number(s): "415161256"

Test #34:

score: 0
Accepted
time: 35ms
memory: 5660kb

input:

14161 7105

output:

134694410

result:

ok 1 number(s): "134694410"

Test #35:

score: 0
Accepted
time: 135ms
memory: 11972kb

input:

46381 37047

output:

187944778

result:

ok 1 number(s): "187944778"

Test #36:

score: 0
Accepted
time: 130ms
memory: 12072kb

input:

33614 4898

output:

747492373

result:

ok 1 number(s): "747492373"

Test #37:

score: 0
Accepted
time: 293ms
memory: 19792kb

input:

91722 35254

output:

694638772

result:

ok 1 number(s): "694638772"

Test #38:

score: 0
Accepted
time: 129ms
memory: 11152kb

input:

43121 16137

output:

287812406

result:

ok 1 number(s): "287812406"

Test #39:

score: 0
Accepted
time: 142ms
memory: 11164kb

input:

43266 29411

output:

573388406

result:

ok 1 number(s): "573388406"

Test #40:

score: 0
Accepted
time: 10ms
memory: 4352kb

input:

4919 1469

output:

683001842

result:

ok 1 number(s): "683001842"

Test #41:

score: 0
Accepted
time: 32ms
memory: 5356kb

input:

10213 4043

output:

828882070

result:

ok 1 number(s): "828882070"

Test #42:

score: 0
Accepted
time: 139ms
memory: 13360kb

input:

57705 29766

output:

908462562

result:

ok 1 number(s): "908462562"

Test #43:

score: 0
Accepted
time: 132ms
memory: 12168kb

input:

50628 43693

output:

874935502

result:

ok 1 number(s): "874935502"

Test #44:

score: 0
Accepted
time: 275ms
memory: 17012kb

input:

71491 8618

output:

720976298

result:

ok 1 number(s): "720976298"

Test #45:

score: 0
Accepted
time: 156ms
memory: 13244kb

input:

61231 37699

output:

905540582

result:

ok 1 number(s): "905540582"

Test #46:

score: 0
Accepted
time: 150ms
memory: 13104kb

input:

60626 48375

output:

847650011

result:

ok 1 number(s): "847650011"

Test #47:

score: 0
Accepted
time: 65ms
memory: 8264kb

input:

29493 22917

output:

808093687

result:

ok 1 number(s): "808093687"

Test #48:

score: 0
Accepted
time: 144ms
memory: 11184kb

input:

42960 4829

output:

582999364

result:

ok 1 number(s): "582999364"

Test #49:

score: 0
Accepted
time: 295ms
memory: 19864kb

input:

92916 35720

output:

871538508

result:

ok 1 number(s): "871538508"

Test #50:

score: 0
Accepted
time: 301ms
memory: 20088kb

input:

95751 52590

output:

676583073

result:

ok 1 number(s): "676583073"

Test #51:

score: 0
Accepted
time: 122ms
memory: 10444kb

input:

38771 20287

output:

598673771

result:

ok 1 number(s): "598673771"

Test #52:

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

input:

711 592

output:

22681776

result:

ok 1 number(s): "22681776"

Test #53:

score: 0
Accepted
time: 262ms
memory: 17008kb

input:

68245 11512

output:

182749044

result:

ok 1 number(s): "182749044"

Test #54:

score: 0
Accepted
time: 260ms
memory: 16964kb

input:

68203 966

output:

488928778

result:

ok 1 number(s): "488928778"

Test #55:

score: 0
Accepted
time: 297ms
memory: 21084kb

input:

100000 111

output:

373450248

result:

ok 1 number(s): "373450248"

Test #56:

score: 0
Accepted
time: 306ms
memory: 20932kb

input:

100000 1231

output:

105765703

result:

ok 1 number(s): "105765703"

Test #57:

score: 0
Accepted
time: 292ms
memory: 21176kb

input:

100000 12333

output:

860654995

result:

ok 1 number(s): "860654995"

Test #58:

score: 0
Accepted
time: 286ms
memory: 20924kb

input:

100000 39198

output:

846441800

result:

ok 1 number(s): "846441800"

Test #59:

score: 0
Accepted
time: 295ms
memory: 20772kb

input:

100000 56721

output:

618984747

result:

ok 1 number(s): "618984747"

Test #60:

score: 0
Accepted
time: 310ms
memory: 21112kb

input:

100000 99823

output:

811855278

result:

ok 1 number(s): "811855278"

Test #61:

score: 0
Accepted
time: 288ms
memory: 20936kb

input:

100000 99998

output:

385349822

result:

ok 1 number(s): "385349822"