How to use Modulo effectively?

Question

Im does (for myself) a very difficult task, where I have to calculate the maximum possible number of sequences when setting the number n of segments.

I found out that the Catalan number represents these sequences, and I got it to work with n <= 32. The results that I get should be calculated modulo 1.000.000.007. The problem is that “q” and “p” become large for a long int and I cannot just mod 1.000.000.007 before dividing “q” and “p”, because I get a different result.

My question is, is there really an effective way to solve my problem, or do I need to think about storing values ​​differently? My limitations are as follows: - only stdio.h / iostream - only integers - n <= 20,000,000 - 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); } 

Answer 1

To solve this problem effectively, you will want to use modular arithmetic , modular inverses , replacing the division.

It is easy to prove that in the absence of overflow (a * b) % c == ((a % c) * b) % c . If we just multiplied, we could take the results of mod 1000000007 at every step and always remain within the 64-bit integer. The problem is separation. (a / b) % c not necessarily equal to ((a % c) / b) % c .

To solve the division problem, we use modular inversions. For integers a and c with c prime and a % c != 0 we can always find an integer b such that a * b % c == 1 . This means that we can use multiplication as division. For any integer d divisible by a , (d * b) % c == (d / a) % c . This means that ((d % c) * b) % c == (d / a) % c , so we can reduce the intermediate results of mod c without twisting our ability to share.

The number we want to calculate is (x1 * x2 * x3 * ...) / (y1 * y2 * y3 * ...) % 1000000007 . Instead, we can calculate x = x1 % 1000000007 * x2 % 1000000007 * x3 % 1000000007 ... and y = y1 % 1000000007 * y2 % 1000000007 * y3 % 1000000007 ... , then calculate the modular inverse z of y using extended Euclidean algorithm and return (x * z) % 1000000007 .

Answer 2

If you use gcc or clang and a 64 bit target, there is an __ int128 type . This gives you extra bits to work with, but obviously only for the point.

Most likely, the easiest way to deal with this problem is to use the "bignum" library, that is, a library that deals with the representation and execution of arithmetic on arbitrarily large numbers. The most popular open source example is libgmp - you should easily get your algorithm. It is also tuned to high performance standards.

Obviously, you can override this yourself by presenting your numbers, for example. arrays of integers of a certain size. You will have to implement algorithms to perform basic arithmetic operations, such as +, -, *, /,% yourself. If you want to do this as a learning experience that is wonderful, but there is no shame in using libgmp if you just want to focus on the algorithm that you are trying to implement.