enumerate/test/enumerate_product.test.cpp

• View this file on GitHub
• Last update: 2026-04-11 01:00:23+09:00
• Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

• $ 0 \leq p_{i} < a_{i} $ を満たす整数列 $p$ の列挙 (enumerate/enumerate_product.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include <iostream>

#include "../../enumerate/enumerate_product.hpp"

void test1_simple() {
    std::vector<int> a = {1, 2, 3};
    std::vector<std::vector<int>> ps;
    auto f = [&](std::vector<int> p) -> void {
        ps.push_back(p);
        return;
    };
    enumerate_product(a, f);
    std::vector<std::vector<int>> ps2 = {{0, 0, 0}, {0, 0, 1}, {0, 0, 2},
                                         {0, 1, 0}, {0, 1, 1}, {0, 1, 2}};
    assert(ps == ps2);
}

void test2_zero() {
    // 一度 0 以下の整数が出現した場合
    // それ以降の整数の値によらず p は列挙されない
    std::vector<int> a = {1, 0, 1000000000, 1000000000};
    std::vector<std::vector<int>> ps;
    auto f = [&](std::vector<int> p) -> void {
        ps.push_back(p);
        return;
    };
    enumerate_product(a, f);
    assert(ps.size() == 0);
}

int main() {
    test1_simple();
    test2_zero();
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}

#line 1 "enumerate/test/enumerate_product.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include <iostream>

#line 2 "enumerate/enumerate_product.hpp"

#include <cassert>
#include <vector>

// enumerate product
// enumerate p (0 <= p[i] < a[i])
template <class F> void enumerate_product(std::vector<int> a, F f) {
    const int n = (int)(a.size());
    std::vector<int> p;
    auto dfs = [&](auto g, int i) -> void {
        if (i == n) {
            f(p);
            return;
        }
        for (int x = 0; x < a[i]; x++) {
            p.push_back(x);
            g(g, i + 1);
            p.pop_back();
        }
    };
    dfs(dfs, 0);
    return;
}
#line 6 "enumerate/test/enumerate_product.test.cpp"

void test1_simple() {
    std::vector<int> a = {1, 2, 3};
    std::vector<std::vector<int>> ps;
    auto f = [&](std::vector<int> p) -> void {
        ps.push_back(p);
        return;
    };
    enumerate_product(a, f);
    std::vector<std::vector<int>> ps2 = {{0, 0, 0}, {0, 0, 1}, {0, 0, 2},
                                         {0, 1, 0}, {0, 1, 1}, {0, 1, 2}};
    assert(ps == ps2);
}

void test2_zero() {
    // 一度 0 以下の整数が出現した場合
    // それ以降の整数の値によらず p は列挙されない
    std::vector<int> a = {1, 0, 1000000000, 1000000000};
    std::vector<std::vector<int>> ps;
    auto f = [&](std::vector<int> p) -> void {
        ps.push_back(p);
        return;
    };
    enumerate_product(a, f);
    assert(ps.size() == 0);
}

int main() {
    test1_simple();
    test2_zero();
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}

Back to top page