C++值元編程

C++值元編程

——永遠不要在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));
}

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

然而,多數函數不止有一句return語句,constexpr對函數體的限制使它很難用於中等複雜的計算任務,為此C++14放寬了限制,允許定義局部變量,允許if-elseswitch-casewhilefor等控制流。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::arrayoperator[]從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類型模板參數作匹配規則,特化falsetrue的情形,另一種情形留給主模板。

比如,計算 \(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:constevalis_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::PartitionCount參數就不會超過10,不信的話你可以加一句static_assert。實例化的模板數量一共只有2000多個,而在完整的問題中這個數量要翻100倍不止。這種性質稱為惰性求值,即用到了才求值。惰性求值是必需的,總不能窮盡模板參數的所有可能組合一一實例化出來吧?

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

性能

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

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

因為編譯器是32位的,4GB內存用完了就爆了。

停機問題

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

思考題

  1. problem2::AccumulatorCount == 0Count == 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\)

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

【其他文章推薦】

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

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

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

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

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