一些打表的小技巧

· · 算法·理论

打表的本质就是最大地利用题面给出的信息，提前算出可能需要的结果并存储到程序中，在使用时从“计算”变成了“调用”，以达到加速算法的目的。最普通的打表方法，就是另开一个程序复制粘贴；在 C++14 前，可以用模板元编程的方法进行编译期计算，但是这种代码过于复杂；在 C++14 之后到现在，日益完善的 constexpr 更加适合用来打表。

模板元编程和constexpr的对比

以输出斐波那契数列前 20 项为例：

模板元编程的程序

template<int N>
struct Fib {
    enum { value = Fib<N - 1>::value + Fib<N - 2>::value };
};

template<>
struct Fib<0> {
    enum { value = 0 };
};

template<>
struct Fib<1> {
    enum { value = 1 };
};

template<int N>
struct FibArray {
    static int data[N];

    template<int I>
    struct Init {
        static void apply() {
            data[I] = Fib<I>::value;
            Init<I - 1>::apply();
        }
    };

    template<>
    struct Init<0> {
        static void apply() {
            data[0] = Fib<0>::value;
        }
    };

    static void init() {
        Init<N - 1>::apply();
    }
};

template<int N>
int FibArray<N>::data[N];

int main() {
    const int cnt = 20;
    FibArray<cnt>::init();

    for (int i = 0; i < cnt; ++i) {
        cout << FibArray<cnt>::data[i] << ' ';
    }

    return 0;
}

为了看懂这个程序，我们需要知道：模板类与模板函数，模板递归，模板特化，模板类的静态成员变量的声明与定义等。这里还没有涉及到模板偏特化和SFINAE（匹配失败不是错误）等进阶内容。此外，模板元编程里面的循环必须以递归的方式实现。综上，可以看出模板元编程确实是十分复杂的。

constexpr的程序

constexpr int fibonacci(int n) {
    return (n <= 1) ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

constexpr std::array<int, 20> generate_fibonacci_array() {
    std::array<int, 20> arr = {};
    for (int i = 0; i < 20; ++i) {
        arr[i] = fibonacci(i);
    }
    return arr;
}

int main() {
    constexpr auto fib = generate_fibonacci_array();

    for (auto num : fib) {
        cout << num << " ";
    }

    return 0;
}

可以看到，利用 constexpr 的写法和普通地写一个生成函数几乎没有区别，仅仅是冠上一个 constexpr 关键字，十分简洁。

constexpr的两个常用例子

示例 1、质数表

计算并存储小于 N 的全部质数，其中的 N 最大可以取 N = 15000。

constexpr size_t N = 2025;

constexpr bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

constexpr size_t count_primes_under_N() {
    size_t count = 0;
    for (int i = 2; i < N; ++i) {
        if (is_prime(i)) ++count;
    }
    return count;
}

constexpr auto get_primes_under_N() {
    std::array<int, count_primes_under_N()> primes{};
    size_t index = 0;
    for (int i = 2; i < N; ++i) {
        if (is_prime(i)) {
            primes[index++] = i;
        }
    }
    return primes;
}

constexpr auto primes = get_primes_under_N();

示例 2、部分和数列

计算并存储公差为 1 的等差数列的部分和数列，计算到 1e9 停止。

constexpr size_t getarrsize(){
    long long s=0;
    size_t i=1;
    while(s<1e9){
        s+=i;
        ++i;
    }
    return i;
}

constexpr auto getsums(){
    array<int,getarrsize()> arr;
    arr[0]=0;
    for(int i=1;i<arr.size();++i){
        arr[i]=arr[i-1]+i;
    }
    return arr;
}

constexpr auto arr=getsums();

这两个例子都说明了，std::array 的第二个模板参数也是可以通过编译期计算给出的。

应用例题：P1795。

编译期计算目前（2025.04.06）的缺点是可用的容器几乎只有 std::array，所有需要 std::hash 的容器全都不能被 constexpr 修饰，std::vector 之类的动态容器仅能实现简单功能（截至C++20）。

灵活使用编译期打表，可以将问题从“计算”转为“查找”，也能一定程度上降低被卡常的风险。