// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define il inline
#define mkp make_pair
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define lll __int128
#define ll long long
#define uint unsigned int
#define ull unsigned ll
#define db double
#define ldb long double
#define sq(x) ((x)*(x))
#define For(i,j,k) for(register i=(j); i<=(k); ++i) // NOLINT
#define ForDown(i,j,k) for(register i=(j); i>=(k); --i) // NOLINT
#define pb push_back
#define eb emplace_back
#define FileIO(filename) freopen(filename ".in" ,"r",stdin);freopen(filename ".out" ,"w",stdout)
template<typename T> il void read(T &x){ x=0;int f=1;int c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x);read(y...); }
#if __cplusplus < 201400
#warning "Please use c++14 or higher."
template<typename T> il T qpow(T x, ull y, T mod){T ans=1;x%=mod;while(y){if(y&1)(ans*=x)%=mod;(x*=x)%=mod;y>>=1;}return ans;}
template<typename T> il T qpow(T x, ull y){T ans=1;while(y){if(y&1)ans*=x;x*=x;y>>=1;}return ans;}
#else
template<typename T> il constexpr T qpow(T x, ull y, T mod){T ans=1;x%=mod;while(y){if(y&1)(ans*=x)%=mod;(x*=x)%=mod;y>>=1;}return ans;}
template<typename T> il constexpr T qpow(T x, ull y){T ans=1;while(y){if(y&1)ans*=x;x*=x;y>>=1;}return ans;}
#endif
#ifndef ONLINE_JUDGE
#define __lg log2
namespace _Debug {
template <typename T> inline void _debug(const char* format, T t) { cerr<<format<<'='<<t<<endl; }
template <class First, class... Rest> inline void _debug(const char* format, First first, Rest... rest) { while (*format != ',') cerr << *format++; cerr << '=' << first << ","; _debug(format + 1, rest...);}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& V) { os << "[ "; for (const auto& vv : V) os << vv << ", "; os << "]"; return os; }
#define debug(...) cerr<<"Line "<<__LINE__<<": ",_debug(#__VA_ARGS__, __VA_ARGS__);
};
using namespace _Debug;
#endif
// File head end
// clang-format on
namespace Modint {
template <const uint Mod> class Modint {
uint _val;
il static unordered_map<uint, uint> _inv;
public:
Modint() : _val(0) {}
constexpr Modint(ll val) : _val((val % Mod + Mod) % Mod) {}
[[nodiscard]] il uint value() const { return _val; }
[[nodiscard]] il uint inv() const {
return _inv.count(_val) ? _inv[_val]
: _inv[_val] = qpow(*this, Mod - 2)._val;
}
void operator*=(const Modint &rhs) { _val = ((ull)_val * rhs._val) % Mod; }
void operator/=(const Modint &rhs) { _val = ((ull)_val * rhs.inv()) % Mod; }
void operator+=(const Modint &rhs) {
int(_val += rhs._val - (Mod << 1)) < 0 ? _val += (Mod << 1) : (ull){};
}
void operator-=(const Modint &rhs) {
int(_val -= rhs._val) < 0 ? _val += (Mod << 1) : (ull){};
}
#define setOper(x) \
[[nodiscard]] Modint operator x(const Modint &rhs) const { \
auto lhs = *this; \
lhs x## = rhs; \
return lhs; \
}
setOper(+) setOper(-) setOper(*) setOper(/)
#undef setOper
};
template <const ll Mod> istream &operator>>(istream &istr, Modint<Mod> &x) {
ll _temp;
istr >> _temp, x = _temp;
return istr;
}
template <const ll Mod> ostream &operator<<(ostream &ostr, Modint<Mod> x) {
ostr << x.value();
return ostr;
}
} // namespace Modint
using Z = Modint::Modint<998244353>;
constexpr Z operator""_Z(ull x) { return {(ll)x}; }
class Poly : public vector<Z> {
il static constexpr Z G = 3;
il static constexpr uint MAXN = 1u << 21;
il static vector<uint> _Rev;
il static uint cur_len = 0;
il static bool gn_table_ok = 0;
il static Z GN[MAXN];
il static void init_rev(uint len) {
cur_len = len;
_Rev.resize(len);
For(i, 0, len - 1) {
_Rev[i] = _Rev[i >> 1] >> 1;
if (i & 1)
_Rev[i] |= len >> 1;
}
}
il static void init_gn_table() {
GN[21] = qpow(G, 998244352 / (1 << 21));
for (uint l = MAXN >> 1, i = 20; l >= 2; l >>= 1, i--) {
GN[i] = sq(GN[i + 1]);
}
gn_table_ok = 1;
}
il void NTT(uint len, bool tp, Poly &res) const {
res = *this;
res.resize(len);
if (len != cur_len)
init_rev(len);
if (!gn_table_ok)
init_gn_table();
for (uint i = 0; i < len; i++)
if (i < _Rev[i])
::swap(res[i], res[_Rev[i]]);
for (uint l = 2, lg = 1; l <= len; l <<= 1, lg++) {
uint m = l >> 1;
Z gn = GN[lg];
for (uint i = 0; i < len; i += l) {
Z g = 1;
for (uint j = 0; j < m; j++, g *= gn) {
Z tmp = res[i + j + m] * g;
res[i + j + m] = res[i + j] - tmp;
res[i + j] += tmp;
}
}
}
if (!tp) {
reverse(res.begin() + 1, res.begin() + len);
auto inv = Z(len).inv();
For(i, 0, len - 1) res[i] *= inv;
}
}
public:
Poly() = default;
Poly(int sz) { this->clear(), this->resize(sz); }
void operator+=(const Poly &rhs) {
int n_sz = max(this->size(), rhs.size()), rhs_sz = rhs.size(); // NOLINT
this->resize(n_sz);
For(i, 0, rhs_sz - 1) this->operator[](i) += rhs[i];
}
void operator-=(const Poly &rhs) {
int n_sz = max(this->size(), rhs.size()), rhs_sz = rhs.size(); // NOLINT
this->resize(n_sz);
For(i, 0, rhs_sz - 1) operator[](i) -= rhs[i];
}
void operator*=(const Poly &rhs) {
int N = 1, NN = this->size() + rhs.size() - 1; // NOLINT
while (N < NN)
N <<= 1;
static Poly x, y, ans{N};
this->NTT(N, 1, x), rhs.NTT(N, 1, y);
For(i, 0, N - 1) ans[i] = x[i] * y[i];
ans.NTT(N, 0, *this);
resize(NN);
}
#define setOper(x) \
[[nodiscard]] Poly operator x(const Poly &rhs) const { \
auto lhs = *this; \
lhs x## = rhs; \
return lhs; \
}
setOper(+) setOper(-) setOper(*)
#undef setOper
};
Poly A, B;
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
A.resize(n + 1), B.resize(m + 1);
copy(a, a + 1 + n, A.begin());
copy(b, b + 1 + m, B.begin());
A *= B;
For(i, 0, n + m) c[i] = A[i].value();
}
| Compilation | N/A | N/A | Compile Error | Score: N/A | 显示更多 |