#include <bits/stdc++.h>
namespace IO {
std::ostream& fmtbase(std::ostream& out, const char* format) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
throw std::invalid_argument("Error Number of Parameters!");
}
out << *format;
}
return out;
}
template <class Fst, class... Nxt>
std::ostream& fmtbase(std::ostream& out, const char* format, const Fst& value, const Nxt&... nxt) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
out << value;
return fmtbase(out, format + 2, nxt...);
}
out << *format;
}
throw std::invalid_argument("Error Number of Parameters!");
}
template <class... Ps>
std::ostream& fmtout(const char* format, const Ps&... ps) {
return fmtbase(std::cout, format, ps...);
}
template <class... Ps>
std::ostream& fmterr(const char* format, const Ps&... ps) {
return fmtbase(std::cerr, format, ps...);
}
std::istream& allin() {
return std::cin;
}
template <class Fst, class ... Nxt>
std::istream& allin(Fst& fst, Nxt&... nxt) {
std::cin >> fst;
return allin(nxt...);
}
template <class Iter>
std::istream& rangin(Iter begin, Iter end) {
while (begin != end) {
std::cin >> *begin;
begin++;
}
return std::cin;
}
namespace Fast {
bool sync = false;
char buf[1 << 23];
char *p1 = buf, *p2 = buf;
void sync_with_ios(bool s) {
sync = s;
}
char getchar() {
if (sync) {
return std::cin.get();
}
else {
if (p1 == p2) {
p1 = buf;
p2 = p1 + fread(buf, 1, 1 << 22, stdin);
}
if (p1 == p2) {
return EOF;
}
else {
char res = *p1;
p1++;
return res;
}
}
}
void read() { }
template <class T, class... U>
void read(T& x, U&... us) {
x = 0;
T pos = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') {
pos = -1;
}
c = getchar();
}
while (isdigit(c)) {
x = 10 * x + c - '0';
c = getchar();
}
x *= pos;
read(us...);
}
}
}
namespace Solve {
using namespace IO;
using Long = long long;
using Double = long double;
int const Shabby = 0;
int const INF = std::numeric_limits<int>::max();
int const NINF = std::numeric_limits<int>::min();
Long const LINF = std::numeric_limits<Long>::max();
Long const LNINF = std::numeric_limits<Long>::min();
Double const EPS = 1e-9;
namespace Polynomial {
template <int M>
struct ModInt {
// Promise: MOD is a prime; 2 * MOD < INT_MAX
static int const MOD = M;
int val;
ModInt() : val(0) { }
ModInt(long long v) {
if (-MOD <= v && v < 2 * MOD) {
if (v > MOD) {
v -= MOD;
}
else if (v < 0) {
v += MOD;
}
}
else {
v %= MOD;
if (v < 0) {
v += MOD;
}
}
val = v;
}
ModInt operator++(signed) {
auto t = *this;
operator+=(1);
return t;
}
ModInt& operator++() {
operator+=(1);
return *this;
}
ModInt operator--(signed) {
auto t = *this;
operator-=(1);
return t;
}
ModInt& operator--() {
operator-=(1);
return *this;
}
ModInt& operator+=(const ModInt& rhs) {
val = val + rhs.val >= MOD ? val + rhs.val - MOD : val + rhs.val;
return *this;
}
friend ModInt operator+(const ModInt& lhs, const ModInt& rhs) {
ModInt res = lhs;
res += rhs;
return res;
}
ModInt& operator-=(const ModInt& rhs) {
val = val - rhs.val < 0 ? val - rhs.val + MOD : val - rhs.val;
return *this;
}
friend ModInt operator-(const ModInt& lhs, const ModInt& rhs) {
ModInt res = lhs;
res -= rhs;
return res;
}
ModInt& operator*=(const ModInt& rhs) {
val = 1ll * val * rhs.val % MOD;
return *this;
}
friend ModInt operator*(const ModInt& lhs, const ModInt& rhs) {
ModInt res = lhs;
res *= rhs;
return res;
}
ModInt fpow(long long p) const {
if (p < 0) {
return fpow(-p).inv();
}
else if (!p) {
return 1;
}
else if (p == 1) {
return *this;
}
else if (p == 2) {
return *this * *this;
}
else {
return fpow(p / 2).fpow(2) * fpow(p % 2);
}
}
friend bool operator==(const ModInt& a, const ModInt& b) {
return a.val == b.val;
}
friend bool operator!=(const ModInt& a, const ModInt& b) {
return a.val != b.val;
}
friend ModInt operator-(const ModInt& a) {
ModInt res;
res.val = MOD - a.val;
return res;
}
ModInt inv() const {
return fpow(MOD - 2);
}
ModInt operator/=(const ModInt& rhs) {
// O(log MOD)
return operator*=(rhs.inv());
}
friend ModInt operator/(const ModInt& lhs, const ModInt& rhs) {
ModInt res = lhs;
res /= rhs;
return res;
}
bool is_square() const {
return val == 0 || fpow((MOD - 1) / 2).val == 1;
}
ModInt sqrt() const {
static std::mt19937 mt(42334435);
static ModInt isq;
assert(is_square());
struct Complex {
ModInt a, b;
Complex operator*(const Complex& rhs) const {
return { a * rhs.a + isq * b * rhs.b, a * rhs.b + b * rhs.a };
}
Complex fpow(int n) {
if (!n) {
return { 1, 0 };
}
else if (n == 1) {
return *this;
}
else if (n == 2) {
return operator*(*this);
}
else {
return fpow(n / 2).fpow(2) * fpow(n % 2);
}
}
};
if (val == 0) {
return 0;
}
ModInt b;
while (true) {
b = mt() % MOD;
if (!(b * b - *this).is_square()) {
break;
}
}
isq = b * b - *this;
Complex c = { b, 1 };
auto res = c.fpow((MOD + 1) / 2).a;
return std::min(res.val, MOD - res.val);
}
};
template <int MOD>
std::istream& operator>>(std::istream& in, ModInt<MOD>& mint) {
long long v;
in >> v;
mint.val = v % MOD;
return in;
}
template <int MOD>
std::ostream& operator<<(std::ostream& out, const ModInt<MOD>& mint) {
return out << mint.val;
}
template <class T, int B>
struct FastPow {
T baby[B + 1];
T gaint[B + 1];
FastPow(T b) {
baby[0] = 1;
for (int i = 1; i <= B; i++) {
baby[i] = baby[i - 1] * b;
}
gaint[0] = 1;
for (int i = 1; i <= B; i++) {
gaint[i] = gaint[i - 1] * baby[B];
}
}
T get(int n) {
return gaint[n / B] * baby[n % B];
}
};
int const MOD = 998244353;
template <int M>
const int ModInt<M>::MOD;
using Mint = ModInt<MOD>;
using Poly = std::vector<Mint>;
Mint const G = 3;
Mint const GI = (MOD + 1) / G;
Poly wbs;
Poly iwbs;
Mint get_wbs(int lg, int op) {
while (lg >= (int) wbs.size()) {
int cur = wbs.size();
wbs.push_back(G.fpow((MOD - 1) / (1 << cur)));
iwbs.push_back(GI.fpow((MOD - 1) / (1 << cur)));
}
return op == 1 ? wbs[lg] : iwbs[lg];
}
void FFT(Poly& f, int op) {
int len = f.size();
std::vector<int> rev(len);
for (int i = 1; i < len; i++) {
rev[i] = rev[i >> 1] >> 1;
if (i & 1) {
rev[i] |= len >> 1;
}
}
for (int i = 0; i < len; i++) {
if (rev[i] < i) {
std::swap(f[rev[i]], f[i]);
}
}
for (int i = 0; (1 << i) < len; i++) {
int cur = 1 << i;
auto wb = get_wbs(i + 1, op);
for (int j = 0; j < len; j += cur * 2) {
Mint w = 1;
if (i == 0) {
auto t = w * f[j + cur];
f[j + cur] = f[j] - t;
f[j] += t;
continue;
}
for (int k = 0; k < cur; k += 2) {
auto t = w * f[j + k + cur];
f[j + k + cur] = f[j + k] - t;
f[j + k] += t;
w *= wb;
t = w * f[j + k + 1 + cur];
f[j + k + 1 + cur] = f[j + k + 1] - t;
f[j + k + 1] += t;
w *= wb;
}
}
}
}
void DFT(Poly& f) {
FFT(f, 1);
}
void IDFT(Poly& f) {
FFT(f, -1);
int len = f.size();
Mint inv = Mint(len).inv();
for (auto& v : f) {
v *= inv;
}
}
int extend(int n) {
int len = 1;
for (; len < n; len *= 2);
return len;
}
Poly mul(Poly f, Poly g, int r = -1, int len = -1) { // 3 times
int n = f.size();
int m = g.size();
if (n <= 100 || m <= 100) {
Poly res(n + m - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res[i + j] += f[i] * g[j];
}
}
if (r != -1) {
res.resize(r);
}
return res;
}
if (len == -1) {
len = extend(n + m - 1);
}
f.resize(len);
g.resize(len);
DFT(f);
DFT(g);
for (int i = 0; i < len; i++) {
f[i] *= g[i];
}
IDFT(f);
f.resize(n + m - 1);
if (r != -1) {
f.resize(r);
}
return f;
}
Poly square(Poly f, int r = -1) {
int n = f.size();
int m = f.size();
if (n <= 100 || m <= 100) {
Poly res(n + m - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res[i + j] += f[i] * f[j];
}
}
if (r != -1) {
res.resize(r);
}
return res;
}
int len = extend(n + m - 1);
f.resize(len);
DFT(f);
for (int i = 0; i < len; i++) {
f[i] *= f[i];
}
IDFT(f);
f.resize(n + m - 1);
if (r != -1) {
f.resize(r);
}
return f;
}
Poly divx(const Poly& f, int x) {
if (x >= (int) f.size()) {
return { 0 };
}
else {
return Poly(f.begin() + x, f.end());
}
}
Poly resize(Poly f, int len) {
f.resize(len);
return f;
}
Poly reverse(Poly f) {
std::reverse(f.begin(), f.end());
return f;
}
Poly add(Poly f, const Poly& g, int r = -1) {
int n = f.size();
int m = g.size();
int len = std::max(n, m);
f.resize(len);
for (int i = 0; i < m; i++) {
f[i] += g[i];
}
if (r != -1) {
f.resize(r);
}
return f;
}
Poly sub(Poly f, const Poly& g, int r = -1) {
int n = f.size();
int m = g.size();
int len = std::max(n, m);
f.resize(len);
for (int i = 0; i < m; i++) {
f[i] -= g[i];
}
if (r != -1) {
f.resize(r);
}
return f;
}
template <class Fst, class Iter>
Poly newtown(const Poly& f, int n, Fst fst, Iter iter) {
Poly res(1);
res[0] = fst(f[0]);
int len = 1;
while (len < n) {
iter(f, res, len);
}
res.resize(n);
return res;
}
Poly inv(const Poly& f, int n) { // 10
return newtown(f, n,
[&](const Mint& v) {
assert(v.val != 0);
return v.inv();
},
[&](const Poly& f, Poly& res, int& len) {
int to = 2 * len;
res = sub(mul(res, { 2 }), mul(square(res, to), resize(f, to), to), to);
len = to;
}
);
}
Poly sqrt(const Poly& f, int n) { // 10
return newtown(f, n,
[&](const Mint& v) {
assert(v.is_square());
return v.sqrt();
},
[&](const Poly& f, Poly& res, int& len) {
int to = 2 * len;
res = mul(add(square(res, to), resize(f, to)), mul(inv(res, to), { Mint(2).inv() }), to);
len = to;
}
);
}
Poly integral(Poly f, Mint c = 0) {
int n = f.size();
f.resize(n + 1);
std::vector<Mint> inv(n + 1);
inv[0] = 1;
for (int i = 1; i <= n; i++) {
inv[i] = inv[i - 1] * i;
}
inv[n] = inv[n].inv();
for (int i = n - 1; i >= 1; i--) {
auto t = inv[i];
inv[i] = inv[i + 1] * (i + 1);
inv[i + 1] *= t;
}
for (int i = n - 1; i >= 0; i--) {
f[i + 1] = f[i] * inv[i + 1];
}
f[0] = c;
return f;
}
Poly differential(Poly f) {
int n = f.size();
for (int i = 1; i < n; i++) {
f[i - 1] = f[i] * i;
}
f.resize(n - 1);
return f;
}
Poly log(const Poly& f, int n) { // 13
assert(f[0].val == 1);
return resize(integral(mul(differential(f), inv(f, n - 1), n - 1)), n);
}
Poly exp(const Poly& f, int n) { // 32
return newtown(f, n,
[&](const Mint& v) {
assert(v.val == 0);
return 1;
},
[&](const Poly& f, Poly& res, int& len) {
int to = 2 * len;
res = mul(res, add(sub({ 1 }, log(res, to)), resize(f, to), to), to);
len = to;
}
);
}
Poly sin(const Poly& f, int n) { // 64
static Mint const I = Mint(Mint::MOD - 1).sqrt();
return resize(mul(sub(exp(mul(f, { I }), n), exp(mul(f, { -I }), n)), { Mint(2 * I).inv() }, n), n);
}
Poly cos(Poly f, int n) { // 64
static Mint const I = Mint(Mint::MOD - 1).sqrt();
return resize(mul(add(exp(mul(f, { I }), n), exp(mul(f, { -I }), n)), { Mint(2).inv() }, n), n);
}
Poly arcsin(Poly f, int n) { // 25
return resize(integral(mul(inv(sqrt(sub({ 1 }, square(f, n - 1)), n - 1), n - 1), differential(f), n - 1)), n);
}
Poly arctan(Poly f, int n) { // 15
return resize(integral(mul(inv(add({ 1 }, square(f, n - 1)), n - 1), differential(f), n - 1)), n);
}
Poly div(Poly f, Poly g) { // 13
int n = f.size();
int m = g.size();
if (m > n) {
return { 0 };
}
int len = n - m + 1;
return reverse(mul(resize(reverse(f), len), inv(resize(reverse(g), len), len)));
}
Poly div(const Poly& f, const Poly& g, int n) {
return mul(f, inv(g, n), n);
}
Poly mod(Poly f, Poly g) { // 16
return sub(f, mul(g, div(f, g)), (int) g.size() - 1);
}
Poly multipoint(const Poly& f, const Poly& p) {
int m = p.size();
int n = f.size();
std::vector<Poly> ps(m);
for (int i = 0; i < m; i++) {
ps[i].resize(2);
ps[i][0] = 1;
ps[i][1] = -p[i];
}
auto revmul = [&](Poly f, Poly g, int len) {
int m = g.size();
g = mul(reverse(g), f);
f.resize(len);
for (int i = 0; i < len && m + i - 1 < (int) g.size(); i++) {
f[i] = g[m + i - 1];
}
return f;
};
std::vector<Poly> prod(4 * m);
std::function<void(int, int, int)> solve1 = [&](int x, int l, int r) {
if (l == r) {
prod[x] = ps[l];
}
else {
int mid = (l + r) >> 1;
solve1(2 * x, l, mid);
solve1(2 * x + 1, mid + 1, r);
prod[x] = mul(prod[2 * x], prod[2 * x + 1]);
}
};
solve1(1, 0, m - 1);
Poly res(m);
std::function<void(int, Poly, int, int)> solve2 = [&](int x, Poly g, int l, int r) {
if (l == r) {
res[l] = g[0];
return;
}
int mid = (l + r) >> 1;
solve2(2 * x, revmul(g, prod[2 * x + 1], mid - l + 1), l, mid);
solve2(2 * x + 1, revmul(g, prod[2 * x], r - mid), mid + 1, r);
};
solve2(1, revmul(f, inv(prod[1], n), n), 0, m - 1);
return res;
}
Poly insert(const Poly& x, const Poly& y) {
int n = x.size();
std::vector<Poly> ps(n);
for (int i = 0; i < n; i++) {
ps[i].resize(2);
ps[i][0] = x[i];
ps[i][1] = -1;
}
std::vector<Poly> prod(4 * n);
std::function<void(int, int, int)> solve1 = [&](int x, int l, int r) {
if (l == r) {
prod[x] = ps[l];
}
else {
int mid = (l + r) >> 1;
solve1(2 * x, l, mid);
solve1(2 * x + 1, mid + 1, r);
prod[x] = mul(prod[2 * x], prod[2 * x + 1]);
}
};
solve1(1, 0, n - 1);
prod[1] = differential(prod[1]);
auto vs = multipoint(prod[1], x);
for (auto& v : vs) {
v *= -1;
}
std::vector<Poly> ans(n);
std::function<void(int, int, int)> solve2 = [&](int x, int l, int r) {
if (l == r) {
ans[l].resize(1);
ans[l][0] = y[l] / vs[l];
}
else {
int mid = (l + r) >> 1;
solve2(2 * x, l, mid);
solve2(2 * x + 1, mid + 1, r);
ans[l] = add(mul(ans[l], prod[2 * x + 1]), mul(ans[mid + 1], prod[2 * x]));
}
};
solve2(1, 0, n - 1);
return ans[0];
}
Mint eval(const Poly& f, Mint k) {
Mint pow = 1;
Mint ans = 0;
for (const auto& v : f) {
ans += pow * v;
pow *= k;
}
return ans;
}
Poly multipow(Poly f, Mint c, int m) {
// f(c^0), ..., f(c^{m-1})
int n = f.size();
std::vector<int> c2(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
c2[i] = 1ll * i * (i - 1) / 2 % (Mint::MOD - 1);
}
auto ci = c.inv();
FastPow<Mint, 35000> cp(c);
FastPow<Mint, 35000> cip(ci);
Poly c2p(n + m - 1);
Poly c2pi(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
c2p[i] = cp.get(c2[i]);
if (i < n || i < m) {
c2pi[i] = cip.get(c2[i]);
}
}
for (int i = 0; i < n; i++) {
f[i] *= c2pi[i];
}
c2p = reverse(c2p);
f = mul(f, c2p, n + m - 1, extend(n + m - 1));
Poly res(m);
for (int i = 0; i < m; i++) {
res[i] = f[n + m - 2 - i];
}
for (int i = 0; i < m; i++) {
res[i] *= c2pi[i];
}
return res;
}
Poly ogf_multiset(const Poly& f, int n) {
Poly r(n);
for (int i = 1; i < n; i++) {
Mint inv = Mint(i).inv();
for (int j = 0; i * j < n; j++) {
r[i * j] += f[j] * inv;
}
}
return exp(r, n);
}
}
using namespace Polynomial;
void main() {
int n;
allin(n);
Poly f(n);
Poly g(n);
for (int i = 0; i < n; i++) {
allin(f[i], g[i]);
}
for (auto& v : insert(f, g)) {
fmtout("{} ", v);
}
fmtout("\n");
}
void init() {
}
void clear() {
}
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
using namespace Solve;
n++;
m++;
Poly f(a, a + n);
Poly g(b, b + m);
f = mul(f, g);
for (int i = 0; i < (int) f.size(); i++) {
c[i] = f[i].val;
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 386.54 ms | 46 MB + 956 KB | Accepted | Score: 100 | 显示更多 |