Submit Info #21136

Problem Lang User Status Time Memory
Subset Convolution cpp Nyaan AC 1492 ms 253.30 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 1476 ms 253.23 MiB
max_random_01 AC 1492 ms 253.30 MiB
max_random_02 AC 1466 ms 253.30 MiB
random_00 AC 1490 ms 253.24 MiB
random_01 AC 2 ms 0.67 MiB
random_02 AC 5 ms 0.86 MiB
small_00 AC 2 ms 0.64 MiB
small_01 AC 1 ms 0.67 MiB
small_02 AC 1 ms 0.67 MiB

#pragma region kyopro_template #define Nyaan_template #include <immintrin.h> #include <bits/stdc++.h> #define pb push_back #define eb emplace_back #define fi first #define se second #define each(x, v) for (auto &x : v) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) #define mem(a, val) memset(a, val, sizeof(a)) #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define die(...) \ do { \ out(__VA_ARGS__); \ return; \ } while (0) using namespace std; using ll = long long; template <class T> using V = vector<T>; using vi = vector<int>; using vl = vector<long long>; using vvi = vector<vector<int>>; using vd = V<double>; using vs = V<string>; using vvl = vector<vector<long long>>; using P = pair<long long, long long>; using vp = vector<P>; using pii = pair<int, int>; using vpi = vector<pair<int, int>>; constexpr int inf = 1001001001; constexpr long long infLL = (1LL << 61) - 1; template <typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template <typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; } template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; } void in() {} template <typename T, class... U> void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template <typename T, class... U> void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << " "; out(u...); } #ifdef NyaanDebug #define trc(...) \ do { \ cerr << #__VA_ARGS__ << " = "; \ dbg_out(__VA_ARGS__); \ } while (0) #define trca(v, N) \ do { \ cerr << #v << " = "; \ array_out(v, N); \ } while (0) #define trcc(v) \ do { \ cerr << #v << " = {"; \ each(x, v) { cerr << " " << x << ","; } \ cerr << "}" << endl; \ } while (0) template <typename T> void _cout(const T &c) { cerr << c; } void _cout(const int &c) { if (c == 1001001001) cerr << "inf"; else if (c == -1001001001) cerr << "-inf"; else cerr << c; } void _cout(const unsigned int &c) { if (c == 1001001001) cerr << "inf"; else cerr << c; } void _cout(const long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else if (c == -1001001001 || c == -((1LL << 61) - 1)) cerr << "-inf"; else cerr << c; } void _cout(const unsigned long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else cerr << c; } template <typename T, typename U> void _cout(const pair<T, U> &p) { cerr << "{ "; _cout(p.fi); cerr << ", "; _cout(p.se); cerr << " } "; } template <typename T> void _cout(const vector<T> &v) { int s = v.size(); cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } "; } template <typename T> void _cout(const vector<vector<T>> &v) { cerr << "[ "; for (const auto &x : v) { cerr << endl; _cout(x); cerr << ", "; } cerr << endl << " ] "; } void dbg_out() { cerr << endl; } template <typename T, class... U> void dbg_out(const T &t, const U &... u) { _cout(t); if (sizeof...(u)) cerr << ", "; dbg_out(u...); } template <typename T> void array_out(const T &v, int s) { cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } " << endl; } template <typename T> void array_out(const T &v, int H, int W) { cerr << "[ "; for (int i = 0; i < H; i++) { cerr << (i ? ", " : ""); array_out(v[i], W); } cerr << " ] " << endl; } #else #define trc(...) #define trca(...) #define trcc(...) #endif inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); } inline int lsb(unsigned long long a) { return __builtin_ctzll(a); } inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); } template <typename T> inline int getbit(T a, int i) { return (a >> i) & 1; } template <typename T> inline void setbit(T &a, int i) { a |= (1LL << i); } template <typename T> inline void delbit(T &a, int i) { a &= ~(1LL << i); } template <typename T> int lb(const vector<T> &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template <typename T> int ub(const vector<T> &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } template <typename T> int btw(T a, T x, T b) { return a <= x && x < b; } template <typename T, typename U> T ceil(T a, U b) { return (a + b - 1) / b; } constexpr long long TEN(int n) { long long ret = 1, x = 10; while (n) { if (n & 1) ret *= x; x *= x; n >>= 1; } return ret; } template <typename T> vector<T> mkrui(const vector<T> &v) { vector<T> ret(v.size() + 1); for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; return ret; }; template <typename T> vector<T> mkuni(const vector<T> &v) { vector<T> ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template <typename F> vector<int> mkord(int N, F f) { vector<int> ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template <typename T = int> vector<T> mkiota(int N) { vector<T> ret(N); iota(begin(ret), end(ret), 0); return ret; } template <typename T> vector<int> mkinv(vector<T> &v) { vector<int> inv(v.size()); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; void solve(); int main() { solve(); } #pragma endregion template <typename mint> vector<mint> subset_convolution(const vector<mint>& a, const vector<mint>& b) { int N = a.size(); assert(a.size() == b.size() && (N & (N - 1)) == 0); int l = __builtin_ctz(N); auto conv = [&](const vector<mint>& a, const vector<mint>& b) { vector<mint> c(l + 1); for (int i = 0; i < (int)a.size(); i++) for (int j = 0; j < (int)b.size(); j++) { if (i + j > l) break; c[i + j] += a[i] * b[j]; } return c; }; vector<vector<mint>> A(N, vector<mint>(l + 1)), B(N, vector<mint>(l + 1)); for (int i = 0; i < N; i++) A[i][0] = a[i], B[i][0] = b[i]; vector<mint> buf(l + 1); for (int n = N / 2, d = 1; n; n >>= 1, ++d) { for (int i = 0; i < N; i += 2 * n) { for (int j = i; j < i + n; j++) { // A[j + n] = A[j] + A[j + n] * x buf[0] = A[j][0]; for (int k = 1; k <= d; k++) buf[k] = A[j][k] + A[j + n][k - 1]; swap(A[j + n], buf); buf[0] = B[j][0]; for (int k = 1; k <= d; k++) buf[k] = B[j][k] + B[j + n][k - 1]; swap(B[j + n], buf); } } } for (int i = 0; i < N; i++) A[i] = conv(A[i], B[i]); for (int n = 1, d = 0; n < N; n <<= 1, ++d) { for (int i = 0; i < N; i += 2 * n) { for (int j = i; j < i + n; j++) { // A[j + n] -= A[j] for (int k = d; k <= l; k++) A[j + n][k] -= A[j][k]; // A[j] *= x for (int k = l; k > d; --k) A[j][k] = A[j][k - 1]; A[j][0] = mint(0); } } } vector<mint> C(N); for (int i = 0; i < N; i++) C[i] = A[i][l]; return C; } using namespace std; namespace fastio { static constexpr int SZ = 1 << 17; char ibuf[SZ], obuf[SZ]; int pil = 0, pir = 0, por = 0; struct Pre { char num[40000]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i * 4 + j] = n % 10 + '0'; n /= 10; } } } } constexpr pre; inline void load() { memcpy(ibuf, ibuf + pil, pir - pil); pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin); pil = 0; } inline void flush() { fwrite(obuf, 1, por, stdout); por = 0; } inline void rd(char& c) { c = ibuf[pil++]; } template <typename T> inline void rd(T& x) { if (pil + 32 > pir) load(); char c; do c = ibuf[pil++]; while (c < '-'); bool minus = 0; if (c == '-') { minus = 1; c = ibuf[pil++]; } x = 0; while (c >= '0') { x = x * 10 + (c & 15); c = ibuf[pil++]; } if (minus) x = -x; } inline void rd() {} template <typename Head, typename... Tail> inline void rd(Head& head, Tail&... tail) { rd(head); rd(tail...); } inline void wt(char c) { obuf[por++] = c; } template <typename T> inline void wt(T x) { if (por > SZ - 32) flush(); if (!x) { obuf[por++] = '0'; return; } if (x < 0) { obuf[por++] = '-'; x = -x; } int i = 12; char buf[16]; while (x >= 10000) { memcpy(buf + i, pre.num + (x % 10000) * 4, 4); x /= 10000; i -= 4; } int d = x < 100 ? (x < 10 ? 1 : 2) : (x < 1000 ? 3 : 4); memcpy(obuf + por, pre.num + x * 4 + 4 - d, d); por += d; memcpy(obuf + por, buf + i + 4, 12 - i); por += 12 - i; } inline void wt() {} template <typename Head, typename... Tail> inline void wt(Head head, Tail... tail) { wt(head); wt(tail...); } template<typename T> inline void wtn(T x){ wt(x, '\n'); } struct Dummy { Dummy() { atexit(flush); } } dummy; } // namespace fastio using fastio::rd; using fastio::wt; using fastio::wtn; using namespace std; template <uint32_t mod> struct LazyMontgomeryModInt { using mint = LazyMontgomeryModInt; using i32 = int32_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod; for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod) % mod; static_assert(r * mod == 1, "invalid, r * mod != 1"); static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod & 1) == 1, "invalid, mod % 2 == 0"); u32 a; constexpr LazyMontgomeryModInt() : a(0) {} constexpr LazyMontgomeryModInt(const int64_t &b) : a(reduce(u64(b % mod + mod) * n2)){}; static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * mod) >> 32; } constexpr mint &operator+=(const mint &b) { if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } constexpr mint &operator-=(const mint &b) { if (i32(a -= b.a) < 0) a += 2 * mod; return *this; } constexpr mint &operator*=(const mint &b) { a = reduce(u64(a) * b.a); return *this; } constexpr mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } constexpr mint operator+(const mint &b) const { return mint(*this) += b; } constexpr mint operator-(const mint &b) const { return mint(*this) -= b; } constexpr mint operator*(const mint &b) const { return mint(*this) *= b; } constexpr mint operator/(const mint &b) const { return mint(*this) /= b; } constexpr bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } constexpr bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } constexpr mint operator-() const { return mint() - mint(*this); } constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } constexpr mint inverse() const { return pow(mod - 2); } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { int64_t t; is >> t; b = LazyMontgomeryModInt<mod>(t); return (is); } constexpr u32 get() const { u32 ret = reduce(a); return ret >= mod ? ret - mod : ret; } static constexpr u32 get_mod() { return mod; } }; void solve() { int N; rd(N); using mint = LazyMontgomeryModInt<998244353>; using vm = V<mint>; vm a(1 << N), b(1 << N); int n; rep(i, 1 << N) { rd(n); a[i] = n; } rep(i, 1 << N) { rd(n); b[i] = n; } auto c = subset_convolution(a, b); rep(i, 1 << N) { if (i) wt(' '); wt(c[i].get()); } wt('\n'); }