2

我正在尝试计算下面的大数表达式。

N!/((N/2)!(N/2)!)

由于这个表达式的值会很大，我只需要这个表达式的值取模一些素数。假设这个表达式的值为x并且我选择素数1000000007；我正在寻找x % 1000000007。

这是我的代码。

#include<iostream>
#define MOD 1000000007
using namespace std;
int main()
{
    unsigned long long A[1001];
    A[2]=2;
    for(int i=4;i<=1000;i+=2)
    {
        A[i]=((4*A[i-2])/i)%MOD;
        A[i]=(A[i]*(i-1))%MOD;

    while(1)
    {
        int N;
        cin>>N;
        cout<<A[N];
    }
}

但即使如此多的优化对于较大的 N 值也是失败的。例如，如果 N 为 50，则正确的输出是605552882，但这给了我132924730。如何进一步优化它以获得正确的输出？

注意：我只认为 N 是偶数。

4

2 回答 2

6

进行模运算时，没有除法之类的操作。取而代之的是，您取分母的模逆并相乘。模逆是使用 Etienne Bezout 在 1779 年发现的扩展欧几里得算法计算的：

# return y such that x * y == 1 (mod m)
function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q, r := divide(b, x)
        x, a, b, u := b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

该divide函数返回商和余数。上面给出的所有赋值运算符都是同时赋值，首先计算所有右侧，然后同时分配所有左侧。您可以在我的博客上看到更多关于模运算的信息。

于 2013-02-06T19:13:28.157 回答
1

  1. 对于初学者来说，根本不需要模除法，您的公式可以重写如下：

    N!/((N/2)!^2) =(1.2.3...N)/((1.2.3...N/2)*(1.2.3...N/2)) = ((N/2+1)...N)/(1.2.3...N/2))

    • 好的，现在您将较大的数字除以较小的数字
    • 所以你可以通过乘除数和除数来迭代结果
    • 所以展位子结果具有相似的幅度
    • 任何时候两个数字都可整除 2 将它们左移
    • 这将确保不会溢出
    • 如果你在 (N/2) 的和处！而不是只为其余的继续乘法。
    • 任何时候两个子结果都可以被任何东西整除
    • 直到你被除以 1
    • 在此之后，您可以乘以模算术直到正常结束。

  2. 有关更高级的方法，请参阅此。

    • N！和（N/2）！比第一眼看起来更容易分解
    • 我已经解决了一段时间了，...
    • 这是我发现的：Fast exact bigint factorial
    • 简而言之，N！和 ((N/2)!)^2 将完全消失。
    • 只有简单的素数分解 + 4N <-> 1N 修正会提醒

解决方案：

I. (4N!)=((2N!)^2) . mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]
II. (4N)!/((4N/2)!^2) = (4N)!/((2N)!^2)
----------------------------------------
I.=II. (4N)!/((2N)!^2)=mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]
  • 唯一的问题是 N 必须能被 4 整除……因此在所有方面都是 4N。
  • 如果您有 N%4!=0 则解决 NN%4 并且结果由 misin 1-3 数字正确。

希望能帮助到你

于 2013-09-03T14:31:39.923 回答