#1170547 (C++23) No.2686 商品券の使い道

提出ソース
結果

問題	No.2686 商品券の使い道
コンテスト
ユーザー	Today03
提出日時	2026-07-07 08:57:37
言語	C++23 (gcc 15.2.0 + boost 1.90.0) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	140 ms / 3,000 ms
コード長	36,103 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	3,572 ms
コンパイル使用メモリ	239,960 KB
実行使用メモリ	52,616 KB
最終ジャッジ日時	2026-07-07 08:58:05
合計ジャッジ時間	8,683 ms
ジャッジサーバーID （参考情報）	judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 48
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifdef TODAY_KYOPRO

/*
 */

void run() {
    II(N, M, Q);
    VI2(B, A, N);

    vi suma(1 << N), sumbm(1 << N), sumbq(1 << N);
    rep(b, 1 << N) {
        ll sum = 0;
        rep(i, N) if(b >> i & 1) {
            suma[b] += A[i];
            sum += B[i];
        }
        sumbm[b] = (sum <= M);
        sumbq[b] = (sum <= Q);
    }

    auto am = suma, aq = suma;
    rep(i, 1 << N) {
        am[i] *= sumbm[i];
        aq[i] *= sumbq[i];
    }

    am = ZetaMobius::SubsetZeta<Monoid::Max<i64>>(am);
    aq = ZetaMobius::SubsetZeta<Monoid::Max<i64>>(aq);

    ii ans = 0;
    rep(i, 1 << N) {
        ii j = ((1 << N) - 1) ^ i;
        chmax(ans, am[i] + aq[j]);
    }

    say(ans);
}

void prep() {}

#else

// #define MULTI
//------>8-------- begin kyopro_library/template.hpp --------->8------

//------>8------ begin kyopro_library/base/include.hpp ------->8------

#include <iostream>
#include <algorithm>
#include <type_traits>
#include <vector>
#include <cassert>
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <utility>

using namespace std;
//------>8------- end kyopro_library/base/include.hpp -------->8------

//------>8------- begin kyopro_library/base/macro.hpp -------->8------

#define rep1(n) for(ii i = 0; i < (n); i++)
#define rep2(i, n) for(ii i = 0; i < (n); i++)
#define rep3(i, a, b) for(ii i = (a); i < (b); i++)
#define rep4(i, a, b, c) for(ii i = (a); i < (b); i += (c))
#define rep_overload(a, b, c, d, e, ...) e
#define rep(...) rep_overload(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define per1(n) for(ii i = (n) - 1; i >= 0; i--)
#define per2(i, n) for(ii i = (n) - 1; i >= 0; i--)
#define per3(i, a, b) for(ii i = (b) - 1; i >= (a); i--)
#define per4(i, a, b, c) for(ii i = (b) - 1; i >= (a); i -= (c))
#define per_overload(a, b, c, d, e, ...) e
#define per(...) per_overload(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__)

#define fore(x, a) for(auto &x : a)

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

#define QYN(q, a, b) ((q) ? (a) : (b))

#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define mkt make_tuple
#define fi first
#define se second

#define vv(type, name, a, ...) \
    vector<vector<type>> name(a, vector<type>(__VA_ARGS__))
#define vvv(type, name, a, b, ...)     \
    vector<vector<vector<type>>> name( \
        a, vector<vector<type>>(b, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)         \
    vector<vector<vector<vector<type>>>> name( \
        a, vector<vector<vector<type>>>(       \
               b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define vvvvv(type, name, a, b, c, d, ...)             \
    vector<vector<vector<vector<vector<type>>>>> name( \
        a, vector<vector<vector<vector<type>>>>(       \
               b, vector<vector<vector<type>>>(        \
                      c, vector<vector<type>>(d, vector<type>(__VA_ARGS__)))))

#define applyv(v, f)      \
    [&]() {               \
        auto &&_v = (v);  \
        for(auto &x : _v) \
            f(x);         \
    }()
#define mapv(v, f)                                           \
    [&]() {                                                  \
        auto &&_v = (v);                                     \
        using Type = std::decay_t<decltype(f(*_v.begin()))>; \
        std::vector<Type> ret;                               \
        ret.reserve(_v.size());                              \
        for(const auto &x : _v)                              \
            ret.push_back(f(x));                             \
        return ret;                                          \
    }()

#define II(...)     \
    ii __VA_ARGS__; \
    input(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    input(__VA_ARGS__)
#define IDX(...)        \
    ii __VA_ARGS__;     \
    input(__VA_ARGS__); \
    input_index(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    input(__VA_ARGS__);
#define CHR(...)      \
    char __VA_ARGS__; \
    input(__VA_ARGS__);
#define LD(...)     \
    ld __VA_ARGS__; \
    input(__VA_ARGS__);
#define VI(A, N)     \
    vector<ii> A(N); \
    input(A);
#define VVI(A, N, M)                        \
    vector<vector<ii>> A(N, vector<ii>(M)); \
    input(A);
#define VL(A, N)     \
    vector<ll> A(N); \
    input(A);
#define VVL(A, N, M)                        \
    vector<vector<ll>> A(N, vector<ll>(M)); \
    input(A);
#define VPI(A, N) \
    vpi A(N);     \
    input(A);
#define VTI(A, N) \
    vti A(N);     \
    input(A);
#define VI2(A, B, N)       \
    vector<ii> A(N), B(N); \
    rep(i, N) cin >> A[i] >> B[i];
#define VL2(A, B, N)       \
    vector<ll> A(N), B(N); \
    rep(i, N) cin >> A[i] >> B[i];
#define VI3(A, B, C, N)          \
    vector<ii> A(N), B(N), C(N); \
    rep(i, N) cin >> A[i] >> B[i] >> C[i];
#define VL3(A, B, C, N)          \
    vector<ll> A(N), B(N), C(N); \
    rep(i, N) cin >> A[i] >> B[i] >> C[i];
#define VST(A, N)        \
    vector<string> A(N); \
    input(A);
#define IN2(A, B) rep(i, siz(A)) cin >> A[i] >> B[i];
#define IN3(A, B, C) rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i];
#define IN4(A, B, C, D) rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i] >> D[i];
#define IN5(A, B, C, D, E) \
    rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i] >> D[i] >> E[i];
//------>8-------- end kyopro_library/base/macro.hpp --------->8------

//------>8-------- begin kyopro_library/base/type.hpp -------->8------

using i16 = short;
using i32 = int;
using i64 = long long;
using i128 = __int128_t;
using u16 = unsigned short;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
using f64 = double;
using f80 = long double;

using ii = i64;
using ll = i64;
using ull = u64;
using vi = vector<ii>;
using vvi = vector<vector<ii>>;
using vvvi = vector<vector<vector<ii>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using ii3 = array<ii, 3>;
using ii4 = array<ii, 4>;
using ii5 = array<ii, 5>;
using lll = i128;
using ulll = u128;
constexpr lll operator""_lll(ull x) { return static_cast<lll>(x); }
using ld = f80;
using str = string;
using vstr = vector<str>;

template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<vector<T>>;
template <typename T>
using VVV = vector<vector<vector<T>>>;
template <typename T>
using VVVV = vector<vector<vector<vector<T>>>>;
template <typename T>
using VVVVV = vector<vector<vector<vector<vector<T>>>>>;
template <typename T>
using VVVVVV = vector<vector<vector<vector<vector<vector<T>>>>>>;

template <typename T>
using max_pq = priority_queue<T>;
template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using unset = unordered_set<T>;
template <typename T, typename T2>
using unmap = unordered_map<T, T2>;

template <typename T, typename U>
struct PR : pair<T, U> {
    template <typename... Args>
    PR(Args... args) : pair<T, U>(args...) {}
    using pair<T, U>::first;
    using pair<T, U>::second;
    PR& operator+=(const PR& r) {
        first += r.first;
        second += r.second;
        return *this;
    }
    PR& operator-=(const PR& r) {
        first -= r.first;
        second -= r.second;
        return *this;
    }
    PR& operator*=(const PR& r) {
        first *= r.first;
        second *= r.second;
        return *this;
    }
    template <typename S>
    PR& operator+=(const S& r) {
        first += r;
        second += r;
        return *this;
    }
    template <typename S>
    PR& operator-=(const S& r) {
        first -= r;
        second -= r;
        return *this;
    }
    template <typename S>
    PR& operator*=(const S& r) {
        first *= r;
        second *= r;
        return *this;
    }
    PR operator+(const PR& r) const { return PR(*this) += r; }
    PR operator-(const PR& r) const { return PR(*this) -= r; }
    PR operator*(const PR& r) const { return PR(*this) *= r; }
    template <typename S>
    PR operator+(const S& r) const { return PR(*this) += r; }
    template <typename S>
    PR operator-(const S& r) const { return PR(*this) -= r; }
    template <typename S>
    PR operator*(const S& r) const { return PR(*this) *= r; }
    PR operator-() const { return PR{-first, -second}; }
};
using pi = PR<ii, ii>;
using vpi = vector<pi>;
using vvpi = vector<vector<pi>>;
using pl = PR<ll, ll>;
using vpl = vector<pl>;
using vvpl = vector<vector<pl>>;

template <typename T, typename U, typename V>
struct TR : tuple<T, U, V> {
    using tuple<T, U, V>::tuple;
    T& x = get<0>(*this);
    U& y = get<1>(*this);
    V& z = get<2>(*this);
    TR() : tuple<T, U, V>() {}
    TR(const T& a, const U& b, const V& c) : tuple<T, U, V>(a, b, c) {}
    TR(const TR& other) : tuple<T, U, V>(other), x(get<0>(*this)), y(get<1>(*this)), z(get<2>(*this)) {}
    TR(TR&& other) noexcept : tuple<T, U, V>(move(other)), x(get<0>(*this)), y(get<1>(*this)), z(get<2>(*this)) {}
    TR& operator=(const TR& other) {
        tuple<T, U, V>::operator=(other);
        return *this;
    }
    TR& operator=(TR&& other) noexcept {
        tuple<T, U, V>::operator=(move(other));
        return *this;
    }
};
using ti = TR<ii, ii, ii>;
using vti = vector<ti>;
using vvti = vector<vector<ti>>;
using tl = TR<ll, ll, ll>;
using vtl = vector<ti>;
using vvtl = vector<vector<tl>>;

const i32 INF = 1e9 + 10;
const i64 INFL = 4e18;
const i128 INFLL = 1_lll << 120;

template <typename T>
constexpr T inf = 0;
template <>
constexpr i32 inf<i32> = INF;
template <>
constexpr i64 inf<i64> = INFL;
template <>
constexpr i128 inf<i128> = INFLL;
template <>
constexpr u32 inf<u32> = INF;
template <>
constexpr u64 inf<u64> = INFL;
template <>
constexpr u128 inf<u128> = INFLL;
template <>
constexpr f64 inf<f64> = numeric_limits<f64>::infinity();
template <>
constexpr f80 inf<f80> = numeric_limits<f80>::infinity();

istream& operator>>(istream& is, lll& x) {
    int c = is.peek();
    while(c == ' ' || c == '\n') is.get(), c = is.peek();
    bool neg = false;
    if(c == '-') neg = true, is.get();
    x = 0;
    while(isdigit(is.peek())) x = x * 10 + is.get() - '0';
    if(neg) x = -x;
    return is;
}

ostream& operator<<(ostream& os, lll x) {
    if(x < 0) os << '-', x = -x;
    if(x == 0) return os << '0';
    string s;
    while(x > 0) s += x % 10 + '0', x /= 10;
    reverse(s.begin(), s.end());
    return os << s;
}

#ifdef TDY
lll abs(lll x) {
    if(x < 0) return -x;
    return x;
}
lll gcd(lll a, lll b) {
    while(b) a %= b, swap(a, b);
    return a;
}
#endif
//------>8--------- end kyopro_library/base/type.hpp --------->8------

//------>8--------- begin kyopro_library/base/io.hpp --------->8------

const char NL = '\n';
void flush() { cout.flush(); }

inline string YesNo(bool f) { return f ? "Yes" : "No"; }
inline string YESNO(bool f) { return f ? "YES" : "NO"; }

template <typename T>
istream& operator>>(istream& is, vector<vector<T>>& v) {
    for(auto& x : v)
        for(auto& y : x) is >> y;
    return is;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for(auto& x : v) is >> x;
    return is;
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <class... T>
void input(T&... a) { (cin >> ... >> a); }

template <class T>
void input_index(T& a) { a--; }
template <class T, class... Ts>
void input_index(T& a, Ts&... b) {
    a--;
    input_index(b...);
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    os << p.fi << ' ' << p.se;
    return os;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const PR<T1, T2>& p) {
    os << p.fi << ' ' << p.se;
    return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3>& t) {
    os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t);
    return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const TR<T1, T2, T3>& t) {
    os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t);
    return os;
}
template <typename T1, typename T2, typename T3, typename T4>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4>& t) {
    os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t) << ' ' << get<3>(t);
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<vector<T>>>& a) {
    int I = a.size();
    for(int i = 0; i < I; i++) {
        int J = a[i].size();
        for(int j = 0; j < J; j++) {
            int K = a[i][j].size();
            for(int k = 0; k < K; k++) {
                os << a[i][j][k];
                if(k != K - 1) os << ' ';
            }
            os << NL;
        }
        if(i != I - 1) os << NL;
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& a) {
    int I = a.size();
    for(int i = 0; i < I; i++) {
        int J = a[i].size();
        for(int j = 0; j < J; j++) {
            os << a[i][j];
            if(j != J - 1) os << ' ';
        }
        if(i != I - 1) cout << NL;
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
    int n = a.size();
    for(int i = 0; i < n; i++) {
        os << a[i];
        if(i != n - 1) os << ' ';
    }
    return os;
}

template <typename T>
ostream& operator<<(ostream& os, const set<T>& a) {
    for(auto itr = a.begin(); itr != a.end(); itr++) {
        os << *itr;
        if(next(itr) != a.end()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const multiset<T>& a) {
    for(auto itr = a.begin(); itr != a.end(); itr++) {
        os << *itr;
        if(next(itr) != a.end()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const deque<T>& a) {
    for(auto itr = a.begin(); itr != a.end(); itr++) {
        os << *itr;
        if(next(itr) != a.end()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, queue<T> a) {
    while(!a.empty()) {
        os << a.front();
        a.pop();
        if(a.size()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, priority_queue<T> a) {
    while(!a.empty()) {
        os << a.top();
        a.pop();
        if(a.size()) os << ' ';
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, priority_queue<T, vector<T>, greater<T>> a) {
    while(!a.empty()) {
        os << a.top();
        a.pop();
        if(a.size()) os << ' ';
    }
    return os;
}
template <typename T, auto N>
ostream& operator<<(ostream& os, array<T, N> a) {
    for(int i = 0; i < N; i++) {
        os << a[i];
        if(i != N - 1) os << ' ';
    }
    return os;
}

template <class T, class... Ts>
void put(const T& a, const Ts&... b) {
    cout << a;
    (void)(cout << ... << b);
}

template <class T, class... Ts>
void line(const T& a, const Ts&... b) {
    cout << a;
    (void)(cout << ... << (cout << ' ', b));
    cout << ' ';
}

void say() { cout << '\n'; }
template <class T, class... Ts>
void say(const T& a, const Ts&... b) {
    cout << a;
    (void)(cout << ... << (cout << ' ', b));
    cout << '\n';
}

void esay() {
#ifdef TDY
    cerr << endl;
#endif
}
template <class T, class... Ts>
void esay(const T& a, const Ts&... b) {
#ifdef TDY
    cerr << a;
    (void)(cerr << ... << (cerr << ' ', b));
    cerr << endl;
#endif
}

#define O(...)            \
    {                     \
        say(__VA_ARGS__); \
        return;           \
    }
//------>8---------- end kyopro_library/base/io.hpp ---------->8------

//------>8-------- begin kyopro_library/base/util.hpp -------->8------

template <typename T>
inline ii siz(const T& v) { return v.size(); }

template <typename A, typename B>
A amin(A a, B b) {
    if(a > b) return b;
    return a;
}
template <typename A, typename B>
A amax(A a, B b) {
    if(a < b) return b;
    return a;
}

template <typename A, typename B>
bool chmin(A& a, B b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <typename A, typename B>
bool chmax(A& a, B b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
T minv(const vector<T>& v) {
    if(v.empty()) return inf<T>;
    return *ranges::min_element(v);
}
template <typename T>
T maxv(const vector<T>& v) {
    if(v.empty()) return -inf<T>;
    return *ranges::max_element(v);
}
template <typename T>
T sumv(const vector<T>& v) { return reduce(v.begin(), v.end()); }

template <typename T>
ii minidx(const vector<T>& v) { return ranges::min_element(v) - v.begin(); }
template <typename T>
ii maxidx(const vector<T>& v) { return ranges::max_element(v) - v.begin(); }

template <typename T>
ii lob(const vector<T>& v, const T& x) { return ranges::lower_bound(v, x) - v.begin(); }
template <typename T>
ii upb(const vector<T>& v, const T& x) { return ranges::upper_bound(v, x) - v.begin(); }
template <typename T>
ii find(const vector<T>& v, const T& x) {
    for(ii i = 0; i < siz(v); i++)
        if(v[i] == x) return i;
    return siz(v);
}
template <typename T>
ii find_last(const vector<T>& v, const T& x) {
    for(ii i = siz(v) - 1; i >= 0; i--)
        if(v[i] == x) return i;
    return -1;
}

template <typename T>
void unique(vector<T>& v) {
    ranges::sort(v);
    v.erase(unique(v.begin(), v.end()), v.end());
}
template <typename T>
vector<T> compress(vector<T> v) {
    auto w = v;
    unique(w);
    for(T& x : v) x = lob(w, x);
    return v;
}

ii countv(const auto& a, auto v) {
    return count(a.begin(), a.end(), v);
}

void insertv(auto& a, ii idx, auto v) {
    assert(idx <= siz(a));
    a.insert(a.begin() + idx, v);
}

void erasev(auto& a, ii idx) {
    assert(idx < siz(a));
    a.erase(a.begin() + idx);
}

// 先頭をoffset個分後ろに
void rotatebackv(auto& a, ii offset) {
    offset %= siz(a);
    rotate(a.begin(), a.end() - offset, a.end());
}

// 末尾をoffset個分前の方に
void rotatefrontv(auto& a, ii offset) {
    offset %= siz(a);
    rotate(a.begin(), a.begin() + offset, a.end());
}

auto mkinsert(const auto& a, ii idx, auto v) {
    auto b = a;
    insertv(b, idx, v);
    return b;
}

auto mkerase(const auto& a, ii idx) {
    auto b = a;
    erasev(b, idx);
    return b;
}

auto mkpush(const auto& a, auto v) {
    auto b = a;
    b.push_back(v);
    return b;
}

template <typename T>
V<T> mkslice(const V<T>& a, ii l, ii r) {
    assert(l <= r && l >= 0 && r <= siz(a));
    V<T> b(a.begin() + l, a.begin() + r);
    return b;
}

template <typename T>
V<T> mkconcat(const V<T>& a, const V<T>& b) {
    auto ret = a;
    ret.reserve(siz(a) + siz(b));
    for(auto x : b) ret.push_back(x);
    return ret;
}

template <typename A, typename B>
vector<PR<A, B>> zip(const vector<A>& a, const vector<B>& b) {
    ii n = siz(a);
    vector<PR<A, B>> ret(n);
    for(ii i = 0; i < n; i++) ret[i] = {a[i], b[i]};
    return ret;
}

template <typename A, typename B, typename C>
vector<tuple<A, B, C>> zip(const vector<A>& a, const vector<B>& b, const vector<C>& c) {
    ii n = siz(a);
    vector<tuple<A, B, C>> ret(n);
    for(ii i = 0; i < n; i++) ret[i] = {a[i], b[i], c[i]};
    return ret;
}

template <typename A, typename B>
PR<vector<A>, vector<B>> unzip(const vector<PR<A, B>>& p) {
    ii n = siz(p);
    vector<A> reta(n);
    vector<B> retb(n);
    for(ii i = 0; i < n; i++) {
        reta[i] = p[i].first;
        retb[i] = p[i].second;
    }
    return mkp(reta, retb);
}

template <typename A, typename B, typename C>
TR<vector<A>, vector<B>, vector<C>> unzip(const vector<TR<A, B, C>>& p) {
    ii n = siz(p);
    vector<A> reta(n);
    vector<B> retb(n);
    vector<C> retc(n);
    for(ii i = 0; i < n; i++) {
        auto [a, b, c] = p[i];
        reta[i] = a;
        retb[i] = b;
        retc[i] = c;
    }
    return mkt(reta, retb, retc);
}

template <typename T>
T pick(max_pq<T>& v) {
    T ret = v.top();
    v.pop();
    return ret;
}
template <typename T>
T pick(min_pq<T>& v) {
    T ret = v.top();
    v.pop();
    return ret;
}
template <typename T>
T pick(queue<T>& v) {
    T ret = v.front();
    v.pop();
    return ret;
}
template <typename T>
T pick(vector<T>& v) {
    T ret = v.back();
    v.pop_back();
    return ret;
}
template <typename T>
T pickf(deque<T>& v) {
    T ret = v.front();
    v.pop_front();
    return ret;
}
template <typename T>
T pickb(deque<T>& v) {
    T ret = v.back();
    v.pop_back();
    return ret;
}

template <typename T>
bool nxperm(T& v) { return next_permutation(v.begin(), v.end()); }

template <typename T>
void operator++(V<T>& a, T) {
    for(auto itr = a.begin(); itr != a.end(); itr++) (*itr)++;
}
template <typename T>
void operator--(V<T>& a, T) {
    for(auto itr = a.begin(); itr != a.end(); itr++) (*itr)--;
}
template <typename T>
void operator+=(V<T>& a, auto x) {
    for(auto itr = a.begin(); itr != a.end(); itr++) (*itr) += x;
}
template <typename T>
void operator-=(V<T>& a, auto x) {
    for(auto itr = a.begin(); itr != a.end(); itr++) (*itr) -= x;
}
template <typename T>
void operator*=(V<T>& a, auto x) {
    for(auto itr = a.begin(); itr != a.end(); itr++) (*itr) *= x;
}
template <typename T>
void operator/=(V<T>& a, auto x) {
    for(auto itr = a.begin(); itr != a.end(); itr++) (*itr) /= x;
}
template <typename T>
void operator%=(V<T>& a, auto x) {
    for(auto itr = a.begin(); itr != a.end(); itr++) (*itr) %= x;
}

template <typename T>
T myfloor(T a, T b) {
    assert(b != 0);
    if(b < 0) a = -a, b = -b;
    return a / b - (a % b < 0);
}
template <typename T>
T myceil(T a, T b) {
    assert(b != 0);
    if(b < 0) a = -a, b = -b;
    return a / b + (a % b > 0);
}
template <typename T>
T mymod(T a, T b) {
    assert(b != 0);
    if(b < 0) b = -b;
    if(a > 0) return a % b;
    return (a % b + b) % b;
}

template <typename T = ll, typename U>
vector<T> mksum(const vector<U>& v) {
    ii n = v.size();
    vector<T> ret(n + 1);
    for(ii i = 0; i < n; i++) ret[i + 1] = ret[i] + v[i];
    return ret;
}

template <typename T>
vector<T> mkpmax(const vector<T>& v) {
    ii n = v.size();
    vector<T> ret(n + 1, -inf<T>);
    for(ii i = 0; i < n; i++) ret[i + 1] = max(ret[i], v[i]);
    return ret;
}

template <typename T>
vector<T> mkpmin(const vector<T>& v) {
    ii n = v.size();
    vector<T> ret(n + 1, inf<T>);
    for(ii i = 0; i < n; i++) ret[i + 1] = min(ret[i], v[i]);
    return ret;
}

vi mkiota(ii n) {
    vi ret(n);
    iota(ret.begin(), ret.end(), 0);
    return ret;
}

template <typename T>
V<T> mkrev(V<T> A) {
    reverse(A.begin(), A.end());
    return A;
}

template <typename T>
vi mkinv(const V<T>& A) {
    ii n = siz(A);
    vi ret(maxv(A) + 1);
    for(ii i = 0; i < n; i++) ret[A[i]] = i;
    return ret;
}

template <typename T>
vvi mkinvvec(const V<T>& A) {
    ii n = siz(A);
    vvi ret(maxv(A) + 1);
    for(ii i = 0; i < n; i++) ret[A[i]].push_back(i);
    return ret;
}

template <typename T>
vi mkcount(const V<T>& A) {
    ii n = siz(A);
    vi ret(maxv(A) + 1);
    for(ii i = 0; i < n; i++) ret[A[i]]++;
    return ret;
}

template <typename T>
vi argsort(const V<T>& A) {
    vi idx = mkiota(siz(A));
    sort(idx.begin(), idx.end(), [&](ii i, ii j) {
        return (A[i] == A[j] ? i < j : A[i] < A[j]);
    });
    return idx;
}

template <typename T>
ii digsiz(T n) {
    ii ret = 0;
    while(n) {
        ret++;
        n /= 10;
    }
    return ret;
}

template <typename T>
vector<ii> digits(T n) {
    vector<ii> ret;
    while(n) {
        ret.push_back(n % 10);
        n /= 10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

i64 tenpow(ii r) {
    i64 ret = 1;
    while(r--) ret *= 10;
    return ret;
}

i64 intpow(i64 x, i64 r) {
    i64 ret = 1;
    while(r--) ret *= x;
    return ret;
}

template <typename T>
T intsqrt(T x) {
    ll sq = (T)sqrtl(ld(x));
    while(sq * sq > x) sq--;
    while((sq + 1) * (sq + 1) <= x) sq++;
    return sq;
}

ii ctoi(char c) {
    assert('0' <= c && c <= '9');
    return c - '0';
}
//------>8--------- end kyopro_library/base/util.hpp --------->8------

void run();
void prep();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
    prep();
#ifdef MULTI
    II(T);
    rep(t, T) {
#ifdef TDY
        esay("============ Case: #", t + 1, " ============");
#endif
        run();
    }
#else
    run();
#endif
}

#ifdef DEBUG
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif
//------>8--------- end kyopro_library/template.hpp ---------->8------

//------>8-- begin kyopro_library/algorithm/zeta_mobius.hpp -->8------
//------>8------- begin kyopro_library/others/bit.hpp -------->8------

/// @brief ビット演算
namespace Bit {
    /// @brief 1であるビットの個数を返す
    ii PopCount(i32 n) { return __builtin_popcount(n); }

    /// @brief 1であるビットの個数を返す
    ii PopCount(i64 n) { return __builtin_popcountll(n); }

    /// @brief popcountの偶奇を返す
    ii Parity(i32 n) { return __builtin_parity(n); }

    /// @brief popcountの偶奇を返す
    ii Parity(i64 n) { return __builtin_parityll(n); }

    /// @brief 最上位ビットの位置を返す
    ii TopBit(i32 n) { return n ? 31 - __builtin_clz(n) : -1; }

    /// @brief 最上位ビットの位置を返す
    ii TopBit(i64 n) { return n ? 63 - __builtin_clzll(n) : -1; }

    /// @brief 2進表現の長さを返す
    ii BitLength(i32 n) { return n ? 32 - __builtin_clz(n) : 1; }

    //// @brief 2進表現の長さを返す
    ii BitLength(i64 n) { return n ? 64 - __builtin_clzll(n) : 1; }

    /// @brief 最下位ビットの位置を返す
    ii LowBit(i32 n) { return n ? __builtin_ctz(n) : -1; }

    /// @brief 最下位ビットの位置を返す
    ii LowBit(i64 n) { return n ? __builtin_ctzll(n) : -1; }

    /// @brief 2のべき乗か否かを返す
    bool IsPowerOfTwo(i32 n) { return n && (n & -n) == n; }

    /// @brief 0~n-1ビットを立てたビットマスクを返す
    ll Mask(i32 n) { return (1LL << n) - 1; }

    /// @brief iビット目が立っているか否かを返す
    bool HasBit(i64 n, ii i) { return (n >> i & 1); }

    /// @brief sの部分集合を返す
    vi Subset(ii s) {
        vi ret;
        ii t = s;
        do {
            ret.push_back(t);
            --t &= s;
        } while(t != s);
        return ret;
    }

    /// @brief 整数nの2進表現を返す
    /// @param len ビット数
    /// @param rev 反転するか否か
    string ToBinary(i64 n, ii len = 32, bool rev = false) {
        string ret;
        rep(i, len) ret += (HasBit(n, rev ? len - 1 - i : i) ? '1' : '0');
        return ret;
    }
}  // namespace Bit
//------>8-------- end kyopro_library/others/bit.hpp --------->8------

/// @brief ゼータ変換・メビウス変換
namespace ZetaMobius {
    /// @brief 高速ゼータ変換（下位集合）
    /// @brief V'[s] = Σ_{t⊆s} V[t] なる V' を返す
    /// @note |V| = 2^N として O(N 2^N)
    template <typename Monoid>
    vector<typename Monoid::Type> SubsetZeta(vector<typename Monoid::Type> V) {
        int N = Bit::TopBit((int)V.size());
        rep(i, N) rep(j, 1 << N) {
            if(j >> i & 1) V[j] = Monoid::op(V[j], V[j ^ (1 << i)]);
        }
        return V;
    }

    /// @brief 高速ゼータ変換（上位集合）
    /// @brief V'[s] = Σ_{t⊇s} V[t] なる V' を返す
    /// @note |V| = 2^N として O(N 2^N)
    template <typename Monoid>
    vector<typename Monoid::Type> SupersetZeta(vector<typename Monoid::Type> V) {
        int N = Bit::TopBit((int)V.size());
        rep(i, N) rep(j, 1 << N) {
            if(~j >> i & 1) V[j] = Monoid::op(V[j], V[j ^ (1 << i)]);
        }
        return V;
    }

    /// @brief 高速メビウス変換（下位集合）
    /// @brief V[s] = Σ_{t⊆s} V'[t] なる V' を返す
    /// @note 逆変換が必要なので、v は可換群の元である必要がある
    /// @note |V| = 2^N として O(N 2^N)
    template <typename Abel>
    vector<typename Abel::Type> SubsetMobius(vector<typename Abel::Type> V) {
        int N = Bit::TopBit((int)V.size());
        rep(i, N) rep(j, 1 << N) {
            if(j >> i & 1) V[j] = Abel::op(V[j], Abel::inv(V[j ^ (1 << i)]));
        }
        return V;
    }

    /// @brief 高速メビウス変換（上位集合）
    /// @brief V[s] = Σ_{t⊇s} V'[t] なる V' を返す
    /// @note 逆変換が必要なので、v は可換群の元である必要がある
    /// @note |V| = 2^N として O(N 2^N)
    template <typename Abel>
    vector<typename Abel::Type> SupersetMobius(vector<typename Abel::Type> V) {
        int N = Bit::TopBit((int)V.size());
        rep(i, N) rep(j, 1 << N) {
            if(~j >> i & 1) V[j] = Abel::op(V[j], Abel::inv(V[j ^ (1 << i)]));
        }
        return V;
    }
}  // namespace ZetaMobius

/// @brief 畳み込み
namespace ConvolutionBit {
    template <typename Ring>
    vector<typename Ring::Type> OrConvolution(
        vector<typename Ring::Type> A,
        vector<typename Ring::Type> B) {
        using Type = typename Ring::Type;
        int N = max(A.size(), B.size());

        struct Abel {
            using Type = typename Ring::Type;
            static Type op(const Type& l, const Type& r) { return Ring::plus(l, r); }
            static Type inv(const Type& x) { return Ring::inv(x); }
            static Type id() { return Ring::zero(); }
        };

        A = move(ZetaMobius::SubsetZeta<Abel>(A));
        B = move(ZetaMobius::SubsetZeta<Abel>(B));
        rep(i, N) A[i] = Ring::mul(A[i], B[i]);
        A = move(ZetaMobius::SubsetMobius<Abel>(A));

        return A;
    }

    template <typename Ring>
    vector<typename Ring::Type> AndConvolution(
        vector<typename Ring::Type> A,
        vector<typename Ring::Type> B) {
        using Type = typename Ring::Type;
        int N = max(A.size(), B.size());

        struct Abel {
            using Type = typename Ring::Type;
            static Type op(const Type& l, const Type& r) { return Ring::plus(l, r); }
            static Type inv(const Type& x) { return Ring::inv(x); }
            static Type id() { return Ring::zero(); }
        };

        A = move(ZetaMobius::SupersetZeta<Abel>(A));
        B = move(ZetaMobius::SupersetZeta<Abel>(B));
        rep(i, N) A[i] = Ring::mul(A[i], B[i]);
        A = move(ZetaMobius::SupersetMobius<Abel>(A));

        return A;
    }

    template <typename Ring>
    vector<typename Ring::Type> SubsetConvolution(
        vector<typename Ring::Type> A,
        vector<typename Ring::Type> B) {
        using Type = typename Ring::Type;
        int N = max(A.size(), B.size());
        int M = Bit::TopBit(N);

        vector<vector<Type>> A2(M + 1, vector<Type>(N)), B2 = A2;
        rep(i, N) {
            A2[Bit::PopCount(i)][i] = A[i];
            B2[Bit::PopCount(i)][i] = B[i];
        }

        struct Abel {
            using Type = typename Ring::Type;
            static Type op(const Type& l, const Type& r) { return Ring::plus(l, r); }
            static Type inv(const Type& x) { return Ring::inv(x); }
            static Type id() { return Ring::zero(); }
        };

        rep(i, M + 1) {
            A2[i] = move(ZetaMobius::SubsetZeta<Abel>(A2[i]));
            B2[i] = move(ZetaMobius::SubsetZeta<Abel>(B2[i]));
        }

        vector<vector<Type>> conv(M + 1, vector<Type>(N));
        for(int i = 0; i <= M; i++)
            for(int j = 0; i + j <= M; j++) {
                rep(k, N) conv[i + j][k] = Ring::plus(conv[i + j][k], Ring::mul(A2[i][k], B2[j][k]));
            }

        rep(i, M + 1) conv[i] = move(ZetaMobius::SubsetMobius<Abel>(conv[i]));

        rep(i, N) A[i] = conv[Bit::PopCount(i)][i];
        return A;
    }
}  // namespace ConvolutionBit

//------>8------ begin kyopro_library/others/monoid.hpp ------>8------

/// @brief モノイド
namespace Monoid {
    /// @brief Minモノイド
    /// @tparam max_value 単位元
    template <typename T, T max_value = INF>
    struct Min {
        using Type = T;
        static Type id() { return max_value; }
        static Type op(const Type& a, const Type& b) { return min(a, b); }
    };

    /// @brief Maxモノイド
    /// @tparam min_value 単位元
    template <typename T, T min_value = -INF>
    struct Max {
        using Type = T;
        static Type id() { return min_value; }
        static Type op(const Type& a, const Type& b) { return max(a, b); }
    };

    /// @brief 和
    template <typename T>
    struct Sum {
        using Type = T;
        static Type id() { return 0; }
        static Type op(const Type& a, const Type& b) { return a + b; }
    };

    /// @brief （和，区間の長さ）
    template <typename T>
    struct SumPair {
        using Type = pair<T, int>;
        static Type id() { return make_pair(T(0), 0); }
        static Type op(const Type& a, const Type& b) { return {a.first + b.first, a.second + b.second}; }
    };

    template <typename T, T not_exist>
    struct Update {
        using Type = T;
        static Type id() { return not_exist; }
        static Type op(const Type& a, const Type& b) { return b == id() ? a : b; }
    };
}  // namespace Monoid
//------>8------- end kyopro_library/others/monoid.hpp ------->8------

//------>8------- begin kyopro_library/others/abel.hpp ------->8------

/// @brief 可換群
namespace Abel {
    /// @brief 和
    template <typename T>
    struct Sum {
        using Type = T;
        static Type id() { return T(0); }
        static Type op(const Type& a, const Type& b) { return a + b; }
        static Type inv(const Type& x) { return -x; }
    };

    template <typename T>
    struct Prod {
        using Type = T;
        static Type id() { return T(1); }
        static Type op(const Type& a, const Type& b) { return a * b; }
        static Type inv(const Type& x) { return Type(1) / x; }
    };

    /// @brief XOR
    template <typename T>
    struct Xor {
        using Type = T;
        static Type id() { return T(0); }
        static Type op(const Type& a, const Type& b) { return a ^ b; }
        static Type inv(const Type& x) { return x; }
    };
}  // namespace Abel
//------>8-------- end kyopro_library/others/abel.hpp -------->8------

//------>8------- begin kyopro_library/others/ring.hpp ------->8------

/// @brief 環・半環
namespace Ring {
    template <typename T>
    struct PlusMul {
        using Type = T;
        static Type plus(const Type& l, const Type& r) { return l + r; }
        static Type inv(const Type& x) { return -x; }
        static Type mul(const Type& l, const Type& r) { return l * r; }
        static Type zero() { return 0; }
        static Type one() { return 1; }
    };

    template <typename T, T max_value>
    struct MinPlus {
        using Type = T;
        static Type plus(const Type& l, const Type& r) { return min(l, r); }
        static Type mul(const Type& l, const Type& r) { return l + r; }
        static Type zero() { return max_value; }
        static Type one() { return 0; }
    };

    template <typename T, T min_value>
    struct MaxPlus {
        using Type = T;
        static Type plus(const Type& l, const Type& r) { return max(l, r); }
        static Type mul(const Type& l, const Type& r) { return l + r; }
        static Type zero() { return min_value; }
        static Type one() { return 0; }
    };
}  // namespace Ring
//------>8-------- end kyopro_library/others/ring.hpp -------->8------

//------>8--- end kyopro_library/algorithm/zeta_mobius.hpp --->8------

// #include <kyopro_library/utils.hpp>

#define TODAY_KYOPRO
#include __FILE__

#endif
// g.cpp
yukicoder

結果

ソースコード
