c - 如何有效地使用Modulo？

我做了一个(对我自己而言)非常复杂的任务，在给定段数n的情况下，我必须计算尽可能多的序列。

我发现加泰罗尼亚语数字表示此序列，并且我得到了它适用于n
我的问题是，有没有一种真正有效的方法来解决我的问题，还是我不得不考虑以不同的方式存储值？
我的限制如下:
-仅stdio.h/iostream
-仅整数
-n -n> = 2

#include <stdio.h>

long long cat(long long  l, long long  m, long long  n);

int main(){
    long long  n = 0;
    long long  val;
    scanf("%lld", &n);

    val = cat(1, 1, n / 2);

    printf("%lld", (val));

    return 0;
}

long long  cat(long long  q, long long  p, long long  n){
    if (n == 0) {
        return (q / p) % 1000000007;
    }
    else {
        q *= 4 * n - 2;
    }

    p *= (n + 1);

    return cat(q, p, n - 1);
}

最佳答案

为了有效地解决此问题，您需要使用modular arithmetic，用modular inverses代替除法。

很容易证明，在没有溢出的情况下，(a * b) % c == ((a % c) * b) % c。如果只是相乘，我们可以在每一步取结果mod 1000000007并始终保持在64位整数的范围内。问题是 split 。 (a / b) % c不一定等于((a % c) / b) % c。

为了解决除法问题，我们使用模逆。对于带有a素数和c的整数c和a % c != 0，我们总是可以找到一个整数b，例如a * b % c == 1。这意味着我们可以将乘法用作除法。对于可被d整除的任何整数a，(d * b) % c == (d / a) % c。这意味着((d % c) * b) % c == (d / a) % c，因此我们可以减少中间结果mod c而不会增加我们的除法能力。

我们要计算的数字的形式为(x1 * x2 * x3 * ...) / (y1 * y2 * y3 * ...) % 1000000007。我们可以代之以计算x = x1 % 1000000007 * x2 % 1000000007 * x3 % 1000000007 ...和y = y1 % 1000000007 * y2 % 1000000007 * y3 % 1000000007 ...，然后使用extended Euclidean algorithm计算z的模块化逆y并返回(x * z) % 1000000007。