Биномиальный коэффициент по модулю 142857

Алгоритм:

• разложить базу на простые степени; 142857 = 3^3×11×13×37
• вычислить результат по модулю каждой степени простого числа
• объединить результаты, используя китайскую теорему об остатках.

Чтобы вычислить (n above k) mod p^q:

Источник: http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf, теорема 1

определить (n!)_p как произведение чисел 1..n, которые не делятся на p

определить n_j как n после удаления j младших значащих цифр в базе p

определить r как n-k

определить e_j как количество переносов при добавлении k+r, не считая переносов из j младших цифр, вычисляя по основанию p

определить s как 1, если p=2 & q>=3, и -1 в противном случае

затем (n above k) mod p^q := p^e_0 * s^e_(q-1) * concatenate(j=d..0)( (n_j!)_p / ((k_j!)_p*(r_j!)_p) ), где каждый член конкатенации вычисляет одну цифру с основанием p результата, а самый низкий j вычисляет младшие значащие ненулевые цифры.

На самом деле вы можете вычислить C(n,k) % m за O(n) времени для произвольного m.

Хитрость заключается в том, чтобы вычислить n!, k! и (n-k)! как простые вектора мощности, вычесть два последних из первого и умножить остаток по модулю m. Для C(10, 4) делаем так:

10! = 2^8 * 3^4 * 5^2 * 7^1
 4! = 2^3 * 3^1
 6! = 2^4 * 3^2 * 5^1

Следовательно

C(10,4) = 2^1 * 3^1 * 5^1 * 7^1

Мы можем легко вычислить это mod m, так как делений нет. Хитрость заключается в том, чтобы рассчитать разложение n! и друзей за линейное время. Если мы предварительно вычислим простые числа до n, мы можем сделать это эффективно следующим образом: Ясно, что для каждого четного числа в произведении 1*2*...*9*10 мы получаем множитель 2. За каждое четвертое число мы получаем второе и так далее. Следовательно, количество факторов 2 в n! равно n/2 + n/4 + n/8 + ... (где / — пол). Мы делаем то же самое для остальных простых чисел, и поскольку есть O(n/logn) простых чисел, меньших n, и мы делаем O(logn) работы для каждого, разложение является линейным.

На практике я бы закодировал его более неявно следующим образом:

func Binom(n, k, mod int) int {
    coef := 1
    sieve := make([]bool, n+1)
    for p := 2; p <= n; p++ {
        // If p is not sieved yet, it is a prime number
        if !sieve[p] {
            // Sieve of Eratosthenes
            for i := p*p; i <= n; i += p {
                sieve[i] = true
            }
            // Calculate influence of p on coef
            for pow := p; pow <= n; pow *= p {
                cnt := n/pow - k/pow - (n-k)/pow
                for j := 0; j < cnt; j++ {
                    coef *= p
                    coef %= mod
                }
            }
        }
    }
    return coef
}

Это включает в себя сито Эратосфена, поэтому время работы составляет nloglogn, а не n, если бы простые числа были предварительно рассчитаны или просеяны с помощью более быстрого сита.

Что особенного в 142857, так это то, что 7 * 142857 = 999999 = 10 ^ 6 - 1. Это множитель, вытекающий из Малой теоремы Ферма с a = 10 и p = 7, что дает модульную эквивалентность 10 ^ 7 == 10 (mod 7 ). Это означает, что вы можете работать по модулю 999999 по большей части и уменьшать до конечного модуля, разделив на 7 в конце. Преимущество этого заключается в том, что модульное деление очень эффективно в базах представления формы 10 ^ k для k = 1,2,3,6. Все, что вы делаете в таких случаях, это складываете вместе группы цифр; это обобщение выбрасывания девяток.

Эта оптимизация действительно имеет смысл только в том случае, если у вас есть аппаратное умножение с основанием 10. Что на самом деле означает, что это работает хорошо, если вам приходится делать это с бумагой и карандашом. Поскольку эта проблема недавно появилась в онлайн-конкурсе, я полагаю, что это именно то, откуда возник вопрос.