% mod совместимые способы генерации биномиальных коэффициентов - PullRequest
Новая
       33

% mod совместимые способы генерации биномиальных коэффициентов

3 голосов
/ 21 февраля 2012

Я хотел бы оптимизировать часть моей программы, в которой я вычисляю сумму биномиальных коэффициентов до K. т.е.Поддерживаю, я рассчитываю значения мод M и искал процедуры для этого.

В настоящее время я сделал это с помощью треугольника Паскаля, но, похоже, он немного загружен.поэтому мне было интересно, есть ли другой эффективный способ сделать это.Я рассмотрел теорему Лукаса, хотя MI уже достаточно велик, так что C (N, k) выходит из-под контроля!

Любые указатели, как, как я могу сделать это по-другому, возможно, рассчитать всю сумму вместе с некоторым другим аккуратным выражением суммы.Если нет, я оставлю это с помощью самого метода треугольника Паскаля.

Спасибо,

Вот что у меня есть до сих пор O(N^2): 

#define MAX 1000000007
long long NChooseK_Sum(int N, int K){
    vector<long long> prevV, V;
    prevV.push_back(1);     prevV.push_back(1);
    for(int i=2;i<=N;++i){
            V.clear();
            V.push_back(1);
            for(int j=0;j<(i-1);++j){
                    long long val = prevV[j] + prevV[j+1];
                    if(val >= MAX)
                            val %= MAX;
                    V.push_back(val);
            }
            V.push_back(1);
            prevV = V;
    }
    long long res=0;
    for(int i=0;i<=K;++i){
            res+=V[i];
            if(res >= MAX)
                    res %= MAX;
    }
    return res;
}

1 Ответ

5 голосов
/ 21 февраля 2012

Алгоритм, который выполняет линейное число арифметических операций Бигнума: 

def binom(n):
    nck = 1
    for k in range(n + 1):  # 0..n
        yield nck
        nck = (nck * (n - k)) / (k + 1)

При этом используется деление, но по модулю простого числа p вы можете сделать почти то же самое, умножив на решение i уравнение i * (k + 1) = 1 mod p. Значение i можно найти в логарифмическом числе арифметических операций с помощью расширенного евклидова алгоритма .

...