计算多项式系数 [英] Calculate multinomial coefficient

问题描述

我想计算多项式系数mod 1e9 + 7。它等于：n！ /（k0！* k1！* k2 * ... * km！）

在我的情况下，m = 3，k0 + k1 + k2 = n， be：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
它不工作大测试

解决方案

我希望我不是linkfarming在这里，但这里是一个工作，解决你的问题： / p>

1. Naive实现总会遇到溢出错误。你必须准备好利用多项式系数的某些数学属性来达到一个鲁棒的解。 Dave Barber 在他的图书馆中执行此操作，其中使用递归属性（4个数字的示例 - 当所有分支被零替换时递归停止）

     multi a，b，c，d）= multi（a-1，b，c，d）基于上述， 
      David SerranoMartínez显示了实施的方式提供溢出控制可以被除掉。他的代码可以很容易地用作
     unsigned long long result_2 = multinomial :: multi< unsigned long long& 8，4}）; 
     
    




2. 第三种方法是使用（或学习）专用于组合，例如 SUBSET 。这是一个更困难的代码读取，由于依赖和长度，但调用是很容易

     int factors [4 ] = {1，2，3，4}; 
    Maths :: Combinatorics :: Arithmetic :: multinomial（4，factors）
     




I want to calculate multinomial coefficient mod 1e9 + 7. It equals: n! / (k0! * k1! * k2 * ... * km!)

In my case m = 3, k0 + k1 + k2 = n, so it would be: n! / (k0! * k1! * k2!) My code for this:

....
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] - factorial of i mod 1e9+7 It does not work on big tests

解决方案

I hope I'm not linkfarming here, but here is a process of work, to solve your problem :

1. Naive implementations will always suffer from overflow errors. You have to be ready to exploit certain mathematical properties of the polynomial coefficient to reach a robust solution. Dave Barber does that in his library, where the recursive property is used (example for 4 numbers - the recursion stops when all branches are replaced by zero)

   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. Based on the above, David Serrano Martínez shows how an implementation that provides overflow control can be divised. His code can be used as easily as

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

3. A third alternative would be to use (or learn from) libraries that are dedicated to combinatorics, like SUBSET. This is a bit more difficult code to read through due to dependencies and length, but invokation is as easy as

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

这篇关于计算多项式系数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！