计算加泰罗尼亚数字mod素数

Question

以下是问题描述:

让c[n]是加泰罗尼亚数量n和p是一个大素如.1000000007

我需要计算范围c[n] % p从哪里来n{1,2,3,...,1000}

我遇到的问题是,在32位计算机上,当你为这么大的整数计算加泰罗尼亚数时会出现溢出.我熟悉模运算.也

(a.b) % p = ((a % p)(b % p)) % p 

这个公式可以帮助我分别逃脱分子中的溢出,但我不知道如何处理分母.

Answer 1

对于1000000007的模数,避免仅使用32位整数的溢出是麻烦的.但任何体面的C实现都提供64位整数(任何体面的C++实现也都如此),所以这不是必需的.

然后,为了处理分母,正如KerrekSB在他的评论中所说的那样,一种可能性是计算以模数为模的分母的模逆p = 1000000007.您可以使用扩展的欧几里德算法计算模逆,或者等效地,使用扩展的欧几里德算法来计算k/p.然后,不是k在计算中除以,而是乘以其模数逆.

另一种选择是对加泰罗尼亚数字使用Segner的递归关系,这给出了一个没有划分的计算:

C(0) = 1
         n
C(n+1) = ? C(i)*C(n-i)
         0

因为你只需要Catalan数C(k)的k <= 1000,你可以预先计算它们,或者迅速在程序启动时计算它们并将它们存储在一个查找表.

如果与预期相反,没有64位整数类型可用,您可以通过将因子分为低16位和高16位来计算模块化产品,

a = a1 + (a2 << 16)    // 0 <= a1, a2 < (1 << 16)
b = b1 + (b2 << 16)    // 0 <= b1, b2 < (1 << 16)
a*b = a1*b1 + (a1*b2 << 16) + (a2*b1 << 16) + (a2*b2 << 32)

要计算a*b (mod m)使用m <= (1 << 31),减少四个产品模数m,

p1 = (a1*b1) % m;
p2 = (a1*b2) % m;
p3 = (a2*b1) % m;
p4 = (a2*b2) % m;

并且最简单的方法是合并班次

for(i = 0; i < 16; ++i) {
    p2 *= 2;
    if (p2 >= m) p2 -= m;
}

相同的for p3和32次迭代p4.然后

s = p1+p2;
if (s >= m) s -= m;
s += p3;
if (s >= m) s -= m;
s += p4;
if (s >= m) s -= m;
return s;

这种方式不是很快,但是对于这里需要的少数乘法,它足够快.应通过减少班次数来获得小幅加速; 先算一下(p4 << 16) % m,

for(i = 0; i < 16; ++i) {
    p4 *= 2;
    if (p4 >= m) p4 -= m;
}

然后全部p2,p3并且当前值p4需要乘以2 ¹⁶模数m,

p4 += p3;
if (p4 >= m) p4 -= m;
p4 += p2;
if (p4 >= m) p4 -= m;
for(i = 0; i < 16; ++i) {
    p4 *= 2;
    if (p4 >= m) p4 -= m;
}
s = p4+p1;
if (s >= m) s -= m;
return s;