結果
| 問題 |
No.2272 多項式乗算 mod 258280327
|
| コンテスト | |
| ユーザー |
 cutmdo
|
| 提出日時 | 2023-04-14 22:31:34 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,811 bytes |
| コンパイル時間 | 11,312 ms |
| コンパイル使用メモリ | 308,692 KB |
| 最終ジャッジ日時 | 2025-02-12 07:15:54 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 31 WA * 2 |
ソースコード
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,avx512f")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>
#include <numeric>
#include <cassert>
#include <memory>
#include <random>
#include <functional>
#include <complex>
#include <immintrin.h>
#include <stdexcept>
#ifdef DEBUG
#include "./CompetitiveProgrammingCpp/Utils/debug.hpp"
#include "./CompetitiveProgrammingCpp/Utils/Timer.hpp"
#include "./CompetitiveProgrammingCpp/Utils/sample.hpp"
#else
#define dump(...)
template<class T>constexpr inline auto d_val(T a, T b) { return a; }
#endif
/* macro */
#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)((e)-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, (n))
#define RREP(i, n) RFOR(i, 0, (n))
#define REPC(x,c) for(const auto& x:(c))
#define REPI2(it,b,e) for(auto it = (b); it != (e); ++it)
#define REPI(it,c) REPI2(it, (c).begin(), (c).end())
#define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend())
#define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);)
#define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end())
#define ALL(x) (x).begin(),(x).end()
#define cauto const auto&
/* macro func */
template<class T>
inline auto sort(T& t) { std::sort(ALL(t)); }
template<class T>
inline auto rsort(T& t) { std::sort((t).rbegin(), (t).rend()); }
template<class T>
inline auto unique(T& t) { (t).erase(unique((t).begin(), (t).end()), (t).end()); }
template<class T, class S>
inline auto chmax(T& t, const S& s) { if(s > t) { t = s; return true; } return false; }
template<class T, class S>
inline auto chmin(T& t, const S& s) { if(s < t) { t = s; return true; } return false; }
inline auto BR() { std::cout << "\n"; }
/* type define */
using ll = long long;
using VS = std::vector<std::string>;
using VL = std::vector<long long>;
using VVL = std::vector<VL>;
using VVVL = std::vector<VVL>;
using VVVVL = std::vector<VVVL>;
using VVVVVL = std::vector<VVVVL>;
using VD = std::vector<double>;
template<class T>
using V = std::vector<T>;
template<class T = ll, class U = T>
using P = std::pair<T, U>;
using PAIR = P<ll>;
/* using std */
using std::cout;
constexpr char endl = '\n';
using std::cin;
using std::pair;
using std::string;
using std::stack;
using std::queue;
using std::deque;
using std::vector;
using std::list;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::set;
using std::unordered_set;
using std::unordered_multiset;
using std::multiset;
using std::bitset;
using std::priority_queue;
/* Initial processing */
struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing;
/* define hash */
namespace std {
template <> class hash<std::pair<ll, ll>> { public: size_t operator()(const std::pair<ll, ll>& x) const { return hash<ll>()(1000000000 * x.first + x.second); } };
}
/* input */
template<class T> std::istream& operator >> (std::istream& is, vector<T>& vec) { for(T& x : vec) is >> x; return is; }
/* constant value */
// constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
//=============================================================================================
struct ArbitraryModInt {
int x;
ArbitraryModInt() : x(0) {}
ArbitraryModInt(int64_t y) : x(y >= 0 ? y % mod() : (mod() - (-y) % mod()) % mod()) {}
static int& mod() {
static int mod = 0;
return mod;
}
static void set_mod(int md) {
mod() = md;
}
ArbitraryModInt& operator+=(const ArbitraryModInt& p) {
if((x += p.x) >= mod()) x -= mod();
return *this;
}
ArbitraryModInt& operator-=(const ArbitraryModInt& p) {
if((x += mod() - p.x) >= mod()) x -= mod();
return *this;
}
ArbitraryModInt& operator*=(const ArbitraryModInt& p) {
unsigned long long a = (unsigned long long) x * p.x;
unsigned xh = (unsigned)(a >> 32), xl = (unsigned)a, d, m;
asm("divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod()));
x = m;
return *this;
}
ArbitraryModInt& operator/=(const ArbitraryModInt& p) {
*this *= p.inverse();
return *this;
}
ArbitraryModInt operator-() const { return ArbitraryModInt(-x); }
ArbitraryModInt operator+(const ArbitraryModInt& p) const { return ArbitraryModInt(*this) += p; }
ArbitraryModInt operator-(const ArbitraryModInt& p) const { return ArbitraryModInt(*this) -= p; }
ArbitraryModInt operator*(const ArbitraryModInt& p) const { return ArbitraryModInt(*this) *= p; }
ArbitraryModInt operator/(const ArbitraryModInt& p) const { return ArbitraryModInt(*this) /= p; }
bool operator==(const ArbitraryModInt& p) const { return x == p.x; }
bool operator!=(const ArbitraryModInt& p) const { return x != p.x; }
ArbitraryModInt inverse() const {
int a = x, b = mod(), u = 1, v = 0, t;
while(b > 0) {
t = a / b;
std::swap(a -= t * b, b);
std::swap(u -= t * v, v);
}
return ArbitraryModInt(u);
}
ArbitraryModInt pow(int64_t n) const {
ArbitraryModInt ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend std::ostream& operator<<(std::ostream& os, const ArbitraryModInt& p) {
return os << p.x;
}
friend std::istream& operator>>(std::istream& is, ArbitraryModInt& a) {
int64_t t;
is >> t;
a = ArbitraryModInt(t);
return (is);
}
};
namespace FastFourierTransform {
using real = long double;
struct C {
real x, y;
C() : x(0), y(0) {}
C(real x, real y) : x(x), y(y) {}
inline C operator+(const C& c) const { return C(x + c.x, y + c.y); }
inline C operator-(const C& c) const { return C(x - c.x, y - c.y); }
inline C operator*(const C& c) const { return C(x * c.x - y * c.y, x * c.y + y * c.x); }
inline C conj() const { return C(x, -y); }
};
const real PI = acosl(-1);
int base = 1;
vector< C > rts = {{0, 0},
{1, 0}};
vector< int > rev = {0, 1};
void ensure_base(int nbase) {
if(nbase <= base) return;
rev.resize(1 << nbase);
rts.resize(1 << nbase);
for(int i = 0; i < (1 << nbase); i++) {
rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
}
while(base < nbase) {
real angle = PI * 2.0 / (1 << (base + 1));
for(int i = 1 << (base - 1); i < (1 << base); i++) {
rts[i << 1] = rts[i];
real angle_i = angle * (2 * i + 1 - (1 << base));
rts[(i << 1) + 1] = C(cos(angle_i), sin(angle_i));
}
++base;
}
}
void fft(vector< C >& a, int n) {
assert((n & (n - 1)) == 0);
int zeros = __builtin_ctz(n);
ensure_base(zeros);
int shift = base - zeros;
for(int i = 0; i < n; i++) {
if(i < (rev[i] >> shift)) {
std::swap(a[i], a[rev[i] >> shift]);
}
}
for(int k = 1; k < n; k <<= 1) {
for(int i = 0; i < n; i += 2 * k) {
for(int j = 0; j < k; j++) {
C z = a[i + j + k] * rts[j + k];
a[i + j + k] = a[i + j] - z;
a[i + j] = a[i + j] + z;
}
}
}
}
vector< int64_t > multiply(const vector< int >& a, const vector< int >& b) {
int need = (int)a.size() + (int)b.size() - 1;
int nbase = 1;
while((1 << nbase) < need) nbase++;
ensure_base(nbase);
int sz = 1 << nbase;
vector< C > fa(sz);
for(int i = 0; i < sz; i++) {
int x = (i < (int)a.size() ? a[i] : 0);
int y = (i < (int)b.size() ? b[i] : 0);
fa[i] = C(x, y);
}
fft(fa, sz);
C r(0, -0.25 / (sz >> 1)), s(0, 1), t(0.5, 0);
for(int i = 0; i <= (sz >> 1); i++) {
int j = (sz - i) & (sz - 1);
C z = (fa[j] * fa[j] - (fa[i] * fa[i]).conj()) * r;
fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conj()) * r;
fa[i] = z;
}
for(int i = 0; i < (sz >> 1); i++) {
C A0 = (fa[i] + fa[i + (sz >> 1)]) * t;
C A1 = (fa[i] - fa[i + (sz >> 1)]) * t * rts[(sz >> 1) + i];
fa[i] = A0 + A1 * s;
}
fft(fa, sz >> 1);
vector< int64_t > ret(need);
for(int i = 0; i < need; i++) {
ret[i] = llround(i & 1 ? fa[i >> 1].y : fa[i >> 1].x);
}
return ret;
}
};
template< typename T >
struct ArbitraryModConvolution {
using real = FastFourierTransform::real;
using C = FastFourierTransform::C;
ArbitraryModConvolution() = default;
vector< T > multiply(const vector< T >& a, const vector< T >& b, int need = -1) {
if(need == -1) need = a.size() + b.size() - 1;
int nbase = 0;
while((1 << nbase) < need) nbase++;
FastFourierTransform::ensure_base(nbase);
int sz = 1 << nbase;
vector< C > fa(sz);
for(int i = 0; i < a.size(); i++) {
fa[i] = C(a[i].x & ((1 << 15) - 1), a[i].x >> 15);
}
fft(fa, sz);
vector< C > fb(sz);
if(a == b) {
fb = fa;
} else {
for(int i = 0; i < b.size(); i++) {
fb[i] = C(b[i].x & ((1 << 15) - 1), b[i].x >> 15);
}
fft(fb, sz);
}
real ratio = 0.25 / sz;
C r2(0, -1), r3(ratio, 0), r4(0, -ratio), r5(0, 1);
for(int i = 0; i <= (sz >> 1); i++) {
int j = (sz - i) & (sz - 1);
C a1 = (fa[i] + fa[j].conj());
C a2 = (fa[i] - fa[j].conj()) * r2;
C b1 = (fb[i] + fb[j].conj()) * r3;
C b2 = (fb[i] - fb[j].conj()) * r4;
if(i != j) {
C c1 = (fa[j] + fa[i].conj());
C c2 = (fa[j] - fa[i].conj()) * r2;
C d1 = (fb[j] + fb[i].conj()) * r3;
C d2 = (fb[j] - fb[i].conj()) * r4;
fa[i] = c1 * d1 + c2 * d2 * r5;
fb[i] = c1 * d2 + c2 * d1;
}
fa[j] = a1 * b1 + a2 * b2 * r5;
fb[j] = a1 * b2 + a2 * b1;
}
fft(fa, sz);
fft(fb, sz);
vector< T > ret(need);
for(int i = 0; i < need; i++) {
int64_t aa = llround(fa[i].x);
int64_t bb = llround(fb[i].x);
int64_t cc = llround(fa[i].y);
aa = T(aa).x, bb = T(bb).x, cc = T(cc).x;
ret[i] = aa + (bb << 15) + (cc << 30);
}
return ret;
}
};
auto solve(ll n, const VL& f, ll m, const VL& g) {
constexpr ll mod = 258280327;
ArbitraryModInt::set_mod(mod);
V<ArbitraryModInt> fm; fm.reserve(n);
REPC(x, f) { fm.emplace_back(x % mod); }
V<ArbitraryModInt> gm; gm.reserve(m);
REPC(x, g) { gm.emplace_back(x % mod); }
dump(fm, gm);
ArbitraryModConvolution<ArbitraryModInt> fft;
auto ans = fft.multiply(fm, gm);
return ans;
}
signed main() {
ll n;
cin >> n;
VL f(n + 1);
cin >> f;
ll m;
cin >> m;
VL g(m + 1);
cin >> g;
auto ans = solve(n, f, m, g);
cout << ans.size() - 1 << endl;
REPC(x, ans) { cout << x << " "; }BR();
}