——永遠不要在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 組合數問題，用元編程實現。
題目描述
組合數 \(\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\)。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※網頁設計公司推薦不同的風格，搶佔消費者視覺第一線
※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益
※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面
※南投搬家公司費用需注意的眉眉角角，別等搬了再說!
※教你寫出一流的銷售文案?
