问题标签 [binomial-coefficients]

I have 2 function, but for the same input a=5 und b=6 different values -.- why?

f1:

wolframalpha.com/input/?i=%28%285^3%2B6^3%29%285^3-6^3%29%29^3%2B3%28%285%286^2%29%2B%285^2%296%29%285%286^2%29-%286^2%296%29%29+%3D

f2:

wolframalpha.com/input/?i=%285^2-6^2%29^3

my haskell code:

f--> wolframalpha.com/input/?i=%28%28a^3%2Bb^3%29%28a^3-b^3%29%29^3%2B3%28%28a%28b^2%29%2B%28a^2%29b%29%28a%28b^2%29-%28a^2%29b%29%29

h--> wolframalpha.com/input/?i=%28a^2-b^2%29^3

我正在寻找为所有实数 n 和整数 k 定义的二项式系数 ( choose(n,k) ) 的有效 Java 实现，即定义为：

有吗a/b mod m = (a mod m)/(b mod m)？

我正在尝试为非常大的数字找到 nCr mod m。如果a/b mod m = (a mod m)/(b mod m)那时认为我会解决我的问题。

它适用于欧拉计划。我正在使用阶乘的 nCr 公式。

在我的 compsci UIL 类中存在一个挑战问题，即使用尾递归来获取给定数字的二项式系数列表。我想我已经很接近了，但我在基本情况下遇到了困难。

以下是我的代码：

现在我只是得到一个列表（1）.....

在这里，我尝试用 C++ 编写一个程序来查找 NCR。但是我的结果有问题。这是不正确的。你能帮我找出程序中的错误吗？

我想优化我的程序的一部分，我正在计算二项式系数的总和，直到 K。即

由于值超出了数据类型（long long）可以支持的范围，我要计算值 modM 并正在寻找执行此操作的程序。

目前，我已经使用 Pascal's Triangle 完成了它，但它似乎需要一些负载。所以，我想知道是否还有其他有效的方法可以做到这一点。我考虑过卢卡斯定理，尽管 MI 已经足够大，以至于 C(N,k) 失控了！

任何关于如何以不同方式执行此操作的指针，也许可以用其他一些简洁的总和表达式来计算整个总和。如果不是，我将把它留给 Pascal 的三角形方法本身。

谢谢，

这是我到目前为止所拥有的O(N^2)：

我需要n!/(n-r)!r!用 C# 计算。使用阶乘函数计算小数字很容易，但是当数字变得像 100 这样大时，它就不起作用了。有没有其他方法可以计算更大数字的组合？

我所说的“大 n”是指数以百万计的东西。p 是素数。

我已经尝试过 http://apps.topcoder.com/wiki/display/tc/SRM+467 但该功能似乎不正确（我用 144 选择 6 mod 5 对其进行了测试，当它应该给我时它给了我 0 2)

我试过 http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 但我不完全理解

我还制作了一个使用逻辑 (combinations(n-1, k-1, p)%p + combination(n-1, k, p)%p) 的记忆递归函数，但它给了我堆栈溢出问题，因为n 很大

我试过卢卡斯定理，但它似乎很慢或不准确。

我要做的就是创建一个快速/准确的 n 为大 n 选择 k mod p。如果有人可以帮助我展示一个很好的实现，我将不胜感激。谢谢。

根据要求，对于大 n 命中堆栈溢出的记忆版本：

我正在 InterviewStreet 进行练习程序，我有一个运行时间为 5.15xx 秒的解决方案，而 Java 解决方案允许的最长时间为 5 秒。我能用我在这里的东西做些什么来让它在 5 秒内完成吗？还有一个 256 MB 的限制，所以据我所知，这是解决问题的最节省时间和内存的方法......

编辑：N 和 K 的可能值是 N <= 10^9 和 K <= N，这就是为什么我选择使用 BigInteger 做所有事情的原因。最大试验次数为 10000。因此，基本上，您输入试验次数，然后输入每个试验次数的一对整数值，程序在第二个循环中计算方程的三个版本的二项式系数。我认为将所有内容读入数组，然后处理数组并将结果放入第三个数组以由第三个循环处理会更快，因为我认为这样可能会更快。我尝试在同一个循环中执行所有操作，但运行速度较慢。

我已经尝试了三种或四种不同的算法来计算二项式系数（nCr - 或 n 选择 r，都是说同一件事的不同方式）。一些算法涉及二维数组，如 c[n][k]。这是我提交的唯一没有出现某种内存错误的解决方案。答案需要输出 mod (10 ^ 6) + 3，因为 nCr * nCr 的答案非常庞大。该程序的示例运行是：

不能在更快的机器上运行它，因为它需要通过他们的机器来计算，基本上我提交代码并针对他们的测试用例运行它，我不知道他们的测试用例是什么，只是输入是在上面给出的范围内。

和程序本身：

}

我想计算数学中的系数。例如，我编写了这段代码来查找 (a+b*cos(x))^4 中 cos(kx) 的系数，其中“a”和“b”是参数。

它适用于 cos(k*x) 的系数，

例如 cos(2x) 的系数是

但它不适用于常数（这里常数意味着独立于 cos(kx)。换句话说，只是带有数字和参数“a”和“b”的术语）。

我想编写代码来查找上述含义中的常量。

谢谢。