verify/unit_test/convolution/or_convolution.test.cpp

• View this file on GitHub
• Last update: 2025-04-27 00:17:33+09:00
• Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

• or_convolution (src/convolution/or_convolution.hpp)
• zeta_transform (src/math/zeta_transform.hpp)
• PermutedCongruentialGenerator (src/random/permuted_congruential_generator.hpp)
• template (src/template/template.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/random/permuted_congruential_generator.hpp"
#include "../../../src/convolution/or_convolution.hpp"
void test() {
    int n = 1 << rng(0, 12);
    vector<ll> a(n), b(n);
    rep(i, 0, n) a[i] = rng(-1000000, 1000000);
    rep(i, 0, n) b[i] = rng(-1000000, 1000000);
    vector<ll> c = or_convolution(a, b);
    if(!n) {
        assert(c.empty());
        return;
    }
    vector<ll> expected(n);
    rep(i, 0, n) {
        rep(j, 0, n) {
            expected[i | j] += a[i] * b[j];
        }
    }
    rep(i, 0, n) {
        assert(c[i] == expected[i]);
    }
}
int main(void) {
    constexpr int test_num = 100;
    rep(_, 0, test_num) {
        test();
    }
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}

#line 1 "verify/unit_test/convolution/or_convolution.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/random/permuted_congruential_generator.hpp"
struct PermutedCongruentialGenerator {
    template <typename T>
        requires(is_integral_v<T> and sizeof(T) == 4) or (is_floating_point_v<T> and sizeof(T) == 8)
    inline T operator()(const T l, const T r) {
        assert(l <= r);
        if constexpr(is_integral_v<T>) {
            const unsigned int range = static_cast<unsigned int>(r - l + 1);
            return l + (next32() % range);
        } else {
            static constexpr unsigned long long denom = 1ull << 53;
            const unsigned long long x = next64() >> 11;
            const double u = static_cast<double>(x) / denom;
            return l + (r - l) * u;
        }
    }

   private:
    static constexpr unsigned long long MULT = 6364136223846793005;
    static inline unsigned long long state = chrono::steady_clock::now().time_since_epoch().count();
    inline unsigned int next32() {
        unsigned long long x = state;
        state *= MULT;
        const unsigned int count = x >> 61;
        x ^= x >> 22;
        return static_cast<unsigned int>(x >> (22 + count));
    }
    inline unsigned long long next64() {
        return (static_cast<unsigned long long>(next32()) << 32) | next32();
    }
} rng;
#line 3 "src/math/zeta_transform.hpp"
template <typename T>
void superset_zeta_transform(vector<T>& f, const bool inv = false) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0);
    const int sign = inv ? -1 : 1;
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                f[j] += sign * f[j | i];
            }
        }
    }
}
template <typename T>
void subset_zeta_transform(vector<T>& f, const bool inv = false) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0);
    const int sign = inv ? -1 : 1;
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                f[j | i] += sign * f[j];
            }
        }
    }
}
#line 4 "src/convolution/or_convolution.hpp"
template <typename T>
vector<T> or_convolution(vector<T> a, vector<T> b) {
    const int n = (int)a.size(), m = (int)b.size();
    assert(n == m and (n & (n - 1)) == 0);
    subset_zeta_transform(a);
    subset_zeta_transform(b);
    for(int i = 0; i < (int)a.size(); ++i) a[i] *= b[i];
    subset_zeta_transform(a, true);
    return a;
}
#line 5 "verify/unit_test/convolution/or_convolution.test.cpp"
void test() {
    int n = 1 << rng(0, 12);
    vector<ll> a(n), b(n);
    rep(i, 0, n) a[i] = rng(-1000000, 1000000);
    rep(i, 0, n) b[i] = rng(-1000000, 1000000);
    vector<ll> c = or_convolution(a, b);
    if(!n) {
        assert(c.empty());
        return;
    }
    vector<ll> expected(n);
    rep(i, 0, n) {
        rep(j, 0, n) {
            expected[i | j] += a[i] * b[j];
        }
    }
    rep(i, 0, n) {
        assert(c[i] == expected[i]);
    }
}
int main(void) {
    constexpr int test_num = 100;
    rep(_, 0, test_num) {
        test();
    }
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}

Back to top page