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 = https://www.cnblogs.com/jerry-fuyi/p/X + 1;
};

template
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 = https://www.cnblogs.com/jerry-fuyi/p/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 = https://www.cnblogs.com/jerry-fuyi/p/X;
};

template
struct AbsoluteHelper
{
    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 = https://www.cnblogs.com/jerry-fuyi/p/N * Factorial::value;
};

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

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

template<int N>
struct SquareSum
{
    static constexpr int value = https://www.cnblogs.com/jerry-fuyi/p/SquareSum::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 = https://www.cnblogs.com/jerry-fuyi/p/Cur * Cur + SquareSumR::value;
};

template
struct SquareSumR
{
    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 = https://www.cnblogs.com/jerry-fuyi/p/SubT::value;
};
// partial specialization for end of recursion criterion
template
struct Sqrt {
    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 = https://www.cnblogs.com/jerry-fuyi/p/Accumulator::value + Partition::value;
};

template
struct Accumulator
{
    static constexpr int value = 0;
};

template
struct Partition
{
    static constexpr int value = Accumulator::value;
};

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

template
struct Store
{
    static inline void store(int* dst)
    {
        Store::store(dst);
        dst[Num] = Partition::value;
    }
};

template
struct Store
{
    static inline void store(int* dst)
    {
        ;
    }
};

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

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

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

}

namespace problem2
{

template 0)>
struct Accumulator
{
    static constexpr int value = Accumulator::value + problem1::Partition::value;
};

template
struct Accumulator
{
    static constexpr int value = Accumulator::value;
};

template
struct Accumulator
{
    static constexpr int value = 0;
};

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

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

inline void store(int* dst)
{
    store(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 = https://www.cnblogs.com/jerry-fuyi/p/(N < mid * mid) ? Sqrt::value
                                              : Sqrt::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 = https://www.cnblogs.com/jerry-fuyi/p/Fibonacci::value + Fibonacci::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$，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/9928.html

標籤：C++

上一篇：L1-018 大笨鐘 (10分)

下一篇：L1-019 誰先倒 (15分)

測驗點	\(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\)