實在是難為了造車的車企，由此催生出的“全能选手”也是越來越多。

大家發現了么，現在純粹的車好像越來越少了。

前些年總流行混搭、串燒，如今說的好聽了一些叫跨界、融合，車型上有SUV跨界轎車，更有SUV跨界MpV；定位上更是注重全面，要運動也要舒適，想豪華也想家用，求動力強也求夠省油…實在是難為了造車的車企，由此催生出的“全能选手”也是越來越多…

本站聲明:網站內容來源於http://www.auto6s.com/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計公司推薦不同的風格，搶佔消費者視覺第一線

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※南投搬家公司費用需注意的眉眉角角，別等搬了再說!

※教你寫出一流的銷售文案?

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

背景

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

1. 運行時預處理，生成所需的表格，根據輸入直接找到對應項，稍加處理后輸出；

2. 一個程序生成表格，作為提交程序的一部分，後續與方法1相同，這樣就省去了運行時計算的步驟；

3. 以上兩種方法結合，編譯期計算表格，運行時直接查詢，即元編程（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等命令行參數來控制。

思考題

1. problem2::Accumulator從Count == 0到Count == Num都要實例化，但其實只需實例化到 \(O \left( \sqrt{n} \right)\) 就可以了，試改寫之。

2. 洛谷 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】

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\)。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計公司推薦不同的風格，搶佔消費者視覺第一線

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※南投搬家公司費用需注意的眉眉角角，別等搬了再說!

※教你寫出一流的銷售文案?