本文共 2229 字，大约阅读时间需要 7 分钟。

隔板法可以用来求将n分解为k个非负整数之和的解的数量，这在组合数学中被广泛应用。对于给定的n和k，我们需要计算组合数C(n + k -1, k -1)，这表示将n个物体分成k个部分的方式数。

为了高效计算这个组合数，我们可以利用模运算的性质和快速幂算法来处理大数。以下是详细的实现思路：

以下是代数运算的优化：

• 模逆计算：由于模数p是质数，根据费马小定理，a^(p-2) ≡ a^(-1) mod p。这使得计算模逆变得容易，可以通过快速幂来计算。
• 组合数计算：将组合数表示为连乘和逆乘的形式，使用预存的阶乘和逆阶乘来增进计算速度。

以下是实现代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const long long MOD = 1000000007;typedef long long LL;LL quick_pow(LL a, LL b, LL mod) { LL result = 1; a %= mod; while (b > 0) { if (b % 2 == 1) { result = (result * a) % mod; } a = (a * a) % mod; b /= 2; } return result;}void init_dp(LL dp[], int size) { dp[0] = 1; for (int i = 1; i < size; ++i) { dp[i] = (dp[i-1] * i) % MOD; }}int main() { // 预计算阶乘和逆阶乘到 2*1e6 +5 const int MAX = 2 * 10^6 + 5; LL dp[MAX + 1]; init_dp(dp, MAX + 1); // 读取输入并处理每个测试用例 int T; scanf("%d", &T); for (int i = 1; i <= T; ++i) { int n, k; scanf("%d %d", &n, &k); // 计算C(n +k -1, k-1) mod MOD // 由于组合数的计算公式为 C(a, b) = f(a) / (f(b) * f(a-b)) mod MOD // 我们可以用预计算的dp数组 // 其中，f(a) = dp[a] // f(b) = dp[b] // f(a-b) = dp[a-b] // 这里b = k-1，a = n +k -1 LL a = n + k - 1; LL b = k - 1; LL c = a - b; LL numerator = dp[a]; LL denominator = (dp[b] * dp[c]) % MOD; LL inv_denominator = quick_pow(denominator, MOD-2, MOD); LL result = (numerator * inv_denominator) % MOD; printf("Case %d: %lld\n", i, result); } return 0;}
        
       
      
     
    
   

代码注释：

优化点：

• 预计算：预计算阶乘和逆阶乘值，减少了每次查询的时间复杂度。
• 快速幂算法：高效地计算了大数的模逆，避免了暴力枚举，提高了计算速度。
• 组合数分解：利用组合数公式，将大数问题转化为阶乘和逆阶乘的计算，使得问题更加可控。

注意事项：

• 确保预计算的阶乘数组大小足够大，能够处理最大的n和k。⟨提示：当n和k都达到1e6时，最大的组合数n +k -1会是2*1e6，因此预计算到2e6 +5是正确的。⟩

• 乘法和模运算要仔细处理，避免溢出或计算错误。

扩展性：

• 如果n和k的范围更大，比如达到1e9，预计算的阶乘方法就不适用，可以考虑使用公式递推或伪分治的方法。但在这个问题中，给定范围是1e6，因此预计算方法已经足够。

测试样例：

按照问题中的示例，输入：

4

输出结果应为：

15

可以验证代码是否得到这些预期结果。

转载地址：http://jzwfk.baihongyu.com/