#587740 (C++17) No.1304 あなたは基本が何か知っていますか？私は知っています．

提出ソース

結果

問題	No.1304 あなたは基本が何か知っていますか？私は知っています．
ユーザー	Pachicobue
提出日時	2020-12-01 21:07:26
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	16,457 bytes
コンパイル時間	2,374 ms
コンパイル使用メモリ	215,420 KB
実行使用メモリ	7,800 KB
最終ジャッジ日時	2023-09-03 03:37:37
合計ジャッジ時間	11,315 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	114 ms 7,280 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	114 ms 7,532 KB
testcase_04	RE	-
testcase_05	AC	2 ms 4,380 KB
testcase_06	RE	-
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	115 ms 7,344 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	2 ms 4,376 KB
testcase_15	AC	2 ms 4,376 KB
testcase_16	AC	1 ms 4,376 KB
testcase_17	AC	114 ms 7,324 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	2 ms 4,380 KB
testcase_20	AC	2 ms 4,376 KB
testcase_21	AC	114 ms 7,228 KB
testcase_22	AC	1 ms 4,376 KB
testcase_23	AC	2 ms 4,376 KB
testcase_24	AC	2 ms 4,376 KB
testcase_25	AC	115 ms 7,324 KB
testcase_26	AC	115 ms 7,484 KB
testcase_27	AC	115 ms 7,272 KB
testcase_28	AC	114 ms 7,216 KB
testcase_29	AC	115 ms 7,216 KB
testcase_30	AC	114 ms 7,532 KB
testcase_31	AC	114 ms 7,540 KB
testcase_32	AC	114 ms 7,224 KB
testcase_33	AC	114 ms 7,232 KB
testcase_34	AC	115 ms 7,276 KB
testcase_35	AC	115 ms 7,340 KB
testcase_36	AC	115 ms 7,800 KB
testcase_37	AC	115 ms 7,332 KB
testcase_38	AC	114 ms 7,532 KB
testcase_39	AC	115 ms 7,584 KB
testcase_40	AC	114 ms 7,216 KB
testcase_41	AC	115 ms 7,592 KB
testcase_42	AC	115 ms 7,272 KB
testcase_43	AC	115 ms 7,280 KB
testcase_44	AC	115 ms 7,600 KB
04_evil_A_01	RE	-
04_evil_A_02	RE	-
04_evil_A_03	RE	-
04_evil_A_04	RE	-
04_evil_A_05	RE	-
04_evil_A_06	RE	-
04_evil_A_07	RE	-
04_evil_A_08	RE	-
04_evil_A_09	RE	-
04_evil_A_10	RE	-
05_evil_B_01	RE	-
05_evil_B_02	RE	-
05_evil_B_03	RE	-
05_evil_B_04	RE	-
05_evil_B_05	RE	-
05_evil_B_06	RE	-
05_evil_B_07	RE	-
05_evil_B_08	RE	-
05_evil_B_09	RE	-
05_evil_B_10	RE	-
06_evil_C_01	RE	-
06_evil_C_02	RE	-
06_evil_C_03	RE	-
06_evil_C_04	RE	-
06_evil_C_05	RE	-
06_evil_C_06	RE	-
06_evil_C_07	RE	-
06_evil_C_08	RE	-
06_evil_C_09	RE	-
06_evil_C_10	RE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using ld = long double;
template<typename T> using max_heap = std::priority_queue<T>;
template<typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr int popcount(const ull v) { return v ? __builtin_popcountll(v) : 0; }
constexpr int log2p1(const ull v) { return v ? 64 - __builtin_clzll(v) : 0; }
constexpr int lsbp1(const ull v) { return __builtin_ffsll(v); }
constexpr int clog(const ull v) { return v ? log2p1(v - 1) : 0; }
constexpr ull ceil2(const ull v) { return 1ULL << clog(v); }
constexpr ull floor2(const ull v) { return v ? (1ULL << (log2p1(v) - 1)) : 0ULL; }
constexpr bool btest(const ull mask, const int ind) { return (mask >> ind) & 1ULL; }
template<typename T> void bset(T& mask, const int ind) { mask |= ((T)1 << ind); }
template<typename T> void breset(T& mask, const int ind) { mask &= ~((T)1 << ind); }
template<typename T> void bflip(T& mask, const int ind) { mask ^= ((T)1 << ind); }
template<typename T> void bset(T& mask, const int ind, const bool b) { (b ? bset(mask, ind) : breset(mask, ind)); }
template<typename T>
struct bfft
{
    bfft() = delete;
    static void fzt(std::vector<T>& a)
    {
        const int sz = a.size();
        for (int i = 1; i < sz; i <<= 1) {
            for (int j = 0; j < sz; j++) {
                if ((j & i) == 0) { a[j | i] += a[j]; }
            }
        }
    }
    static void fmt(std::vector<T>& a)
    {
        const int sz = a.size();
        for (int i = 1; i < sz; i <<= 1) {
            for (int j = 0; j < sz; j++) {
                if ((j & i) == 0) { a[j | i] -= a[j]; }
            }
        }
    }
    static void fwt(std::vector<T>& a, const bool rev)
    {
        const int sz = a.size();
        for (int i = 1; i < sz; i <<= 1) {
            for (int j = 0; j < sz; j++) {
                if ((j & i) == 0) {
                    const T x = a[j], y = a[j | i];
                    a[j] = (rev ? (x + y) / T(2) : x + y), a[j | i] = (rev ? (x - y) / T(2) : x - y);
                }
            }
        }
    }
    static std::vector<T> and_convolute(const std::vector<T>& a, const std::vector<T>& b)
    {
        const int sz = ceil2(std::max(a.size(), b.size()));
        std::vector<T> A(sz), B(sz);
        for (int i = 0; i < a.size(); i++) { A[i] = a[i]; }
        for (int i = 0; i < b.size(); i++) { B[i] = b[i]; }
        fzt(A), fzt(B);
        for (int i = 0; i < sz; i++) { A[i] *= B[i]; }
        return fmt(A), A;
    }
    static std::vector<T> or_convolute(const std::vector<T>& a, const std::vector<T>& b)
    {
        const int sz = ceil2(std::max(a.size(), b.size()));
        const int mask = (1 << sz) - 1;
        std::vector<T> A(sz), B(sz);
        for (int i = 0; i < a.size(); i++) { A[i] = a[mask ^ i]; }
        for (int i = 0; i < b.size(); i++) { B[i] = b[mask ^ i]; }
        auto C = and_convolute(A, B);
        for (int i = 0; i < sz - i; i++) { std::swap(C[i], C[mask ^ i]); }
        return C;
    }
    static std::vector<T> xor_convolute(const std::vector<T>& a, const std::vector<T>& b)
    {
        const int sz = ceil2(std::max(a.size(), b.size()));
        std::vector<T> A(sz), B(sz);
        for (int i = 0; i < a.size(); i++) { A[i] = a[i]; }
        for (int i = 0; i < b.size(); i++) { B[i] = b[i]; }
        fwt(A, false), fwt(B, false);
        for (int i = 0; i < sz; i++) { A[i] *= B[i]; }
        return fwt(A, true), A;
    }
};
template<const uint& mod>
class modint
{
public:
    modint() : m_val{0} {}
    modint(const ll v) : m_val{normll(v)} {}
    modint(const modint& m) = default;
    modint& operator =(const modint& m) { return m_val = m(), (*this); }
    modint& operator =(const ll v) { return m_val = normll(v), (*this); }
    modint operator+() const { return *this; }
    modint operator-() const { return modint{0} - (*this); }
    modint& operator+=(const modint& m) { return m_val = norm(m_val + m()), *this; }
    modint& operator-=(const modint& m) { return m_val = norm(m_val + mod - m()), *this; }
    modint& operator*=(const modint& m) { return m_val = normll((ll)m_val * (ll)m() % (ll)mod), *this; }
    modint& operator/=(const modint& m) { return *this *= m.inv(); }
    modint& operator+=(const ll val) { return *this += modint{val}; }
    modint& operator-=(const ll val) { return *this -= modint{val}; }
    modint& operator*=(const ll val) { return *this *= modint{val}; }
    modint& operator/=(const ll val) { return *this /= modint{val}; }
    modint operator+(const modint& m) const { return modint{*this} += m; }
    modint operator-(const modint& m) const { return modint{*this} -= m; }
    modint operator*(const modint& m) const { return modint{*this} *= m; }
    modint operator/(const modint& m) const { return modint{*this} /= m; }
    modint operator+(const ll v) const { return *this + modint{v}; }
    modint operator-(const ll v) const { return *this - modint{v}; }
    modint operator*(const ll v) const { return *this * modint{v}; }
    modint operator/(const ll v) const { return *this / modint{v}; }
    bool operator==(const modint& m) const { return m_val == m(); }
    bool operator!=(const modint& m) const { return not(*this == m); }
    friend modint operator+(const ll v, const modint& m) { return modint{v} + m; }
    friend modint operator-(const ll v, const modint& m) { return modint{v} - m; }
    friend modint operator*(const ll v, const modint& m) { return modint{v} * m; }
    friend modint operator/(const ll v, const modint& m) { return modint{v} / m; }
    friend std::istream& operator>>(std::istream& is, modint& m)
    {
        ll v;
        return is >> v, m = v, is;
    }
    friend std::ostream& operator<<(std::ostream& os, const modint& m) { return os << m(); }
    uint operator()() const { return m_val; }
    modint pow(ull n) const
    {
        modint ans = 1;
        for (modint x = *this; n > 0; n >>= 1, x *= x) {
            if (n & 1ULL) { ans *= x; }
        }
        return ans;
    }
    modint inv() const { return m_val <= 2000000 ? sinv(m_val) : pow(mod - 2); }
    static modint fact(const uint n)
    {
        static std::vector<modint> fs{1, 1};
        for (uint i = (uint)fs.size(); i <= n; i++) { fs.push_back(fs.back() * i); }
        return fs[n];
    }
    static modint ifact(const uint n)
    {
        static std::vector<modint> ifs{1, 1};
        for (uint i = (uint)ifs.size(); i <= n; i++) { ifs.push_back(ifs.back() * sinv(i)); }
        return ifs[n];
    }
    static modint perm(const int n, const int k) { return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k); }
    static modint comb(const int n, const int k) { return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k) * ifact(k); }
private:
    static constexpr uint norm(const uint x) { return x < mod ? x : x - mod; }
    static constexpr uint normll(const ll x) { return norm(uint(x % (ll)mod + (ll)mod)); }
    static modint sinv(const uint n)
    {
        static std::vector<modint> is{1, 1};
        for (uint i = (uint)is.size(); i <= n; i++) { is.push_back(-is[mod % i] * (mod / i)); }
        return is[n];
    }
    uint m_val;
};
template<typename T> bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }
template<typename T> bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }
template<typename T> constexpr T inf_v = std::numeric_limits<T>::max() / 4;
template<typename Real> constexpr Real pi_v = Real{3.141592653589793238462643383279502884};
template<typename T> constexpr T TEN(const int n) { return n == 0 ? T{1} : TEN<T>(n - 1) * T{10}; }
template<typename F> struct fix : F
{
    fix(F&& f) : F{std::forward<F>(f)} {}
    template<typename... Args> auto operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); }
};
template<typename T, int n, int i = 0>
auto nd_array(int const (&szs)[n], const T x = T{})
{
    if constexpr (i == n) {
        return x;
    } else {
        return std::vector(szs[i], nd_array<T, n, i + 1>(szs, x));
    }
}
template<typename T, std::size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template<typename T, typename A>
std::ostream& operator<<(std::ostream& os, const std::deque<T, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template<typename K, typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::map<K, T, C, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
    return (os << "]" << std::endl);
}
template<typename K, typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::multimap<K, T, C, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
    return (os << "]" << std::endl);
}
template<typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::multiset<T, C, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) { return (os << "<" << v.first << "," << v.second << ">"); }
template<typename T1, typename T2, typename T3>
std::ostream& operator<<(std::ostream& os, const std::priority_queue<T1, T2, T3>& v)
{
    auto q = v;
    os << "[";
    while (not q.empty()) { os << q.top() << ",", q.pop(); }
    return os << "]\n";
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::queue<T1>& v)
{
    auto q = v;
    os << "[";
    while (not q.empty()) { os << q.front() << ",", q.pop(); }
    return os << "]\n";
}
template<typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::set<T, C, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::stack<T1>& v)
{
    auto q = v;
    os << "[";
    while (not q.empty()) { os << q.top() << ",", q.pop(); }
    return os << "]\n";
}
template<typename TupType, size_t... I>
std::ostream& print(std::ostream& os, const TupType& _tup, std::index_sequence<I...>) { return os << "(", (..., (os << (I == 0 ? "" : ", ") << std::get<I>(_tup))), os << ")\n"; }
template<typename... T>
std::ostream& operator<<(std::ostream& os, const std::tuple<T...>& _tup) { return print(os, _tup, std::make_index_sequence<sizeof...(T)>()); }
template<typename K, typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_map<K, T, H, P, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
    return (os << "]" << std::endl);
}
template<typename K, typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_multimap<K, T, H, P, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
    return (os << "]" << std::endl);
}
template<typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_multiset<T, H, P, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template<typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_set<T, H, P, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
template<typename T, typename A>
std::ostream& operator<<(std::ostream& os, const std::vector<T, A>& v)
{
    os << "[";
    for (const auto& e : v) { os << e << ","; }
    return (os << "]" << std::endl);
}
class printer
{
public:
    printer(std::ostream& os_ = std::cout) : m_os{os_} { m_os << std::fixed << std::setprecision(15); }
    template<typename... Args> int ln(const Args&... args) { return dump(args...), m_os << '\n', 0; }
    template<typename... Args> int el(const Args&... args) { return dump(args...), m_os << std::endl, 0; }
private:
    template<typename T> void dump(const T& v) { m_os << v; }
    template<typename T> void dump(const std::vector<T>& vs)
    {
        for (int i = 0; i < (int)vs.size(); i++) { m_os << (i ? " " : ""), dump(vs[i]); }
    }
    template<typename T> void dump(const std::vector<std::vector<T>>& vss)
    {
        for (int i = 0; i < (int)vss.size(); i++) { m_os << (0 <= i or i + 1 < (int)vss.size() ? "\n" : ""), dump(vss[i]); }
    }
    template<typename T, typename... Args> int dump(const T& v, const Args&... args) { return dump(v), m_os << ' ', dump(args...), 0; }
    std::ostream& m_os;
};
printer out;
class scanner
{
public:
    scanner(std::istream& is_ = std::cin) : m_is{is_} { m_is.tie(nullptr), std::ios::sync_with_stdio(false); }
    template<typename T> T val()
    {
        T v;
        return m_is >> v, v;
    }
    template<typename T> T val(const T offset) { return val<T>() - offset; }
    template<typename T> std::vector<T> vec(const int n)
    {
        return make_v<T>(n, [this]() { return val<T>(); });
    }
    template<typename T> std::vector<T> vec(const int n, const T offset)
    {
        return make_v<T>(n, [this, offset]() { return val<T>(offset); });
    }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1)
    {
        return make_v<std::vector<T>>(n0, [this, n1]() { return vec<T>(n1); });
    }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1, const T offset)
    {
        return make_v<std::vector<T>>(n0, [this, n1, offset]() { return vec<T>(n1, offset); });
    }
    template<typename... Args> auto tup() { return std::tuple<std::decay_t<Args>...>{val<Args>()...}; }
    template<typename... Args> auto tup(const Args&... offsets) { return std::tuple<std::decay_t<Args>...>{val<Args>(offsets)...}; }
private:
    template<typename T, typename F>
    std::vector<T> make_v(const int n, F f)
    {
        std::vector<T> ans;
        for (int i = 0; i < n; i++) { ans.push_back(f()); }
        return ans;
    }
    std::istream& m_is;
};
scanner in;
template<typename T>
void HogeHogeSansuu(T x) { std::cerr << x; }
template<typename T, typename... Args>
void HogeHogeSansuu(T x, Args... args) { std::cerr << x << ",", HogeHogeSansuu(args...); }
int main()
{
    static constexpr uint mod = 998244353;
    using mint = modint<mod>;
    const auto [N, K, X, Y] = in.tup<int, int, int, int>();
    assert(2 <= N and N <= 40);
    assert(N % 2 == 0);
    assert(0 <= X and X <= Y and Y <= TEN<int>(9));
    {
        ull prod = 1;
        for (int i = 0; i < N; i++) { prod *= (ull)K; }
        assert(prod <= 2ULL * TEN<ull>(15));
    }
    const auto as = in.vec<int>(K);
    const int H = N / 2;
    constexpr int A = 1024;
    for (const int a : as) { assert(0 <= a and a < A); }
    if (N == 2) {
        std::vector<mint> total(A, 0);
        for (int i = 0; i < K; i++) { total[as[i]] += 1; }
        mint ans = 0;
        total = bfft<mint>::xor_convolute(total, total);
        for (int x = 1; x < A; x++) {
            if (X <= x and x <= Y) { ans += total[x]; }
        }
        assert(X > 0);
        return out.ln(ans);
    }
    auto total = nd_array<mint>({A}, 0);
    auto dp = nd_array<mint>({A, A}, 0);
    for (int i = 0; i < K; i++) {
        fix([&](auto self, int n, int x, int y) -> void {
            if (n == H) {
                total[x] += 1;
                dp[as[i]][x] += 1;
            } else {
                for (int k = 0; k < K; k++) {
                    if (as[k] == y) { continue; }
                    const int nx = x ^ as[k];
                    self(n + 1, nx, as[k]);
                }
            }
        })(1, as[i], as[i]);
    }
    total = bfft<mint>::xor_convolute(total, total);
    for (int a = 0; a < A; a++) {
        dp[a] = bfft<mint>::xor_convolute(dp[a], dp[a]);
        for (int x = 0; x < A; x++) { total[x] -= dp[a][x]; }
    }
    mint ans = 0;
    for (int x = 0; x < A; x++) {
        if (X <= x and x <= Y) { ans += total[x]; }
    }
    out.ln(ans);
    return 0;
}

yukicoder

結果

テストケース

ソースコード