結果
問題 | No.2272 多項式乗算 mod 258280327 |
ユーザー | 👑 Nachia |
提出日時 | 2023-04-14 21:58:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 32,172 bytes |
コンパイル時間 | 3,106 ms |
コンパイル使用メモリ | 154,200 KB |
実行使用メモリ | 26,336 KB |
最終ジャッジ日時 | 2024-10-10 12:43:53 |
合計ジャッジ時間 | 5,767 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,820 KB |
testcase_08 | AC | 2 ms
6,820 KB |
testcase_09 | AC | 2 ms
6,816 KB |
testcase_10 | AC | 1 ms
6,816 KB |
testcase_11 | AC | 2 ms
6,816 KB |
testcase_12 | AC | 2 ms
6,816 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 2 ms
6,816 KB |
testcase_16 | AC | 2 ms
6,820 KB |
testcase_17 | AC | 2 ms
6,816 KB |
testcase_18 | AC | 2 ms
6,816 KB |
testcase_19 | AC | 1 ms
6,820 KB |
testcase_20 | AC | 2 ms
6,820 KB |
testcase_21 | AC | 2 ms
6,816 KB |
testcase_22 | AC | 2 ms
6,820 KB |
testcase_23 | AC | 2 ms
6,816 KB |
testcase_24 | AC | 5 ms
6,816 KB |
testcase_25 | AC | 16 ms
6,820 KB |
testcase_26 | AC | 16 ms
6,820 KB |
testcase_27 | AC | 33 ms
6,820 KB |
testcase_28 | AC | 32 ms
6,820 KB |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
ソースコード
#line 1 "..\\Main.cpp" #line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math-modulo\\dynamic-mod-supply.hpp" #include <cassert> #line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\ext-gcd.hpp" #include <utility> #include <algorithm> #line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\ext-gcd.hpp" namespace nachia{ // ax + by = gcd(a,b) // return ( x, - ) std::pair<long long, long long> ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, a); } } // namespace nachia #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math-modulo\\dynamic-mod-supply.hpp" namespace nachia{ class DynamicModSupplier{ using u64 = unsigned long long; using u128 = unsigned __int128; using Int = unsigned int; private: u64 imod; Int mod; // atcoder library u64 reduce2(u64 z) const noexcept { // atcoder library #ifdef _MSC_VER u64 x; _umul128(z, im, &x); #else u64 x = (u64)(((u128)(z)*imod) >> 64); #endif return z - x * mod; } Int reduce(u64 z) const noexcept { Int v = reduce2(z); if(mod <= v) v += mod; return v; } public: DynamicModSupplier(unsigned int MOD = 998244353) : mod(MOD) { assert(2 <= MOD); assert(MOD < (1u << 31)); imod = (u64)(-1) / mod + 1; } Int add(Int a, Int b) const { a += b; if(a >= mod){ a -= mod; } return a; } Int sub(Int a, Int b) const { a -= b; if(a >= mod){ a += mod; } return a; } Int mul(Int a, Int b) const { return reduce((u64)a * b); } Int muladd(Int a, Int b, Int c) const { return reduce((u64)a * b + c); } Int inv(Int a) const { Int v = ExtGcd(a, mod).first; return (v < mod) ? v : (v + mod); } Int pow(Int a, u64 i) const { Int r = a, ans = 1; while(i){ if(i & 1) ans = mul(ans, r); i /= 2; r = mul(r, r); } return ans; } Int getMod() const { return mod; } }; } // namespace nachia #line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math-modulo\\garner.hpp" #include <vector> namespace nachia{ template<class FinishType> struct GarnerMod{ using Int = unsigned int; using IntLong = unsigned long long; std::vector<Int> mods; std::vector<DynamicModSupplier> dynmods; std::vector<std::vector<Int>> table_coeff; std::vector<Int> table_coeffinv; void precalc(std::vector<Int> new_mods){ mods = std::move(new_mods); dynmods.resize(mods.size()); for(size_t i=0; i<mods.size(); i++) dynmods[i] = DynamicModSupplier(mods[i]); int nmods = mods.size(); table_coeff.assign(nmods+1, std::vector<Int>(nmods, 1)); for(int j=0; j<nmods; j++){ for(int k=0; k<nmods; k++) table_coeff[j+1][k] = table_coeff[j][k]; for(int k=j+1; k<nmods; k++) table_coeff[j+1][k] = dynmods[k].mul(table_coeff[j+1][k], mods[j] % mods[k]); } table_coeffinv.resize(nmods); for(int i=0; i<nmods; i++) table_coeffinv[i] = dynmods[i].inv(table_coeff[i][i]); } FinishType calc(const std::vector<Int>& x){ int nmods = mods.size(); std::vector<Int> table_const(nmods); FinishType res = 0; FinishType res_coeff = 1; for(int j=0; j<nmods; j++){ Int t = dynmods[j].mul(dynmods[j].sub(x[j], table_const[j]), table_coeffinv[j]); for(int k=j+1; k<nmods; k++){ table_const[k] = dynmods[k].muladd(t, table_coeff[j][k], table_const[k]); } res += res_coeff * FinishType(t); res_coeff *= mods[j]; } return res; } std::vector<FinishType> calc(std::vector<std::vector<Int>> x){ int n = x[0].size(), m = x.size(); std::vector<FinishType> res(n); std::vector<Int> buf(m); for(int i=0; i<n; i++){ for(int j=0; j<m; j++) buf[j] = x[j][i]; res[i] = calc(buf); } return res; } }; } // namespace nachia #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\fps\\fps-ntt.hpp" #include <string> #line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\fps\\fps-ntt.hpp" #include <iostream> #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math-modulo\\modulo-primitive-root.hpp" namespace nachia{ template<unsigned int MOD> struct PrimitiveRoot{ using u64 = unsigned long long; static constexpr u64 powm(u64 a, u64 i) { u64 res = 1, aa = a; while(i){ if(i & 1) res = res * aa % MOD; aa = aa * aa % MOD; i /= 2; } return res; } static constexpr bool ExamineVal(unsigned int g){ unsigned int t = MOD - 1; for(u64 d=2; d*d<=t; d++) if(t % d == 0){ if(powm(g, (MOD - 1) / d) == 1) return false; while(t % d == 0) t /= d; } if(t != 1) if(powm(g, (MOD - 1) / t) == 1) return false; return true; } static constexpr unsigned int GetVal(){ for(unsigned int x=2; x<MOD; x++) if(ExamineVal(x)) return x; return 0; } static const unsigned int val = GetVal(); }; } // namespace nachia #line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\combination.hpp" namespace nachia{ template<class Modint> class Comb{ private: std::vector<Modint> F; std::vector<Modint> iF; public: void extend(int newN){ int prevN = (int)F.size() - 1; if(prevN >= newN) return; F.resize(newN+1); iF.resize(newN+1); for(int i=prevN+1; i<=newN; i++) F[i] = F[i-1] * Modint::raw(i); iF[newN] = F[newN].inv(); for(int i=newN; i>prevN; i--) iF[i-1] = iF[i] * Modint::raw(i); } Comb(int n = 1){ F.assign(2, Modint(1)); iF.assign(2, Modint(1)); extend(n); } Modint factorial(int n) const { return F[n]; } Modint invFactorial(int n) const { return iF[n]; } Modint invOf(int n) const { return iF[n] * F[n-1]; } Modint comb(int n, int r) const { if(n < 0 || n < r || r < 0) return Modint(0); return F[n] * iF[r] * iF[n-r]; } Modint invComb(int n, int r) const { if(n < 0 || n < r || r < 0) return Modint(0); return iF[n] * F[r] * F[n-r]; } Modint perm(int n, int r) const { if(n < 0 || n < r || r < 0) return Modint(0); return F[n] * iF[n-r]; } Modint invPerm(int n, int r) const { if(n < 0 || n < r || r < 0) return Modint(0); return iF[n] * F[n-r]; } Modint operator()(int n, int r) const { return comb(n,r); } }; } // namespace nachia #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\misc\\bit-operations.hpp" namespace nachia{ int Popcount(unsigned long long c) noexcept { #ifdef __GNUC__ return __builtin_popcountll(c); #else c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3)); c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5)); c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17)); c = (c * (~0ull/257)) >> 56; return c; #endif } // please ensure x != 0 int MsbIndex(unsigned long long x) noexcept { #ifdef __GNUC__ return 63 - __builtin_clzll(x); #else int res = 0; for(int d=32; d>0; d>>=1) if(x >> d){ res |= d; x >>= d; } return res; #endif } // please ensure x != 0 int LsbIndex(unsigned long long x) noexcept { #ifdef __GNUC__ return __builtin_ctzll(x); #else return MsbIndex(x & -x); #endif } } #line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\fps\\ntt-interface.hpp" namespace nachia { template<class mint> struct NttInterface{ template<class Iter> void Butterfly(Iter, int) const {} template<class Iter> void IButterfly(Iter, int) const {} template<class Iter> void BitReversal(Iter a, int N) const { for(int i=0, j=0; j<N; j++){ if(i < j) std::swap(a[i], a[j]); for(int k = N>>1; k > (i^=k); k>>=1); } } }; } // namespace nachia #line 5 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\fps\\ntt-acl.hpp" #include <iterator> #line 8 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\fps\\ntt-acl.hpp" #include <array> namespace nachia{ constexpr int bsf_constexpr(unsigned int n) { int x = 0; while (!(n & (1 << x))) x++; return x; } template <class mint> struct NttFromAcl : NttInterface<mint> { using u32 = unsigned int; using u64 = unsigned long long; static int ceil_pow2(int n) { int x = 0; while ((1U << x) < (u32)(n)) x++; return x; } struct fft_info { static constexpr u32 g = nachia::PrimitiveRoot<mint::mod()>::val; static constexpr int rank2 = bsf_constexpr(mint::mod()-1); std::array<mint, rank2+1> root; std::array<mint, rank2+1> iroot; std::array<mint, std::max(0, rank2-1)> rate2; std::array<mint, std::max(0, rank2-1)> irate2; std::array<mint, std::max(0, rank2-2)> rate3; std::array<mint, std::max(0, rank2-2)> irate3; fft_info(){ root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2); iroot[rank2] = root[rank2].inv(); for(int i=rank2-1; i>=0; i--){ root[i] = root[i+1] * root[i+1]; iroot[i] = iroot[i+1] * iroot[i+1]; } mint prod = 1, iprod = 1; for(int i=0; i<=rank2-2; i++){ rate2[i] = root[i+2] * prod; irate2[i] = iroot[i+2] * iprod; prod *= iroot[i+2]; iprod *= root[i+2]; } prod = 1; iprod = 1; for(int i=0; i<=rank2-3; i++){ rate3[i] = root[i+3] * prod; irate3[i] = iroot[i+3] * iprod; prod *= iroot[i+3]; iprod *= root[i+3]; } } }; template<class RandomAccessIterator> void Butterfly(RandomAccessIterator a, int n) const { int h = ceil_pow2(n); static const fft_info info; int len = 0; while(len < h){ if(h-len == 1){ int p = 1 << (h-len-1); mint rot = 1; for(int s=0; s<(1<<len); s++){ int offset = s << (h-len); for(int i=0; i<p; i++){ auto l = a[i+offset]; auto r = a[i+offset+p] * rot; a[i+offset] = l+r; a[i+offset+p] = l-r; } if(s+1 != (1<<len)) rot *= info.rate2[LsbIndex(~(u32)(s))]; } len++; } else { int p = 1 << (h-len-2); mint rot = 1, imag = info.root[2]; for(int s=0; s<(1<<len); s++){ mint rot2 = rot * rot; mint rot3 = rot2 * rot; int offset = s << (h-len); for(int i=0; i<p; i++){ auto mod2 = 1ULL * mint::mod() * mint::mod(); auto a0 = 1ULL * a[i+offset].val(); auto a1 = 1ULL * a[i+offset+p].val() * rot.val(); auto a2 = 1ULL * a[i+offset+2*p].val() * rot2.val(); auto a3 = 1ULL * a[i+offset+3*p].val() * rot3.val(); auto a1na3imag = 1ULL * mint(a1 + mod2 - a3).val() * imag.val(); auto na2 = mod2 - a2; a[i+offset] = a0 + a2 + a1 + a3; a[i+offset+1*p] = a0 + a2 + (2 * mod2 - (a1 + a3)); a[i+offset+2*p] = a0 + na2 + a1na3imag; a[i+offset+3*p] = a0 + na2 + (mod2 - a1na3imag); } if(s+1 != (1<<len)) rot *= info.rate3[LsbIndex(~(u32)(s))]; } len += 2; } } } template<class RandomAccessIterator> void IButterfly(RandomAccessIterator a, int n) const { int h = ceil_pow2(n); static const fft_info info; constexpr int MOD = mint::mod(); int len = h; while(len){ if(len == 1){ int p = 1 << (h-len); mint irot = 1; for(int s=0; s<(1<<(len-1)); s++){ int offset = s << (h-len+1); for(int i=0; i<p; i++){ auto l = a[i+offset]; auto r = a[i+offset+p]; a[i+offset] = l+r; a[i+offset+p] = (u64)(MOD + l.val() - r.val()) * irot.val(); } if(s+1 != (1<<(len-1))) irot *= info.irate2[LsbIndex(~(u32)(s))]; } len--; } else { int p = 1 << (h-len); mint irot = 1, iimag = info.iroot[2]; for(int s=0; s<(1<<(len-2)); s++){ mint irot2 = irot * irot; mint irot3 = irot2 * irot; int offset = s << (h-len+2); for(int i=0; i<p; i++){ auto a0 = 1ULL * a[i+offset+0*p].val(); auto a1 = 1ULL * a[i+offset+1*p].val(); auto a2 = 1ULL * a[i+offset+2*p].val(); auto a3 = 1ULL * a[i+offset+3*p].val(); auto a2na3iimag = 1ULL * mint((MOD + a2 - a3) * iimag.val()).val(); a[i+offset] = a0 + a1 + a2 + a3; a[i+offset+1*p] = (a0 + (MOD - a1) + a2na3iimag) * irot.val(); a[i+offset+2*p] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val(); a[i+offset+3*p] = (a0 + (MOD - a1) + (MOD - a2na3iimag)) * irot3.val(); } if(s+1 != (1<<(len-2))) irot *= info.irate3[LsbIndex(~(u32)(s))]; } len -= 2; } } } }; } // namespace nachia #line 11 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\fps\\fps-ntt.hpp" namespace nachia { template<class Elem, class NttInst = NttFromAcl<Elem>> struct FpsNtt { public: using Fps = FpsNtt; using ElemTy = Elem; static constexpr unsigned int MOD = Elem::mod(); static constexpr int CONV_THRES = 30; static const NttInst nttInst; static const unsigned int zeta = nachia::PrimitiveRoot<MOD>::GetVal(); private: using u32 = unsigned int; static Elem ZeroElem() noexcept { return Elem(0); } static Elem OneElem() noexcept { return Elem(1); } static Comb<Elem> comb; std::vector<Elem> a; int RSZ(int& sz) const { return sz = (sz < 0 ? size() : sz); } public: int size() const noexcept { return a.size(); } Elem& operator[](int x) noexcept { return a[x]; } const Elem& operator[](int x) const noexcept { return a[x]; } Elem getCoeff(int x) const noexcept { return (0 <= x && x < size()) ? a[x] : ZeroElem(); } static Comb<Elem>& GetComb() { return comb; } static int BestNttSize(int x) noexcept { assert(x); return 1 << MsbIndex(x*2-1); } Fps move(){ return std::move(*this); } Fps& set(int i, Elem c){ a[i] = c; return *this; } Fps& removeLeadingZeros(){ int newsz = size(); while(newsz && a[newsz-1].val() == 0) newsz--; a.resize(newsz); if((int)a.capacity() / 4 > newsz) a.shrink_to_fit(); return *this; } FpsNtt(){} FpsNtt(int sz) : a(sz, ZeroElem()) {} FpsNtt(std::vector<Elem>&& src) : a(std::move(src)) {} FpsNtt(const std::vector<Elem>& src) : a(src) {} Fps& ntt() { capSize(BestNttSize(size())); nttInst.Butterfly(a.begin(), size()); return *this; } Fps& intt() { nttInst.IButterfly(a.begin(), a.size()); return times(Elem::raw(size()).inv()); } Fps nttDouble(Fps vanilla) const { int n = size(); assert(n == (n&-n)); // n is a power of 2 Elem q = Elem::raw(zeta).pow((Elem::mod() - 1) / (n*2)); Elem qq = OneElem(); for(int i=0; i<n; i++){ vanilla[i] *= qq; qq *= q; } vanilla.ntt(); Fps res = clip(0, n*2); for(int i=0; i<n; i++) res[n+i] = vanilla[i]; return res; } Fps nttDouble() const { return nttDouble(clip().intt().move()); } // Fps res(resSz); // for(int j=0; j<resSz-destL && j+srcL < srcR; j++) res[j+destL] = a.getCoeff(j+srcL) // if srcR is unspecified -> srcR = max(srcL, size()); // if resSz is unspecified -> resSz = destL + srcR - srcL Fps clip(int srcL, int srcR = -1, int destL = 0, int resSz = -1) const { srcR = RSZ(srcR); if(resSz < 0) resSz = destL + srcR - srcL; int rj = std::min(std::min(srcR, size()) - srcL, resSz - destL); Fps res(resSz); for(int j=std::max(0, -srcL); j<rj; j++) res[j+destL] = a[j+srcL]; return res; } Fps clip() const { return *this; } Fps& capSize(int l, int r) { if(r <= (int)size()) a.resize(r); if(size() <= l) a.resize(l, ZeroElem()); return *this; } Fps& capSize(int z){ a.resize(RSZ(z), ZeroElem()); return *this; } Fps& times(Elem x){ for(int i=0; i<size(); i++){ a[i] *= x; } return *this; } Fps& timesFactorial(int z = -1){ comb.extend(RSZ(z)); for(int i=0; i<z; i++){ a[i] *= comb.factorial(i); } return *this; } Fps& timesInvFactorial(int z = -1){ comb.extend(RSZ(z)); for(int i=0; i<z; i++){ a[i] *= comb.invFactorial(i); } return *this; } Fps& clrRange(int l, int r){ for(int i=l; i<r; i++){ a[i] = ZeroElem(); } return *this; } Fps& negate(){ for(auto& e : a){ e = -e; } return *this; } Fps& mulEach(const Fps& other, int maxi = -1){ maxi = std::min(RSZ(maxi), std::min(size(), other.size())); for(int i=0; i<maxi; i++) a[i] *= other[i]; return *this; } Fps& reverse(int sz = -1){ RSZ(sz); std::reverse(a.begin(), a.begin() + sz); return *this; } static Fps convolution(const Fps& a, const Fps& b, int sz = -1){ if(std::min(a.size(), b.size()) <= CONV_THRES){ if(a.size() > b.size()) return convolution(b, a, sz); if(sz < 0) sz = std::max(0, a.size() + b.size() - 1); std::vector<Elem> res(sz); for(int i=0; i<a.size(); i++) for(int j=0; j<b.size() && i+j<sz; j++) res[i+j] += a[i] * b[j]; return res; } int Z = BestNttSize(a.size() + b.size() - 1); return a.clip(0, Z).ntt().mulEach(b.clip(0, Z).ntt()).intt().capSize(sz).move(); } Fps convolve(const Fps& r, int sz = -1) const { return convolution(*this, r, sz); } // 1 // ----- = 1 + f + f^2 + f^3 + ... // 1-f Fps powerSum(int sz) const { RSZ(sz); if(sz == 0) return {}; int q = std::min(sz, 32); Fps x = Fps(q).set(0, OneElem()).move(); for(int i=1; i<q; i++) for(int j=1; j<=std::min(i,(int)a.size()-1); j++) x[i] += x[i-j] * a[j]; while(x.size() < sz){ int hN = x.size(), N = hN*2; Fps a = x.clip(0, N).ntt().move(); Fps b = clip(0, N).ntt().mulEach(a).intt().clrRange(0,hN).ntt().mulEach(a).intt().move(); for(int i=0; i<hN; i++) b[i] = x[i]; std::swap(b, x); } return x.capSize(sz).move(); } Fps inv(int sz = -1) const { RSZ(sz); Elem iA0 = a[0].inv(); return clip(0, std::min(sz, size())).times(-iA0).set(0, ZeroElem()).powerSum(sz).times(iA0).move(); } Fps& difference(){ if(size() == 0) return *this; for(int i=0; i+1<size(); i++) a[i] = a[i+1] * Elem::raw(i+1); return capSize(size()-1); } Fps& integral(){ if(size() == 0) return capSize(1); capSize(size()+1); comb.extend(size()); for(int i=size()-1; i>=1; i--) a[i] = a[i-1] * comb.invOf(i); return set(0, ZeroElem()); } Fps& EgfToOgf(){ comb.extend(size()); for(int i=0; i<size(); i++) a[i] *= comb.factorial(i); return *this; } Fps& OgfToEgf(){ comb.extend(size()); for(int i=0; i<size(); i++) a[i] *= comb.invFactorial(i); return *this; } Fps log(int sz = -1){ RSZ(sz); assert(sz != 0); assert(a[0].val() == 1); return convolution(inv(sz), clip().difference(), sz-1).integral(); } Fps exp(int sz = -1){ RSZ(sz); Fps res = Fps(1).set(0, OneElem()); while(res.size() < sz){ auto z = res.size(); auto tmp = res.capSize(z*2).log().set(0, -OneElem()).move(); for(int i=0; i<z*2 && i<size(); i++) tmp[i] -= a[i]; auto resntt = res.clip().ntt().mulEach(tmp.ntt()).intt().move(); for(int i=z; i<z*2; i++) res[i] = -resntt[i]; } return res.capSize(0, sz).move(); } Fps pow(unsigned long long k, int sz = -1){ int n = RSZ(sz); if(k == 0) return Fps(n).set(0, OneElem()).move(); int ctz = 0; while(ctz<n && a[ctz].val() == 0) ctz++; if((unsigned long long)ctz >= (n-1) / k + 1) return Fps(n); Elem a0 = a[ctz]; return clip(ctz, ctz+n-ctz*k).times(a0.inv()).log().times(Elem(k)).exp().times(a0.pow(k)).clip(0, -1, ctz*k); } auto begin(){ return a.begin(); } auto end(){ return a.end(); } auto begin() const { return a.begin(); } auto end() const { return a.end(); } std::string toString(std::string beg = "[ ", std::string delim = " ", std::string en = " ]") const { std::string res = beg; bool f = false; for(auto x : a){ if(f){ res += delim; } f = true; res += std::to_string(x.val()); } res += en; return res; } std::vector<Elem> getVectorMoved(){ return std::move(a); } Fps& operator+=(const Fps& r){ capSize(std::max(size(), r.size())); for(int i=0; i<r.size(); i++) a[i] += r[i]; return *this; } Fps& operator-=(const Fps& r){ capSize(std::max(size(), r.size())); for(int i=0; i<r.size(); i++) a[i] -= r[i]; return *this; } Fps operator+(const Fps& r) const { return (clip(0, std::max(size(), r.size())) += r).move(); } Fps operator-(const Fps& r) const { return (clip(0, std::max(size(), r.size())) -= r).move(); } Fps operator-() const { return (clip().negate()).move(); } Fps operator*(const Fps& r) const { return convolve(r).removeLeadingZeros().move(); } Fps& operator*=(const Fps& r){ return (*this) = operator*(r); } Fps& operator*=(Elem m){ return times(m); } Fps operator*(Elem m) const { return (clip() *= m).move(); } Elem eval(Elem x) const { Elem res = 0; for(int i=size()-1; i>=0; i--) res = res * x + a[i]; return res; } }; template<class Elem, class NttInst> Comb<Elem> FpsNtt<Elem, NttInst>::comb; template<class Elem, class NttInst> const NttInst FpsNtt<Elem, NttInst>::nttInst; } // namespace nachia #line 5 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math-modulo\\static-modint.hpp" namespace nachia{ template<unsigned int MOD> struct StaticModint{ private: using u64 = unsigned long long; unsigned int x; public: using my_type = StaticModint; template< class Elem > static Elem safe_mod(Elem x){ if(x < 0){ if(0 <= x+MOD) return x + MOD; return MOD - ((-(x+MOD)-1) % MOD + 1); } return x % MOD; } StaticModint() : x(0){} StaticModint(const my_type& a) : x(a.x){} StaticModint& operator=(const my_type&) = default; template< class Elem > StaticModint(Elem v) : x(safe_mod(v)){} unsigned int operator*() const noexcept { return x; } my_type& operator+=(const my_type& r) noexcept { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator+(const my_type& r) const noexcept { my_type res = *this; return res += r; } my_type& operator-=(const my_type& r) noexcept { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator-(const my_type& r) const noexcept { my_type res = *this; return res -= r; } my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; } my_type& operator*=(const my_type& r)noexcept { x = (u64)x * r.x % MOD; return *this; } my_type operator*(const my_type& r) const noexcept { my_type res = *this; return res *= r; } my_type pow(unsigned long long i) const noexcept { my_type a = *this, res = 1; while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; } return res; } my_type inv() const { return my_type(ExtGcd(x, MOD).first); } unsigned int val() const noexcept { return x; } static constexpr unsigned int mod() { return MOD; } static my_type raw(unsigned int val) noexcept { auto res = my_type(); res.x = val; return res; } my_type& operator/=(const my_type& r){ return operator*=(r.inv()); } my_type operator/(const my_type& r) const { return operator*(r.inv()); } }; } #line 5 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\fps\\convolution-uint64.hpp" namespace nachia{ struct ConvolutionUint64Supplier{ GarnerMod<unsigned long long> garner; ConvolutionUint64Supplier(){ garner.precalc(std::vector<unsigned int>{ 1107296257, 1711276033, 1811939329, 2013265921, 2113929217 }); } template<class Elem> static std::vector<unsigned int> SubConvolutionULL( const std::vector<unsigned long long>& a, const std::vector<unsigned long long>& b ){ using Fps = FpsNtt<Elem>; int z = a.size() + b.size() - 1; int z2 = Fps::BestNttSize(z); Fps ax(z2), bx(z2); for(int i=0; i<(int)a.size(); i++) ax[i] = Elem::raw(a[i] % Elem::mod()); for(int i=0; i<(int)b.size(); i++) bx[i] = Elem::raw(b[i] % Elem::mod()); ax.ntt().mulEach(bx.ntt()).intt(); std::vector<unsigned int> res(z); for(int i=0; i<z; i++) res[i] = ax[i].val(); return res; } std::vector<unsigned long long> operator()( std::vector<unsigned long long> a, std::vector<unsigned long long> b ){ if(a.empty() || b.empty()) return {}; std::vector<std::vector<unsigned int>> cx = { SubConvolutionULL<StaticModint<1107296257>>(a, b), SubConvolutionULL<StaticModint<1711276033>>(a, b), SubConvolutionULL<StaticModint<1811939329>>(a, b), SubConvolutionULL<StaticModint<2013265921>>(a, b), SubConvolutionULL<StaticModint<2113929217>>(a, b) }; return garner.calc(std::move(cx)); } }; } // namespace nachia #line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\misc\\fastio.hpp" #include <cstdio> #include <cctype> #include <cstdint> #line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\misc\\fastio.hpp" namespace nachia{ struct CInStream{ private: static const unsigned int INPUT_BUF_SIZE = 1 << 17; unsigned int p = INPUT_BUF_SIZE; static char Q[INPUT_BUF_SIZE]; public: using MyType = CInStream; char seekChar(){ if(p == INPUT_BUF_SIZE){ size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin); if(len != INPUT_BUF_SIZE) Q[len] = '\0'; p = 0; } return Q[p]; } void skipSpace(){ while(isspace(seekChar())) p++; } uint32_t nextU32(){ skipSpace(); uint32_t buf = 0; while(true){ char tmp = seekChar(); if('9' < tmp || tmp < '0') break; buf = buf * 10 + (tmp - '0'); p++; } return buf; } int32_t nextI32(){ skipSpace(); if(seekChar() == '-'){ p++; return (int32_t)(-nextU32()); } return (int32_t)nextU32(); } uint64_t nextU64(){ skipSpace(); uint64_t buf = 0; while(true){ char tmp = seekChar(); if('9' < tmp || tmp < '0') break; buf = buf * 10 + (tmp - '0'); p++; } return buf; } int64_t nextI64(){ skipSpace(); if(seekChar() == '-'){ p++; return (int64_t)(-nextU64()); } return (int64_t)nextU64(); } char nextChar(){ skipSpace(); char buf = seekChar(); p++; return buf; } std::string nextToken(){ skipSpace(); std::string buf; while(true){ char ch = seekChar(); if(isspace(ch) || ch == '\0') break; buf.push_back(ch); p++; } return buf; } MyType& operator>>(unsigned int& dest){ dest = nextU32(); return *this; } MyType& operator>>(int& dest){ dest = nextI32(); return *this; } MyType& operator>>(unsigned long& dest){ dest = nextU64(); return *this; } MyType& operator>>(long& dest){ dest = nextI64(); return *this; } MyType& operator>>(unsigned long long& dest){ dest = nextU64(); return *this; } MyType& operator>>(long long& dest){ dest = nextI64(); return *this; } MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; } MyType& operator>>(char& dest){ dest = nextChar(); return *this; } } cin; struct FastOutputTable{ char LZ[1000][4] = {}; char NLZ[1000][4] = {}; constexpr FastOutputTable(){ using u32 = uint_fast32_t; for(u32 d=0; d<1000; d++){ LZ[d][0] = ('0' + d / 100 % 10); LZ[d][1] = ('0' + d / 10 % 10); LZ[d][2] = ('0' + d / 1 % 10); LZ[d][3] = '\0'; } for(u32 d=0; d<1000; d++){ u32 i = 0; if(d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10); if(d >= 10) NLZ[d][i++] = ('0' + d / 10 % 10); if(d >= 1) NLZ[d][i++] = ('0' + d / 1 % 10); NLZ[d][i++] = '\0'; } } }; struct COutStream{ private: using u32 = uint32_t; using u64 = uint64_t; using MyType = COutStream; static const u32 OUTPUT_BUF_SIZE = 1 << 17; static char Q[OUTPUT_BUF_SIZE]; static constexpr FastOutputTable TB = FastOutputTable(); u32 p = 0; static constexpr u32 P10(u32 d){ return d ? P10(d-1)*10 : 1; } static constexpr u64 P10L(u32 d){ return d ? P10L(d-1)*10 : 1; } template<class T, class U> static void Fil(T& m, U& l, U x){ m = l/x; l -= m*x; } void next_dig9(u32 x){ u32 y; Fil(y, x, P10(6)); nextCstr(TB.LZ[y]); Fil(y, x, P10(3)); nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]); } public: void nextChar(char c){ Q[p++] = c; if(p == OUTPUT_BUF_SIZE){ fwrite(Q, p, 1, stdout); p = 0; } } void nextEoln(){ nextChar('\n'); } void nextCstr(const char* s){ while(*s) nextChar(*(s++)); } void nextU32(uint32_t x){ u32 y = 0; if(x >= P10(9)){ Fil(y, x, P10(9)); nextCstr(TB.NLZ[y]); next_dig9(x); } else if(x >= P10(6)){ Fil(y, x, P10(6)); nextCstr(TB.NLZ[y]); Fil(y, x, P10(3)); nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]); } else if(x >= P10(3)){ Fil(y, x, P10(3)); nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]); } else if(x >= 1) nextCstr(TB.NLZ[x]); else nextChar('0'); } void nextI32(int32_t x){ if(x >= 0) nextU32(x); else{ nextChar('-'); nextU32((u32)-x); } } void nextU64(uint64_t x){ u32 y = 0; if(x >= P10L(18)){ Fil(y, x, P10L(18)); nextU32(y); Fil(y, x, P10L(9)); next_dig9(y); next_dig9(x); } else if(x >= P10L(9)){ Fil(y, x, P10L(9)); nextU32(y); next_dig9(x); } else nextU32(x); } void nextI64(int64_t x){ if(x >= 0) nextU64(x); else{ nextChar('-'); nextU64((u64)-x); } } void writeToFile(bool flush = false){ fwrite(Q, p, 1, stdout); if(flush) fflush(stdout); p = 0; } COutStream(){ Q[0] = 0; } ~COutStream(){ writeToFile(); } MyType& operator<<(unsigned int tg){ nextU32(tg); return *this; } MyType& operator<<(unsigned long tg){ nextU64(tg); return *this; } MyType& operator<<(unsigned long long tg){ nextU64(tg); return *this; } MyType& operator<<(int tg){ nextI32(tg); return *this; } MyType& operator<<(long tg){ nextI64(tg); return *this; } MyType& operator<<(long long tg){ nextI64(tg); return *this; } MyType& operator<<(const std::string& tg){ nextCstr(tg.c_str()); return *this; } MyType& operator<<(const char* tg){ nextCstr(tg); return *this; } MyType& operator<<(char tg){ nextChar(tg); return *this; } } cout; char CInStream::Q[INPUT_BUF_SIZE]; char COutStream::Q[OUTPUT_BUF_SIZE]; } // namespace nachia #line 4 "..\\Main.cpp" int main(){ using nachia::cin; using nachia::cout; using namespace std; const unsigned int MOD = 258280327; int N; cin >> N; N++; vector<unsigned long long> A(N); for(auto& a : A){ cin >> a; a %= MOD; } int M; cin >> M; M++; vector<unsigned long long> B(M); for(auto& a : B){ cin >> a; a %= MOD; } auto C = nachia::ConvolutionUint64Supplier()(A, B); bool c = false; cout << (C.size()-1) << '\n'; for(auto& a : C){ a %= MOD; cout << (c ? " " : "") << a; c = true; } cout << '\n'; }