c++ - 计算多项式系数

Question

我想计算多项式系数 mod 1e9 + 7。它等于:n!/(k0!* k1!* k2 * ... * km!)

在我的例子中，m = 3，k0 + k1 + k2 = n，所以它是:n!/(k0! * k1! * k2!) 我的代码:

....
long long k2 = n - k1 - k0;
long long dans = fact[n] % MOD;
long long tmp = fact[i] % MOD;
tmp = (tmp * fact[j]) % MOD;
tmp = (tpm * fact[k]) % MOD;
res = (fact[n] / tmp) % MOD; // mb mistake is here...
cout << res;

fact[i] - i mod 1e9+7 的阶乘它不适用于大型测试

Answer 1

我希望我不是在这里做 linkfarming，但这是一个工作过程，可以解决您的问题:

1. 朴素的实现总是会出现溢出错误。您必须准备好利用多项式系数的某些数学特性来获得稳健的解决方案。 Dave Barber 在他的 library 中做到了这一点，其中使用了递归属性(例如 4 个数字 - 当所有分支都被零替换时递归停止)

   multi (a, b, c, d) = multi (a − 1, b, c, d) + multi (a, b − 1, c, d) + multi (a, b, c − 1, d) + multi (a, b, c, d − 1)
   

2. 基于以上内容，David Serrano Martínez 展示了 implementation提供溢出控制的可以被分割。他的代码可以像

   一样容易使用

   unsigned long long result_2 = multinomial::multi<unsigned long long>({9, 8, 4});
   

3. 第三种选择是使用(或学习)专用于组合学的库，例如 SUBSET .由于依赖关系和长度，这段代码有点难以阅读，但调用非常简单

   int factors[4] = {1, 2, 3, 4};
   Maths::Combinatorics::Arithmetic::multinomial(4, factors)