This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub packer-jp/kyopro-lib-cpp
#include "math/subset_convolution.hpp"
#pragma once #include "../template.hpp" #include "fps.hpp" #include "fzt_fmt.hpp" template <typename V> vector<fps<V>> attach(const vector<V> &a) { vector<fps<V>> ret(a.size()); for (ll i : rep(a.size())) { ll j = __builtin_popcount(i); ret[i].resize(j + 1); ret[i][j] = a[i]; } return ret; } template <typename V> vector<V> detach(const vector<fps<V>> &a) { vector<V> ret(a.size()); for (ll i : rep(a.size())) ret[i] = a[i][__builtin_popcount(i)]; return ret; } template <typename V> vector<V> subset_convolution(vector<V> a, vector<V> b) { ll _n = max(a.size(), b.size()), n; for (n = 1; n < _n; n <<= 1) {} a.resize(n), b.resize(n); vector<fps<V>> _a = attach(a), _b = attach(b); fzt_sub(_a), fzt_sub(_b); for (ll i : rep(n)) _a[i] *= _b[i]; fmt_sub(_a); return detach(_a); }
#line 2 "math/subset_convolution.hpp" #line 2 "template.hpp" #include <bits/stdc++.h> using namespace std; #define all(a) begin(a), end(a) #define rall(a) rbegin(a), rend(a) #define uniq(a) (a).erase(unique(all(a)), (a).end()) #define t0 first #define t1 second using ll = long long; using ull = unsigned long long; using pll = pair<ll, ll>; using vll = vector<ll>; constexpr double pi = 3.14159265358979323846; constexpr ll dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0}; constexpr ll dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0}; constexpr ll sign(ll a) { return (a > 0) - (a < 0); } constexpr ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } constexpr ll cdiv(ll a, ll b) { return -fdiv(-a, b); } constexpr ll pw(ll n) { return 1ll << n; } constexpr ll flg(ll n) { return 63 - __builtin_clzll(n); } constexpr ll clg(ll n) { return n == 1 ? 0 : flg(n - 1) + 1; } constexpr ll safemod(ll x, ll mod) { return (x % mod + mod) % mod; } template <typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; template <typename T> constexpr T sq(const T &a) { return a * a; } template <typename T, typename U> constexpr bool chmax(T &a, const U &b) { return a < b ? a = b, true : false; } template <typename T, typename U> constexpr bool chmin(T &a, const U &b) { return a > b ? a = b, true : false; } template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &a) { os << "(" << a.first << ", " << a.second << ")"; return os; } template <typename T, typename U, typename V> ostream &operator<<(ostream &os, const tuple<T, U, V> &a) { os << "(" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &a) { os << "("; for (auto itr = a.begin(); itr != a.end(); ++itr) os << *itr << (next(itr) != a.end() ? ", " : ""); os << ")"; return os; } template <typename T> ostream &operator<<(ostream &os, const set<T> &a) { os << "("; for (auto itr = a.begin(); itr != a.end(); ++itr) os << *itr << (next(itr) != a.end() ? ", " : ""); os << ")"; return os; } template <typename T> ostream &operator<<(ostream &os, const multiset<T> &a) { os << "("; for (auto itr = a.begin(); itr != a.end(); ++itr) os << *itr << (next(itr) != a.end() ? ", " : ""); os << ")"; return os; } template <typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &a) { os << "("; for (auto itr = a.begin(); itr != a.end(); ++itr) os << *itr << (next(itr) != a.end() ? ", " : ""); os << ")"; return os; } #ifdef ONLINE_JUDGE #define dump(...) (void(0)) #else void debug() { cerr << endl; } template <typename Head, typename... Tail> void debug(Head &&head, Tail &&... tail) { cerr << head; if (sizeof...(Tail)) cerr << ", "; debug(tail...); } #define dump(...) cerr << __LINE__ << ": " << #__VA_ARGS__ << " = ", debug(__VA_ARGS__) #endif struct rep { struct itr { ll v; itr(ll v) : v(v) {} void operator++() { ++v; } ll operator*() const { return v; } bool operator!=(itr i) const { return v < *i; } }; ll l, r; rep(ll l, ll r) : l(l), r(r) {} rep(ll r) : rep(0, r) {} itr begin() const { return l; }; itr end() const { return r; }; }; struct per { struct itr { ll v; itr(ll v) : v(v) {} void operator++() { --v; } ll operator*() const { return v; } bool operator!=(itr i) const { return v > *i; } }; ll l, r; per(ll l, ll r) : l(l), r(r) {} per(ll r) : per(0, r) {} itr begin() const { return r - 1; }; itr end() const { return l - 1; }; }; struct io_setup { static constexpr int PREC = 20; io_setup() { cout << fixed << setprecision(PREC); cerr << fixed << setprecision(PREC); }; } iOS; #line 2 "math/fps.hpp" #line 2 "math/convolution.hpp" #line 2 "math/ntt.hpp" #line 4 "math/ntt.hpp" template <typename mint> void ntt(vector<mint> &a, bool inv = false) { ll n = a.size(), m = n >> 1; mint root = 2; while (root.pow((mint::mod() - 1) >> 1) == 1) root += 1; mint wn = root.pow((mint::mod() - 1) / n); if (inv) wn = wn.inv(); vector<mint> b(n); for (ll i = 1; i < n; i <<= 1, wn *= wn, swap(a, b)) { mint wj = 1; for (ll j = 0; j < m; j += i, wj *= wn) { for (ll k : rep(i)) { b[0 + (j << 1) + k] = (a[0 + j + k] + a[m + j + k]); b[i + (j << 1) + k] = (a[0 + j + k] - a[m + j + k]) * wj; } } } if (inv) { mint ninv = mint(n).inv(); for (mint &ai : a) ai *= ninv; } } template <typename mint> void intt(vector<mint> &a) { ntt(a, true); } #line 5 "math/convolution.hpp" template <typename V> vector<V> convolution_naive(vector<V> a, vector<V> b) { ll na = a.size(), nb = b.size(); vector<V> c(na + nb - 1); if (na < nb) swap(a, b), swap(na, nb); for (ll i : rep(na)) { for (ll j : rep(nb)) c[i + j] += a[i] * b[j]; } return c; } template <typename mint> vector<mint> convolution_ntt(vector<mint> a, vector<mint> b) { ll _n = a.size() + b.size() - 1, n; for (n = 1; n < _n; n <<= 1) {} a.resize(n), b.resize(n); ntt(a), ntt(b); for (ll i : rep(n)) a[i] *= b[i]; intt(a); a.resize(_n); return a; } template <typename mint> vector<mint> convolution(const vector<mint> &a, const vector<mint> &b) { if (min(a.size(), b.size()) <= 60) { return convolution_naive(a, b); } else { return convolution_ntt(a, b); } } #line 2 "math/modint.hpp" #line 4 "math/modint.hpp" template <typename M> struct modint { ll val; modint(ll val = 0) : val(val >= 0 ? val % M::mod : (M::mod - (-val) % M::mod) % M::mod) {} static ll mod() { return M::mod; } modint inv() const { ll a = val, b = M::mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return u; } modint pow(ll k) const { modint ret = 1, mul = val; while (k) { if (k & 1) ret *= mul; mul *= mul; k >>= 1; } return ret; } modint &operator+=(const modint &a) { if ((val += a.val) >= M::mod) val -= M::mod; return *this; } modint &operator-=(const modint &a) { if ((val += M::mod - a.val) >= M::mod) val -= M::mod; return *this; } modint &operator*=(const modint &a) { (val *= a.val) %= M::mod; return *this; } modint &operator/=(const modint &a) { return *this *= a.inv(); } modint operator+() const { return *this; } modint operator-() const { return modint(-val); } friend bool operator==(const modint &a, const modint &b) { return a.val == b.val; } friend bool operator!=(const modint &a, const modint &b) { return rel_ops::operator!=(a, b); } friend modint operator+(const modint &a, const modint &b) { return modint(a) += b; } friend modint operator-(const modint &a, const modint &b) { return modint(a) -= b; } friend modint operator*(const modint &a, const modint &b) { return modint(a) *= b; } friend modint operator/(const modint &a, const modint &b) { return modint(a) /= b; } friend istream &operator>>(istream &is, modint &a) { ll val; is >> val; a = modint(val); return is; } friend ostream &operator<<(ostream &os, const modint &a) { return os << a.val; } }; struct _998244353 { constexpr static ll mod = 998244353; }; struct _1000000007 { constexpr static ll mod = 1000000007; }; using modint998244353 = modint<_998244353>; using modint1000000007 = modint<_1000000007>; struct arbitrary { static ll mod; }; ll arbitrary::mod; #line 6 "math/fps.hpp" template <typename mint> struct fps : vector<mint> { using vector<mint>::vector; using vector<mint>::operator=; fps() : vector<mint>() {} fps(const mint &a) : vector<mint>(1, a) {} fps(const vector<mint> &a) : vector<mint>(a) {} fps(const fps &a) : vector<mint>(a) {} fps &operator=(const fps &a) { *this = (vector<mint>)a; return *this; } fps &operator+=(const fps &a) { if (a.size() > this->size()) this->resize(a.size()); for (ll i : rep(a.size())) (*this)[i] += a[i]; return *this; } fps &operator-=(const fps &a) { if (a.size() > this->size()) this->resize(a.size()); for (ll i : rep(a.size())) (*this)[i] -= a[i]; return *this; } fps &operator*=(const fps &a); fps &operator/=(const mint &a) { for (ll i : rep(this->size())) (*this)[i] /= a; return *this; }; fps &operator>>=(ll d) { if ((ll)this->size() <= d) { *this = {}; } else { this->erase(this->begin(), this->begin() + d); } return *this; } fps &operator<<=(ll d) { this->insert(this->begin(), d, 0); return *this; } fps &chdot(const fps &a) { for (ll i : rep(this->size())) { if (i < (ll)a.size()) { (*this)[i] *= a[i]; } else { (*this)[i] = 0; } } return *this; } fps prefix(ll d) const { return fps(this->begin(), this->begin() + min((ll)this->size(), d)); } fps differential() const { ll n = this->size(); fps ret(max(0ll, n - 1)); for (ll i : rep(1, n)) { ret[i - 1] = i * (*this)[i]; } return ret; } fps integral() const { ll n = this->size(); fps ret(n + 1); ret[0] = 0; if (n > 0) ret[1] = 1; for (ll i : rep(2, n + 1)) ret[i] = (-ret[mint::mod() % i]) * (mint::mod() / i); for (ll i : rep(n)) ret[i + 1] *= (*this)[i]; return ret; } fps inv(ll d) const { fps ret{(*this)[0].inv()}; for (ll m = 1; m < d; m <<= 1) ret = (ret + ret - ret * ret * this->prefix(m << 1)).prefix(m << 1); return ret.prefix(d); } fps log(ll d) const { assert((*this)[0] == 1); return (this->differential() * this->inv(d)).prefix(d - 1).integral(); } fps exp(ll d) const { assert(this->size() == 0 || (*this)[0] == 0); fps ret{1}; for (ll m = 1; m < d; m <<= 1) ret = (ret * (this->prefix(m << 1) + 1 - ret.log(m << 1))).prefix(m << 1); return ret.prefix(d); } fps pow(ll k, ll d) const { if (k == 0) { fps ret(d); if (d) ret[0] = 1; return ret; } for (ll i : rep(this->size())) { if ((*this)[i] != 0) { if (i > d / k) return fps(d); fps ret = (((*this * (*this)[i].inv()) >> i).log(d) * mint(k)).exp(d) * (*this)[i].pow(k); ret = (ret << (i * k)).prefix(d); ret.resize(d); return ret; } } return fps(d); } friend fps operator+(const fps &a) { return a; } friend fps operator-(const fps &a) { return fps() -= a; } friend fps operator+(const fps &a, const fps &b) { return fps(a) += b; } friend fps operator-(const fps &a, const fps &b) { return fps(a) -= b; } friend fps operator*(const fps &a, const fps &b) { return fps(a) *= b; } friend fps operator>>(const fps &a, ll d) { return fps(a) >>= d; } friend fps operator<<(const fps &a, ll d) { return fps(a) <<= d; } }; using m9 = modint998244353; template <> fps<m9> &fps<m9>::operator*=(const fps<m9> &a) { *this = convolution(*this, a); return *this; } template <> fps<m9> fps<m9>::inv(ll d) const { fps ret{(*this)[0].inv()}; for (ll m = 1; m < d; m <<= 1) { fps f = this->prefix(m << 1); fps g = ret; f.resize(m << 1), ntt(f); g.resize(m << 1), ntt(g); f.chdot(g); intt(f); f >>= m, f.resize(m << 1), ntt(f); f.chdot(g); intt(f); f = -f; ret.insert(ret.end(), f.begin(), f.begin() + m); } return ret.prefix(d); } template <> fps<m9> fps<m9>::exp(ll d) const { assert(this->size() == 0 || (*this)[0] == 0); fps ret{1}, g{1}, g_freq{1}; for (ll m = 1; m < d; m <<= 1) { fps ret_freq = ret.prefix(m); ret_freq.resize(m << 1), ntt(ret_freq); fps g_cont = g_freq; for (ll i : rep(m)) g_cont[i] *= ret_freq[i << 1]; intt(g_cont); g_cont >>= m >> 1; g_cont.resize(m), ntt(g_cont); g_cont.chdot(g_freq); intt(g_cont); g_cont = -g_cont; g.insert(g.end(), g_cont.begin(), g_cont.begin() + (m >> 1)); fps r = this->differential().prefix(m - 1); r.resize(m), ntt(r); for (ll i : rep(m)) r[i] *= ret_freq[i << 1]; intt(r); fps t = ret.differential() - r; t.insert(t.begin(), t.back()), t.pop_back(); t.resize(m << 1), ntt(t); g_freq = g, g_freq.resize(m << 1), ntt(g_freq); t.chdot(g_freq); intt(t), t.resize(m); fps u = (this->prefix(m << 1) - (t << m - 1).integral()) >> m; u.resize(m << 1), ntt(u); u.chdot(ret_freq); intt(u); ret += u.prefix(m) << m; } return ret.prefix(d); } #line 2 "math/fzt_fmt.hpp" #line 4 "math/fzt_fmt.hpp" template <typename V> void fzt_super(vector<V> &a) { for (ll i : rep(flg(a.size()))) { for (ll s : rep(a.size())) { if ((s >> i) & 1) a[s ^ pw(i)] += a[s]; } } } template <typename V> void fzt_sub(vector<V> &a) { for (ll i : rep(flg(a.size()))) { for (ll s : rep(a.size())) { if (!((s >> i) & 1)) a[s ^ pw(i)] += a[s]; } } } template <typename V> void fmt_super(vector<V> &a) { for (ll i : rep(flg(a.size()))) { for (ll s : rep(a.size())) { if ((s >> i) & 1) a[s ^ pw(i)] -= a[s]; } } } template <typename V> void fmt_sub(vector<V> &a) { for (ll i : rep(flg(a.size()))) { for (ll s : rep(a.size())) { if (!((s >> i) & 1)) a[s ^ pw(i)] -= a[s]; } } } #line 6 "math/subset_convolution.hpp" template <typename V> vector<fps<V>> attach(const vector<V> &a) { vector<fps<V>> ret(a.size()); for (ll i : rep(a.size())) { ll j = __builtin_popcount(i); ret[i].resize(j + 1); ret[i][j] = a[i]; } return ret; } template <typename V> vector<V> detach(const vector<fps<V>> &a) { vector<V> ret(a.size()); for (ll i : rep(a.size())) ret[i] = a[i][__builtin_popcount(i)]; return ret; } template <typename V> vector<V> subset_convolution(vector<V> a, vector<V> b) { ll _n = max(a.size(), b.size()), n; for (n = 1; n < _n; n <<= 1) {} a.resize(n), b.resize(n); vector<fps<V>> _a = attach(a), _b = attach(b); fzt_sub(_a), fzt_sub(_b); for (ll i : rep(n)) _a[i] *= _b[i]; fmt_sub(_a); return detach(_a); }