C++值元編程

2020 年 6 月 15 日
筆記
C++, 數據結構與演算法

——永遠不要在OJ上使用值元編程，過於簡單的沒有優勢，能有優勢的編譯錯誤。

背景

2019年10月，我在學習演算法。有一道作業題，輸入規模很小，可以用打表法解決。具體方案有以下三種：

運行時預處理，生成所需的表格，根據輸入直接找到對應項，稍加處理後輸出；
一個程式生成表格，作為提交程式的一部分，後續與方法1相同，這樣就省去了運行時計算的步驟；
以上兩種方法結合，編譯期計算表格，運行時直接查詢，即元編程（metaprogramming）。

做題當然是用方法1或2，但是元編程已經埋下了種子。時隔大半年，我來補上這個坑。

題目

北京大學OpenJudge 百練4119 複雜的整數劃分問題

描述

將正整數 $n$ 表示成一系列正整數之和，$n = n_1 + n_2 + … + n_k$，其中 $n_1 \geq n_2 \geq … \geq n_k \geq 1$，$k \geq 1$。正整數 $n$ 的這種表示稱為正整數 $n$ 的劃分。

輸入

標準的輸入包含若干組測試數據。每組測試數據是一行輸入數據，包括兩個整數 $N$ 和 $K$。（ $0 \le N \leq 50$，$0 \le K \leq N$ ）

輸出

對於每組測試數據，輸出以下三行數據:

第一行: $N$ 劃分成 $K$ 個正整數之和的劃分數目

第二行: $N$ 劃分成若干個不同正整數之和的劃分數目

第三行: $N$ 劃分成若干個奇正整數之和的劃分數目

樣例輸入

5 2

樣例輸出

2
3
3

提示

第一行: 4+1，3+2

第二行: 5，4+1，3+2

第三行: 5，1+1+3，1+1+1+1+1+1

解答

標準的動態規劃題。用dp[c][i][j]表示把i分成c個正整數之和的方法數，其中每個數都不超過j。

第一行。初始化：由$i \leq j$是否成立決定dp[1][i][j]的值，當$i \leq j$時為1，劃分為$i = i$，否則無法劃分，值為0。

遞推：為了求dp[c][i][j]，對$i = i_1 + i_2 + … + i_c$，$i_1 \geq i_2 \geq … \geq i_c$中的最大數$i_1$分類討論，最小為$1$，最大不超過$i – 1$，因為$c \geq 2$，同時不超過$j$，因為定義。最大數為$n$時，對於把$i – n$分成$c – 1$個數，每個數不超過$n$的劃分，追加上$n$可得$i$的一個劃分。$n$只有這些取值，沒有漏；對於不同的$n$，由於最大數不一樣，兩個劃分也不一樣，沒有多。故遞推式為：

\[dp[c][i][j] = \sum_{n=1}^{min\{i-1,j\}}dp[c-1][i-n][n]
\]

dp[K][N][N]即為所求ans1[K][N]。

第二行。可以把遞推式中的dp[c - 1][i - n][n]修改為dp[c - 1][i - n][n - 1]後重新計算。由於只需一個與c無關的結果，可以省去c這一維度，相應地改變遞推順序，每輪累加。

另一種方法是利用已經計算好的ans1數組。設$i = i_1 + i_2 + … + + i_{c-1} + i_c$，其中$i_1 \ge i_2 \ge … \ge i_{c+1} \ge i_c \ge 0$，則$i_1 – \left( c-1 \right) \geq i_2 – \left( c-2 \right) \geq … \geq i_{c-1} – 1 \geq i_c \ge 0$，且$\left( i_1 – \left( c-1 \right) \right) + \left( i_2 – \left( c-2 \right) \right) + … + \left( i_{c-1} – 1 \right) + \left( i_c \right) = i – \frac {c \left( c-1 \right)} {2}$，故把i劃分成c個不同正整數之和的劃分數目等於ans[c][i - c * (c - 1) / 2]，遍歷c累加即得結果。

第三行。想法與第二行相似，也是找一個對應，此處從略。另外，數學上可以證明，第二行和第三行的結果一定是一樣的。

#include <iostream>
#include <algorithm>

constexpr int max = 50;
int dp[max + 1][max + 1][max + 1] = { 0 };
int ans1[max + 1][max + 1] = { 0 };
int ans2[max + 1] = { 0 };
int ans3[max + 1] = { 0 };

int main()
{
    int num, k;
    for (int i = 1; i <= max; ++i)
        for (int j = 1; j <= max; ++j)
            dp[1][i][j] = i <= j;
    for (int cnt = 2; cnt <= max; ++cnt)
        for (int i = 1; i <= max; ++i)
            for (int j = 1; j <= max; ++j)
            {
                auto min = std::min(i - 1, j);
                for (int n = 1; n <= min; ++n)
                    dp[cnt][i][j] += dp[cnt - 1][i - n][n];
            }
    for (int cnt = 1; cnt <= max; ++cnt)
        for (int i = 1; i <= max; ++i)
            ans1[cnt][i] = dp[cnt][i][i];
    for (int i = 1; i <= max; ++i)
        for (int cnt = 1; cnt <= i; ++cnt)
        {
            int j = i - cnt * (cnt - 1) / 2;
            if (j <= 0)
                break;
            ans2[i] += ans1[cnt][j];
        }
    for (int i = 1; i <= max; ++i)
        for (int cnt = 1; cnt <= i; ++cnt)
        {
            int j = i + cnt;
            if (j % 2)
                continue;
            j /= 2;
            ans3[i] += ans1[cnt][j];
        }
    
    while (std::cin >> num)
    {
        std::cin >> k;
        std::cout << ans1[k][num] << std::endl;
        std::cout << ans2[num] << std::endl;
        std::cout << ans3[num] << std::endl;
    }
}

值元編程基礎

元編程是指電腦程式能把其他程式作為它們的數據的編程技術。在目前的C++中，元編程體現為用程式碼生成程式碼，包括宏與模板。當我們使用了std::vector<int>中的任何一個名字時，std::vector類模板就用模板參數int, std::allocator<int>實例化為std::vector<int, std::allocator<int>>模板類，這是一種元編程，不過我們通常不這麼講。

狹義的C++模板元編程（template metaprogramming，TMP）包括值元編程、類型元編程，以及兩者的相交。本文討論的是值元編程，即為編譯期值編程。

在C++中有兩套工具可用於值元編程：模板和constexpr。C++模板是圖靈完全的，這是模板被引入C++以後才被發現的，並不是C++模板的初衷，因此用模板做計算在C++中算不上一等用法，導致其語法比較冗長複雜。constexpr的初衷是提供純正的編譯期常量，後來才取消對計算的限制，但不能保證計算一定在編譯期完成。總之，這兩套工具都不完美，所以本文都會涉及。

嚴格來說，constexpr不符合上述對元編程的定義，但它確實可以提供運行時程式需要的數據，所以也歸入元編程的類別。

constexpr式值元編程

從constexpr開始講，是因為它與我們在C++中慣用的編程範式——過程式範式是一致的。

constexpr關鍵字在C++11中被引入。當時，constexpr函數中只能包含一條求值語句，就是return語句，返回值可以用於初始化constexpr變數，作模板參數等用途。如果需要分支語句，用三目運算符?:；如果需要循環語句，用函數遞歸實現。比如，計算階乘：

constexpr int factorial(int n)
{
    return n <= 1 ? 1 : (n * factorial(n - 1));
}

對於編譯期常量i，factorial(i)產生編譯期常量；對於運行時值j，factorial(j)產生運行時值，也就是說，constexpr可以視為對既有函數的附加修飾。

然而，多數函數不止有一句return語句，constexpr對函數體的限制使它很難用於中等複雜的計算任務，為此C++14放寬了限制，允許定義局部變數，允許if-else、switch-case、while、for等控制流。factorial函數可以改寫為：

constexpr int factorial(int n)
{
    int result = 1;
    for (; n > 1; --n)
        result *= n;
    return result;
}

也許你會覺得factorial函數的遞歸版本比循環版本易懂，那是因為你學習遞歸時接觸的第一個例子就是它。對於C++開發者來說，大多數情況下首選的還是循環。

計算單個constexpr值用C++14就足夠了，但是傳遞數組需要C++17，因為std::array的operator[]從C++17開始才是constexpr的。

整數劃分問題的constexpr元編程實現需要C++17標準：

#include <iostream>
#include <utility>
#include <array>

constexpr int MAX = 50;

constexpr auto calculate_ans1()
{
    std::array<std::array<std::array<int, MAX + 1>, MAX + 1>, MAX + 1> dp{};
    std::array<std::array<int, MAX + 1>, MAX + 1> ans1{};
    constexpr int max = MAX;
    for (int i = 1; i <= max; ++i)
        for (int j = 1; j <= max; ++j)
            dp[1][i][j] = i <= j;
    for (int cnt = 2; cnt <= max; ++cnt)
        for (int i = 1; i <= max; ++i)
            for (int j = 1; j <= max; ++j)
            {
                auto min = std::min(i - 1, j);
                for (int n = 1; n <= min; ++n)
                    dp[cnt][i][j] += dp[cnt - 1][i - n][n];
            }
    for (int cnt = 1; cnt <= max; ++cnt)
        for (int i = 1; i <= max; ++i)
            ans1[cnt][i] = dp[cnt][i][i];
    return ans1;
}

constexpr auto calculate_ans2()
{
    constexpr auto ans1 = calculate_ans1();
    std::array<int, MAX + 1> ans2{};
    constexpr int max = MAX;
    for (int i = 1; i <= max; ++i)
        for (int cnt = 1; cnt <= i; ++cnt)
        {
            int j = i - cnt * (cnt - 1) / 2;
            if (j <= 0)
                break;
            ans2[i] += ans1[cnt][j];
        }
    return ans2;
}

int main()
{
    constexpr auto ans1 = calculate_ans1();
    constexpr auto ans2 = calculate_ans2();

    for (int cnt = 1; cnt <= 10; ++cnt)
    {
        for (int i = 1; i <= 10; ++i)
            std::cout << ans1[cnt][i] << ' ';+
        std::cout << std::endl;
    }
    std::cout << std::endl;
    for (int i = 1; i <= 50; ++i)
        std::cout << ans2[i] << ' ';
    std::cout << std::endl;

    int num, k;
    while (std::cin >> num)
    {
        std::cin >> k;
        std::cout << ans1[k][num] << std::endl;
        std::cout << ans2[num] << std::endl;
        std::cout << ans2[num] << std::endl;
    }
}

模板式值元編程

模板式與C++11中的constexpr式類似，必須把循環化為遞歸。事實上C++模板是一門函數式程式語言，對值元編程和類型元編程都是如此。

程式控制流有三種基本結構：順序、分支與循環。

順序

在函數式編程中，數據都是不可變的，函數總是接受若干參數，返回若干結果，參數和結果是不同的變數；修改原來的變數是不允許的。對於C++模板這門語言，函數是類模板，也稱「元函數」（metafunction）；參數是模板參數；運算結果是模板類中定義的靜態編譯期常量（在C++11以前，常用enum來定義；C++11開始用constexpr）。

比如，對於參數 $x$，計算 $x + 1$ 和 $x ^ 2$ 的元函數：

template<int X>
struct PlusOne
{
    static constexpr int value = X + 1;
};

template<int X>
struct Square
{
    static constexpr int value = X * X;
};

這裡假定運算數的類型為int。從C++17開始，可以用auto聲明非類型模板參數。

順序結構，是對數據依次進行多個操作，可以用函數嵌套來實現：

std::cout << PlusOne<1>::value << std::endl;
std::cout << Square<2>::value << std::endl;
std::cout << Square<PlusOne<3>::value>::value << std::endl;
std::cout << PlusOne<Square<4>::value>::value << std::endl;

或者藉助constexpr函數，回歸熟悉的過程式範式：

template<int X>
struct SquareAndIncrease
{
    static constexpr int calculate()
    {
        int x = X;
        x = x * x;
        x = x + 1;
        return x;
    }
    static constexpr int value = calculate();
};

void f()
{
    std::cout << SquareAndIncrease<5>::value << std::endl;
}

過程式方法同樣可以用於分支和循環結構，以下省略；函數式方法可以相似地用於值元編程與類型元編程，所以我更青睞（主要還是逼格更高）。

分支

C++模板元編程實現分支的方式是模板特化與模板參數匹配，用一個額外的帶默認值的bool類型模板參數作匹配規則，特化false或true的情形，另一種情形留給主模板。

比如，計算 $x$ 的絕對值：

template<int X, bool Pos = (X > 0)>
struct AbsoluteHelper
{
    static constexpr int value = X;
};

template<int X>
struct AbsoluteHelper<X, false>
{
    static constexpr int value = -X;
};

如果你怕用戶瞎寫模板參數，可以再包裝一層：

template<int X>
struct Absolute : AbsoluteHelper<X> { };

void g()
{
    std::cout << Absolute<6>::value << std::endl;
    std::cout << Absolute<-7>::value << std::endl;
}

標準庫提供了std::conditional及其輔助類型std::conditional_t用於模板分支：

template<bool B, class T, class F>
struct conditional;

定義了成員類型type，當B == true時為T，否則為F。

模板匹配實際上是在處理switch-case的分支，bool只是其中一種簡單情況。對於對應關係不太規則的分支語句，可以用一個constexpr函數把參數映射到一個整數或枚舉上：

enum class Port_t
{
    PortB, PortC, PortD, PortError,
};

constexpr Port_t portMap(int pin)
{
    Port_t result = Port_t::PortError;
    if (pin < 0)
        ;
    else if (pin < 8)
        result = Port_t::PortD;
    else if (pin < 14)
        result = Port_t::PortB;
    else if (pin < 20)
        result = Port_t::PortC;
    return result;
}

template<int Pin, Port_t Port = portMap(Pin)>
struct PinOperation;

template<int Pin>
struct PinOperation<Pin, Port_t::PortB> { /* ... */ };

template<int Pin>
struct PinOperation<Pin, Port_t::PortC> { /* ... */ };

template<int Pin>
struct PinOperation<Pin, Port_t::PortD> { /* ... */ };

如果同一個模板有兩個參數分別處理兩種分支（這已經從分支上升到模式匹配了），或同時處理分支和循環的特化，總之有兩個或以上維度的特化，需要注意兩個維度的特化是否會同時滿足，如果有這樣的情形但沒有提供兩參數都特化的模板特化，編譯會出錯。見problem2::Accumulator，它不需要提供兩個參數同時特化的版本。

循環

如前所述，循環要化為遞歸，循環的開始與結束是遞歸的起始與終點或兩者對調，遞歸終點的模板需要特化。比如，還是計算階乘：

template<int N>
struct Factorial
{
    static constexpr int value = N * Factorial<N - 1>::value;
};

template<>
struct Factorial<0>
{
    static constexpr int value = 1;
};

或許階乘的遞歸定義很大程度上來源於數學，那就再看一個平方和的例子：

template<int N>
struct SquareSum
{
    static constexpr int value = SquareSum<N - 1>::value + N * N;
};

template<>
struct SquareSum<0>
{
    static constexpr int value = 0;
};

（$1^2 + 2^2 + \cdots + n^2 = \frac {n \left( n + 1 \right) \left( 2n + 1\right)} {6}$）

好吧，還是挺數學的，去下面看實例感覺一下吧，那裡還有break——哦不，被我放到思考題中去了。

加群是交換群，求和順序不影響結果，上面這樣的順序寫起來方便。有些運算符不滿足交換律，需要逆轉順序。還以平方和為例：

template<int N, int Cur = 0>
struct SquareSumR
{
    static constexpr int value = Cur * Cur + SquareSumR<N, Cur + 1>::value;
};

template<int N>
struct SquareSumR<N, N>
{
    static constexpr int value = N * N;
};

遞歸

遞歸在過程式中是一種高級的結構，它可以直接轉化為函數式的遞歸，後面會提到兩者的異同。

比如，計算平方根，這個例子來源於C++ Templates: The Complete Guide 2e：

// primary template for main recursive step
template<int N, int LO = 1, int HI = N>
struct Sqrt {
    // compute the midpoint, rounded up
    static constexpr auto mid = (LO + HI + 1) / 2;
    // search a not too large value in a halved interval
    using SubT = std::conditional_t<(N < mid * mid),
                                   Sqrt<N, LO, mid - 1>,
                                   Sqrt<N, mid, HI>>;
    static constexpr auto value = SubT::value;
};
// partial specialization for end of recursion criterion
template<int N, int S>
struct Sqrt<N, S, S> {
    static constexpr auto value = S;
};

這個遞歸很容易化為循環，有助於你對循環化遞歸的理解。

存儲

實際應用中我們可能不需要把所有計算出來的值存儲起來，但在打表的題目中需要。存儲一系列數據需要用循環，循環的實現方式依然是遞歸。比如，存儲階乘（Factorial類模板見上）：

template<int N>
inline void storeFactorial(int* dst)
{
    storeFactorial<N - 1>(dst);
    dst[N] = Factorial<N>::value;
}

template<>
inline void storeFactorial<-1>(int* dst)
{
    ;
}

void h()
{
    constexpr int MAX = 10;
    int factorial[MAX + 1];
    storeFactorial<MAX>(factorial);
    for (int i = 0; i <= MAX; ++i)
        std::cout << factorial[i] << ' ';
    std::cout << std::endl;
}

多維數組同理，例子見下方。注意，函數模板不能偏特化，但有靜態方法的類模板可以，這個靜態方法就充當原來的模板函數。

雖然我們是對數組中的元素挨個賦值的，但編譯器的生成程式碼不會這麼做，即使不能優化成所有數據一起用memcpy，至少能做到一段一段拷貝。

類內定義的函數隱式成為inline，手動寫上inline沒有語法上的意義，但是對於一些編譯器，寫上以後函數被內聯的可能性更高，所以寫inline是一個好習慣。

解答

#include <iostream>
#include <algorithm>

constexpr int MAX = 50;

namespace problem1
{

template<int Count, int Num, int Max>
struct Partition;

template<int Count, int Num, int Loop>
struct Accumulator
{
    static constexpr int value = Accumulator<Count, Num, Loop - 1>::value + Partition<Count, Num - Loop, Loop>::value;
};

template<int Count, int Num>
struct Accumulator<Count, Num, 0>
{
    static constexpr int value = 0;
};

template<int Count, int Num, int Max = Num>
struct Partition
{
    static constexpr int value = Accumulator<Count - 1, Num, std::min(Num - 1, Max)>::value;
};

template<int Num, int Max>
struct Partition<1, Num, Max>
{
    static constexpr int value = Num <= Max;
};

template<int Count, int Num>
struct Store
{
    static inline void store(int* dst)
    {
        Store<Count, Num - 1>::store(dst);
        dst[Num] = Partition<Count, Num>::value;
    }
};

template<int Count>
struct Store<Count, 0>
{
    static inline void store(int* dst)
    {
        ;
    }
};

template<int Count>
inline void store(int (*dst)[MAX + 1])
{
    store<Count - 1>(dst);
    Store<Count, MAX>::store(dst[Count]);
}

template<>
inline void store<0>(int (*dst)[MAX + 1])
{
    ;
}

inline void store(int(*dst)[MAX + 1])
{
    store<MAX>(dst);
}

}

namespace problem2
{

template<int Num, int Count = Num, int Helper = Num - Count * (Count - 1) / 2, bool Valid = (Helper > 0)>
struct Accumulator
{
    static constexpr int value = Accumulator<Num, Count - 1>::value + problem1::Partition<Count, Helper>::value;
};

template<int Num, int Count, int Helper>
struct Accumulator<Num, Count, Helper, false>
{
    static constexpr int value = Accumulator<Num, Count - 1>::value;
};

template<int Num, int Helper, bool Valid>
struct Accumulator<Num, 0, Helper, Valid>
{
    static constexpr int value = 0;
};

template<int Num>
inline void store(int* dst)
{
    store<Num - 1>(dst);
    dst[Num] = Accumulator<Num>::value;
}

template<>
inline void store<0>(int* dst)
{
    ;
}

inline void store(int* dst)
{
    store<MAX>(dst);
}

}

int ans1[MAX + 1][MAX + 1];
int ans2[MAX + 1];

int main()
{
    problem1::store(ans1);
    problem2::store(ans2);
    int num, k;
    while (std::cin >> num)
    {
        std::cin >> k;
        std::cout << ans1[k][num] << std::endl;
        std::cout << ans2[num] << std::endl;
        std::cout << ans2[num] << std::endl;
    }
}

請對照運行時版本自行理解。

討論

constexpr

constexpr不保證計算在編譯期完成，大部分編譯器在Debug模式下把所有可以推遲的constexpr計算都推遲到運行時完成。但constexpr可以作為一個強有力的優化提示，原本在最高優化等級都不會編譯期計算的程式碼，在有了constexpr後編譯器會儘力幫你計算。如果編譯器實在做不到，根據你是否強制編譯期求值，編譯器會給出錯誤或推遲到運行時計算。在不同的編譯器中，這類行為的表現是不同的——眾所周知MSVC對constexpr的支援不好。

目前（C++17）沒有任何方法可以檢查一個表達式是否是編譯期求值的，但是有方法可以讓編譯器對於非編譯期求值表達式給出一個錯誤，把期望constexpr的表達式放入模板參數或static_assert表達式都是可行的：如果編譯期求值，則編譯通過；否則編譯錯誤。

（C++20：consteval、is_constant_evaluated）

模板

如果我們把Sqrt中的遞歸替換為如下語句：

static constexpr auto value = (N < mid * mid) ? Sqrt<N, LO, mid - 1>::value
                                              : Sqrt<N, mid, HI>::value;

顯然計算結果是相同的，看上去還更簡潔。但是問題在於，編譯器會把Sqrt<N, LO, mid - 1>和Sqrt<N, mid, HI>兩個類都實例化出來，儘管只有一個模板類的value會被使用到。這些類模板實例繼續導致其他實例產生，最終將產生 $O \left( n \log n \right)$ 個實例。相比之下，把兩個類型名字傳給std::conditional並不會導致類模板被實例化，std::conditional只是定義一個類型別名，對該類型求::value才會實例化它，一共產生 $O \left( \log n \right)$ 個實例。

還有一個很常見的工具是變參模板，我沒有介紹是因為暫時沒有用到，而且我怕寫出非多項式複雜度的元程式。如果我還有機會寫一篇類型元編程的話，肯定會包含在其中的。

函數式

循環的一次迭代往往需要上一次迭代的結果，對應地在遞歸中就是函數對一個參數的結果依賴於對其他 $n$ 個參數的結果。有些問題用遞歸解決比較直觀，但是如果 $n \geq 2$，計算過程就會指數爆炸，比如：

int fibonacci(int n)
{
    if (n <= 2)
        return 1;
    else
        return fibonacci(n - 2) + fibonacci(n - 1);
}

計算fibonacci(30)已經需要一點點時間了，而計算fibonacci(46)（4位元組帶符號整型能容納的最大斐波那契數）就很慢了。把這種遞歸轉化為循環，就是設計一個動態規劃演算法的過程。然而函數式中的遞歸與過程式中的循環可能有相同的漸近時間複雜度：

template<int N>
struct Fibonacci
{
    static constexpr int value = Fibonacci<N - 2>::value + Fibonacci<N - 1>::value;
};

template<>
struct Fibonacci<1>
{
    static constexpr int value = 1;
};

template<>
struct Fibonacci<2>
{
    static constexpr int value = 1;
};

因為只有Fibonacci<1>到Fibonacci<46>這46個類模板被實例化，是 $O \left( n \right)$ 複雜度的。

在題目中，由於表中的所有數據都有可能用到，並且運行時不能執行計算，所以要把所有數據都計算出來。實際問題中可能只需要其中一個值，比如我現在就想知道不同整數的劃分問題對 $50$ 的答案是多少，就寫：

std::cout << problem2::Accumulator<50>::value << std::endl;

那麼problem1::Partition的Count參數就不會超過10，不信的話你可以加一句static_assert。實例化的模板數量一共只有2000多個，而在完整的問題中這個數量要翻100倍不止。這種性質稱為惰性求值，即用到了才求值。惰性求值是必需的，總不能窮盡模板參數的所有可能組合一一實例化出來吧？

函數式程式語言可以在運行時實現這些特性。

性能

我愧對這個小標題，因為C++值元編程根本沒有性能，時間和空間都是。類型元編程也許是必需，至於值元編程，emm，做點簡單的計算就可以了，這整篇文章都是反面教材。

思考題2用GCC編譯，大概需要10分鐘；用MSVC編譯，出現我聞所未聞的錯誤：

因為編譯器是32位的，4GB記憶體用完了就爆了。

停機問題

一個很有趣的問題是編譯器對於死循環的行為。根據圖靈停機問題，編譯器無法判斷它要編譯的元程式是否包含死循環，那麼它在遇到死循環時會怎樣表現呢？當然不能跟著元程式一起死循環，constexpr的循環次數與模板的嵌套深度都是有限制的。在GCC中，可以用-fconstexpr-depth、-fconstexpr-loop-limit和-ftemplate-depth等命令行參數來控制。

思考題

problem2::Accumulator從Count == 0到Count == Num都要實例化，但其實只需實例化到 $O \left( \sqrt{n} \right)$ 就可以了，試改寫之。
洛谷 NOIp2016提高組D2T1 組合數問題，用元編程實現。

只需完成 $n \leq 100, m \leq 100$ 的任務點；
使用64位編譯器（指編譯器本身而非目標程式碼），給編譯器億點點時間；
不要去網站上提交，我已經試過了，編譯錯誤。
測試數據下載。

題目描述

組合數 $\binom {n} {m}$ 表示的是從 $n$ 個物品中選出 $m$ 個物品的方法數。舉個例子，從 $\left( 1, 2, 3 \right)$ 三個物品中選擇兩個物品可以有 $\left( 1, 2 \right), \left( 1, 3 \right), \left( 2, 3 \right)$ 這三種選擇方法。根據組合數的定義，我們可以給出計算組合數 $\binom {n} {m}$ 的一般公式

\[\binom {n} {m} = \frac {n!} {m! \left( n-m \right) !} \,,
\]

其中 $n! = 1 \times 2 \times \cdots \times n$；特別地，定義 $0! = 1$。

小蔥想知道如果給定 $n$，$m$ 和 $k$，對於所有的 $0 \leq i \leq n, 0 \leq j \leq \min \left( i, m \right)$ 有多少對 $\left( i, j \right)$ 滿足 $k \mid \binom {i} {j}$。

輸入格式

第一行有個兩個整數 $t, k$，其中 $t$ 代表該測試點總共有多少組測試數據，$k$ 的意義見問題描述。

接下來 $t$ 行每行兩個整數 $n, m$，其中 $n, m$ 的意義見問題描述。

輸出格式

共 $t$ 行，每行一個整數代表所有的 $0 \leq i \leq n, 0 \leq j \leq \min \left( i, m \right)$ 有多少對 $\left( i, j \right)$ 滿足 $k \mid \binom {i} {j}$。

輸入輸出樣例

【輸入#1】

1 2
3 3

【輸出#1】

【輸入#2】

2 5
4 5
6 7

【輸出#2】

0 7

說明/提示

【樣例1說明】

在所有可能的情況中，只有 $\binom {2} {1} = 2$ 一種情況是 $2$ 的倍數。

【子任務】

測試點	$n$	$m$	$k$	$t$
1	$\leq 3$	$ \leq 3$	$= 2$	$ = 1$
2			$= 3$	$\leq 10^4$
3	$\leq 7$	$ \leq 7$	$= 4$	$ = 1$
4			$= 5$	$\leq 10^4$
5	$\leq 10$	$ \leq 10$	$= 6$	$ = 1$
6			$= 7$	$\leq 10^4$
7	$\leq 20$	$ \leq 100$	$= 8$	$ = 1$
8			$= 9$	$\leq 10^4$
9	$\leq 25$	$ \leq 2000$	$=10$	$ = 1$
10			$=11$	$\leq 10^4$
11	$\leq 60$	$ \leq 20$	$=12$	$ = 1$
12			$=13$	$\leq 10^4$
13	$\leq 100$	$ \leq 25$	$=14$	$ = 1$
14			$=15$	$\leq 10^4$
15		$ \leq 60$	$=16$	$ = 1$
16			$=17$	$\leq 10^4$
17	$\leq 2000$	$ \leq 100$	$=18$	$ = 1$
18			$=19$	$\leq 10^4$
19		$ \leq 2000$	$=20$	$ = 1$
20			$=21$	$\leq 10^4$

對於全部的測試點，保證 $0 \leq n, m \leq 2 \times 10^3, 1 \leq t \leq 10^4$。

Tags: C++ 數據結構與演算法

測試點	\(n\)	\(m\)	\(k\)	\(t\)
1	\(\leq 3\)	$ \leq 3$	\(= 2\)	$ = 1$
2			\(= 3\)	\(\leq 10^4\)
3	\(\leq 7\)	$ \leq 7$	\(= 4\)	$ = 1$
4			\(= 5\)	\(\leq 10^4\)
5	\(\leq 10\)	$ \leq 10$	\(= 6\)	$ = 1$
6			\(= 7\)	\(\leq 10^4\)
7	\(\leq 20\)	$ \leq 100$	\(= 8\)	$ = 1$
8			\(= 9\)	\(\leq 10^4\)
9	\(\leq 25\)	$ \leq 2000$	\(=10\)	$ = 1$
10			\(=11\)	\(\leq 10^4\)
11	\(\leq 60\)	$ \leq 20$	\(=12\)	$ = 1$
12			\(=13\)	\(\leq 10^4\)
13	\(\leq 100\)	$ \leq 25$	\(=14\)	$ = 1$
14			\(=15\)	\(\leq 10^4\)
15		$ \leq 60$	\(=16\)	$ = 1$
16			\(=17\)	\(\leq 10^4\)
17	\(\leq 2000\)	$ \leq 100$	\(=18\)	$ = 1$
18			\(=19\)	\(\leq 10^4\)
19		$ \leq 2000$	\(=20\)	$ = 1$
20			\(=21\)	\(\leq 10^4\)

C++值元編程

背景

題目

描述

輸入

輸出

樣例輸入

樣例輸出

提示

解答

值元編程基礎

constexpr式值元編程

模板式值元編程

順序

分支

循環

遞歸

存儲

解答

討論

constexpr

模板

函數式

性能

停機問題

思考題

題目描述

輸入格式

輸出格式

輸入輸出樣例

說明/提示

VirMach 便宜 VPS

QNews

C++值元編程

背景

題目

描述

輸入

輸出

樣例輸入

樣例輸出

提示

解答

值元編程基礎

constexpr式值元編程

模板式值元編程

順序

分支

循環

遞歸

存儲

解答

討論

constexpr

模板

函數式

性能

停機問題

思考題

題目描述

輸入格式

輸出格式

輸入輸出樣例

說明/提示

分享此文：

Related Posts

Spring Boot構建的Web項目如何在服務端校驗表單輸入

淺談分散式事務與TX-LCN

Spark文檔閱讀之一：Spark Overview

Python機器學習筆記：SVM（4）——sklearn實現

VirMach 便宜 VPS

QNews

熱門搜尋