QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#61990 | #4822. Matrix Counting | alpha1022 | AC ✓ | 310ms | 21176kb | C++17 | 16.4kb | 2022-11-16 15:57:09 | 2022-11-16 15:57:12 |
Judging History
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"