3

这个问题的答案原来是使用卢卡斯定理计算大二项式系数模素数。这是使用此技术解决该问题的方法：here。

现在我的问题是：

  • 如果数据由于变量溢出而增加，似乎我的代码就会过期。有什么方法可以处理这个吗？
  • 有什么方法可以在不使用这个定理的情况下做到这一点？

编辑：请注意，由于这是OI 或 ACM问题，因此不允许使用原始库以外的外部库。

下面的代码：

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

#define N 100010

long long mod_pow(int a,int n,int p)
{
    long long ret=1;
    long long A=a;
    while(n)
    {
        if (n & 1)
            ret=(ret*A)%p;
        A=(A*A)%p;
        n>>=1;
    }
    return ret;
}

long long factorial[N];

void init(long long p)
{
    factorial[0] = 1;
    for(int i = 1;i <= p;i++)
        factorial[i] = factorial[i-1]*i%p;
    //for(int i = 0;i < p;i++)
        //ni[i] = mod_pow(factorial[i],p-2,p);
}

long long Lucas(long long a,long long k,long long p) 
{
    long long re = 1;
    while(a && k)
    {
        long long aa = a%p;long long bb = k%p;
        if(aa < bb) return 0; 
        re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p;
        a /= p;
        k /= p;
    }
    return re;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        long long n,m,p;
        cin >> n >> m >> p;
        init(p);
        cout << Lucas(n+m,m,p) << "\n";
    }
    return 0;
}
4

4 回答 4

4

此解决方案假定p 2适合于unsigned long long. 由于 anunsigned long long根据标准至少有 64 位，因此这至少适用于p高达 40 亿，比问题指定的要多得多。

typedef unsigned long long num;

/* x such that a*x = 1 mod p */
num modinv(num a, num p)
{
    /* implement this one on your own */
    /* you can use the extended Euclidean algorithm */
}

/* n chose m mod p */
/* computed with the theorem of Lucas */
num modbinom(num n, num m, num p)
{
    num i, result, divisor, n_, m_;

    if (m == 0)
        return 1;

    /* check for the likely case that the result is zero */
    if (n < m)
        return 0;

    for (n_ = n, m_ = m; m_ > 0; n_ /= p, m_ /= p)
        if (n_ % p < m_ % p)
            return 0;

    for (result = 1; n >= p || m >= p; n /= p, m /= p) {
        result *= modbinom(n % p, m % p, p);
        result %= p;
    }

    /* avoid unnecessary computations */
    if (m > n - m)
         m = n - m;

    divisor = 1;
    for (i = 0; i < m; i++) {
         result *= n - i;
         result %= p;

         divisor *= i + 1;
         divisor %= p;
    }

    result *= modinv(divisor, p);
    result %= p;

    return result;
}
于 2015-11-10T16:25:54.150 回答
0

无限精度整数似乎是要走的路。

如果您使用 C++，PicklingTools 库有一个“无限精度”整数（类似于 Python 的 LONG 类型）。其他人建议使用 Python，如果您了解 Python，这是一个合理的答案。如果你想用 C++ 来做，你可以使用 int_n 类型：

#include "ocval.h"
int_n n="012345678910227836478627843";
n = n + 1;   // Can combine with other plain ints as well

请查看以下位置的文档：

http://www.picklingtools.com/html/usersguide.html#c-int-n-and-the-python-arbitrary-size-ints-long

和

http://www.picklingtools.com/html/faq.html#c-and-otab-tup-int-un-int-n-new-in-picklingtools-1-2-0

C++ PicklingTools 的下载地址在这里。

于 2015-11-10T15:10:59.977 回答
0

假设我们需要计算(a / b) mod pwherep是素数的值。因为p是素数，所以每个数字b都有一个反模p。所以(a / b) mod p = (a mod p) * (b mod p)^-1。我们可以使用欧几里得算法来计算逆。

为了得到(n over k)，我们需要计算n! mod p, (k!)^-1, ((n - k)!)^-1. 总时间复杂度为O(n)。

更新：这是 C++ 中的代码。虽然我没有对它进行广泛的测试。

int64_t fastPow(int64_t a, int64_t exp, int64_t mod)                               
{                                                                                  
    int64_t res = 1;                                                               
    while (exp)                                                                    
    {                                                                              
        if (exp % 2 == 1)                                                          
        {                                                                          
            res *= a;                                                              
            res %= mod;                                                            
        }                                                                          

        a *= a;                                                                    
        a %= mod;                                                                  
        exp >>= 1;                                                                 
    }                                                                              
    return res;                                                                    
}                                                                                  

// This inverse works only for primes p, it uses Fermat's little theorem                                                                                   
int64_t inverse(int64_t a, int64_t p)                                              
{                                                                                  
    assert(p >= 2);                                                                
    return fastPow(a, p - 2, p);                                                   
}                                                                                  

int64_t binomial(int64_t n, int64_t k, int64_t p)                                  
{                                                                                  
    std::vector<int64_t> fact(n + 1);                                              
    fact[0] = 1;                                                                   
    for (auto i = 1; i <= n; ++i)                                                  
        fact[i] = (fact[i - 1] * i) % p;                                           

    return ((((fact[n] * inverse(fact[k], p)) % p) * inverse(fact[n - k], p)) % p);
}
于 2015-11-10T16:27:57.390 回答
0

您需要一个bignum（又名任意精度算术）库。

首先，不要编写自己的 bignum（或 bigint）库，因为高效算法（比您在学校学到的幼稚算法更高效）很难设计和实现。

然后，我会推荐GMPlib。它是免费软件，有据可查，经常使用，效率很高，设计得很好（可能有一些缺陷，特别是无法插入自己的内存分配器来替换系统malloc；但你可能不在乎，除非你想要捕捉罕见的内存不足情况......）。它有一个简单的C++ 接口。它被打包在大多数 Linux 发行版中。

如果是家庭作业，也许你的老师希望你更多地思考数学，并通过一些证据找到一种解决问题的方法，而不需要任何大数。

于 2015-11-10T15:15:56.693 回答